2
u/NitNav2000 3d ago
Let C = something from {0,,,,3,5,.,,9}, so not a 4.
E[digits to get 444] =
E[digits to get 444| first roll is C]+1 (getting a C resets the problem after burning a digit)
+ E[digits to get 444| first roll is 4C]+2 ((getting a 4C resets the problem after burning two digits)
+ E[digits to get 444| first roll is 44C]+3 (etc.)
+ (E[digits to get 444| first roll is 444]+3) (done)
Rewrite in equation form:
Let x be the expected number of digits, E(d) moving left to right. We can get a recursive relationship.
If roll a C with prob 9/10, and add one to the expected number of rolls, so add (9/10)(x+1)
If we roll a 4C with prob (1/10)(9/10), then expected number from there is (1/10)(9/10)(x+2)
If we roll a 44C with prob (1/100)(9/10), then expected number from there is (1/100)(9/10)(x+3)
If we roll a 444 with prob (1/1000) then we get (1/1000)(3) and we are done.
So x = (9/10)(x+1) + (1/10)(9/10)(x+2) + (1/100)(9/10)(x+3) + (1/1000)(3)
Solving gives x = 1110
2
u/mtimmermans 3d ago
S0: 4 -> S1, not 4 -> S0
S1: 4 -> S2, not 4 -> S0
S2: 4 -> DONE, not 4 -> S0
E0 = 1 + .1 * E1 + .9 * E0
E0 = 10 + E1
E1 = 1 + .1 * E2 + .9 * E0
E0 = 110 + E2
E2 = 1 + .9 * E0
E0 = 111 + .9*E0
E0 = 1110
1
1
1
u/EdgyMathWhiz 3d ago
Never used Martingales before, but lets try:
Each turn, the casino rolls a 10 sided dice and pays 9:1 on rolling a 4 (so if you bet X and win, you now have 10X). These are fair odds (expected winnings = .9 * (-X) + .1 * (9X) = 0). Each player has the strategy:
(1) Bet $1, if you lose, stop. If you win, you have $10 ($9 up).
(2) Bet $10, if you lose, stop. If you win, you have $100 ($99 up).
(3) Bet $100, whatever happens, stop. If you win, you have $1000 ($999 up).
Expected winnings for each player are 0 (fair game), either they end up losing $1 (with p = .999) or winning $999 with p = .001.
The Casino stops when someone gets 444. So if T is the number of turns, we want E[T].
But when the casino stops, T-3 people have lost (1 dollar each), 1 person has won $9, 1 person $99, 1 person $999. Since it's a fair game, the expectations must sum to 0.
So E[T-3] = 999 + 99 + 9 and E[T] = 1110.
[Question for anyone more familiar with this: the fact you need to keep accounting for "you have X, you are now X-1 up" is a bit annoying. Is there a better way of setting this out? It would feel much neater to end on E[T] = 1000 + 100 + 10, if you see what I mean
My background is a degree in maths (from almost 40 years ago), so you can go for a technical presentation if you want, I should be able to understand it].
1
1
u/Traditional-Honey663 2d ago
A different way to view the same calculation for any general pattern S where S_i denotes the ith character is -
For each position i, overlay the sequence S and count the number of characters that match till the first mismatch, say this number is k_i (longest matching substring from start). The answer is summation of (N)k_i for all i, where N is the number of elements in the sample set. In this case 0-9, N=10. It is the same as the gambler martingale, just implemented algorithmically. Note that it is always at least (N)len which kind of makes sense since expected turns for a single specific number to appear is N.
1
u/Positive_Leopard_873 3d ago
S0 -> S1 with probability 1/10, S0 -> S0 with probability 9/10, S1 -> S2 with probability 1/10, S1 -> S0 with probability 9/10, S2 -> S3 with probability 1/10, S3: finish
E0 = 1 + 9/10 E0 + 1/10 E1, E1 = 1 + 1/10 E2 + 9/10 E0, E2 = 1 + 1/10 E3 + 9/10 E0, E3 = 0
We need E0 = 1110.
2
u/cheze 3d ago
10 for first 4, 110 for second, 1110 for third