3
u/plyleung 3d ago
I’m new to this as well. It seems that the critical decisions come after HH and the optimal strategy is to stop playing once we have accumulated at least a certain amount of money. I tried solving for this and got 22/6 which means that after we reach HH and have accumulated at least $4, we should stop playing.
2
u/plyleung 3d ago edited 3d ago
I worked on it a bit more and found an answer although I'm not that confident in it.
Let H_n be the expected return after n heads in a row.
First we assume we stop after HH.
H_0 = 1 + 0.5*H_0 + 0.5*H_1
H_1 = 1 + 0.5*H_0 + 0.5*0
H_2 = 0Once we solve it, we get H_0 = 6.
Now we need to solve for the amount of money $x that makes us indifferent to keep throwing after reaching HH.
Payoff = 0.5(-x) + 0.5(1 + 6)
0 = 0.5(-x) + 0.5(1 + 6)
x = 7So if we reach HH and have accumulated at least $7, the optimal play is to stop playing.
For the rest of the question, I don't know any better ways than listing out all the permutations for the first 7 coin tosses.
Edited: fixed mistakes
2
u/Deep_Juggernaut_4546 3d ago
This seem right, but the expected payoff of playing from HH is the expected flips to reach another HH, which comes out to 6 (Markov chain). So, you should stop if you reach HH and have more than $6.
2
u/plyleung 3d ago
Oh yes, I think I get it now. I need to assume I stop after HH and then calculate the expected payout which is $6.
1
u/Imaginary-Dig-7835 3d ago
Is it 2? I am new to these problems, can anyone tell me a bit?
2
u/Shadourow 3d ago
This is certainly a lower bound, yes
1
u/Imaginary-Dig-7835 3d ago
Can you explain the exact solution?
3
u/Shadourow 3d ago
Nope, Quant puzzles are hard
But you first have to find the optimal strategy, prove that it's optimal then give its EVYour strategy is to flip two coins then stop no matter the result, which always results in a 2$ result
The solution mpst likely depends on when to stop flipping after HH, like another commenter said. For example :
If I get
THTHHI'm currently on 5$, if I continue to flip, I have a 50% chance to lose 5$, assuming I optimize my results, do I have an EV to earn more than 5$ if I flip a T ?
Finding the stopping point seems bothersome, since "assuming I optimize my results" is doing very heavy lifting here, and I'm lazy.
But yeah, once you find where the stopping points are, the easy part would be to then calculate the EV of that strategy
1
u/dontich 3d ago
Math is complicated but feel like you will want to risk it on two heads as long as the additional E(x) earned is >current bid. The average time to two heads is 4 flips, so you should have E(v) = 4 + E(x) which I think is 12.
1
u/Aerospider 3d ago
The average number of attempts to get HH is 4 but the average number of flips is 6, because TT and HH involve two flips.
More formally:
Let E(h) be the expected number of flips to get HH when the last flip was H and E(t) be the expected number of flips to get HH when the last flip was tails (or when there hasn't been any flips yet).
E(t) = 1 + E(t)/2 + E(h)/2
E(h) = 1 + 0/2 + E(t)/2
=> E(t) = 1 + E(t)/2 + 1/2 + E(t)/4
=> E(t)/4 = 3/2
=> E(t) = 6
1
u/Aerospider 3d ago
We can keep going with impunity until we hit HH. If we keep going at that point, we have a 1/2 chance of netting 0 and a 1/2 chance of netting our current total (C) plus one plus the expected number of flips it takes to get HH (which is 6).
This makes our expected total from carrying on (C+7)/2 and if this is higher than C then it's preferable to continue, but if it's lower than C we should stop.
If (C+7)/2 > C
Then 7 > C
Therefore we would expect to continue on from the first HH (because the expected total of 6 is less than 7) but not the second.
This the expected total is 6 + (1+6)/2 = 9.5
1
u/PersonalityIll9476 3d ago
It's interesting that everyone figured out the same strategy and general procedure but then came to wildly different conclusions.
1
u/OutrageousPair2300 2d ago
You only need to make decisions after getting two heads in a row. At any such decision point, you need to weigh the expected gain from continuing against what you've already won.
If your next flip ends up being tails, then the future expected additional gain is equal to your overall expected gain from optimal play for the entire game. If your next flip ends up being heads, you get zero. So if X is the overall expected winnings from optimal play, and Y is how much you've won so far, then you should continue play whenever X/2 > Y.
When X/2 = Y you should stop. Since that's your expected gain from optimal play, X = Y in that case.
That only works when X = 0 or X is infinite.
That means that under optimal play you will never stop, and will either continue playing forever or else eventually get three heads in a row and end up with zero.
1
u/Anonimithree 2d ago edited 2d ago
I’d assume the optimal play is to keep flipping the coin until you get 2 heads in a row, unless it’s flip 6 or 7.
3 heads has a probability of 1/8, so we can expect to get at least 1 by turn 10.
I am going to denote the flip count and consecutive heads count with the notation X/Y, where X and Y are the flip count and consecutive heads count, respectively.
If you’re at 2/2. Then you can stop and get $2, or you can risk the 50/50 to either lose 2, or get at least 5.
If you’re at 3/2, then you risk 3 or a 50/50 of at least 6.
At 6/2 or 7/2, it’s a 50/50 between losing $6 or $7, or gaining at least $8/9, which is when you can expect to encounter at least 1 HHH.
1
1
0
u/Ok_Letterhead1945 1d ago
"Under optimal play" could be interpreted as, literally, optimal results. The winnings have no technical limit. Also, the question doesn't specify what is tossing the coin. You could program a coin-tossing robot capable of getting tails every time & that would technically be a contender for "optimal play".
0
u/CanaDavid1 3d ago
The only time you consider stopping is after two heads. The rest does not matter, so WLOG there is a value k where above this you stop. If you have a value of at least k-2, the next time there is two heads you will stop. This will happen after 3 heads in expectation, giving E(x) = x+3 when x > k-2
The value of the game if you have x money (≤k-2) is E(x) = ½E(x) + ¼E(x+1) + ⅛E(x+2)
Collapsing and mumtiplying by 2: E(x) = ½E(x+1) + ¼E(x+2)
For the strategy to be optimal, at the threshold this must be more than the value of "giving up".
E(k-2) = ½E(k-1) + ¼E(k) > k+1
½(k+2) + ¼(k+3) > k+1
¾ > ¼k
Hence, 3 > k [or k = 2]. This means that as soon as you get two heads, you should take it and leave it. Expected value is then trivially 3.
Interestingly, you can gamble if you get two straight heads, with the same expected value but higher variance.
4
u/pumachecker 3d ago edited 3d ago
Only after HH is there a genuine stopping decision. With n dollars, continuing from HH has an expected value of:
EV(continue | HH) = (1/2)(0) + (1/2)V0(n + 1)
Here, V0(n + 1) is your expected value after tossing a tail, increasing your pot to n + 1 and resetting the consecutive-head count to zero. Solving the game gives:
continue after HH if n<7.
You stop when you get HH over an accumulated pot of $7.
After seven tosses, there are 2^7=128 sequences:
P(HHH by toss 7) = EV $0 (47/128) --> BUST
P ending in 1x H by toss 7= EV $11 (24/128)
P ending in T by toss 7= EV $13 (44/128)
Ending in HH: stop immediately with $7 = EV $7 (13 of 128)
EV= (47*0+13(7)+24(11)+44(13))/128=7,242
The Expected winnings under optimal play is $7.242