AdministratorNovember 5, 2018 at 6:05 pm
What is the expected number of tosses until you get five heads in a row with a fair coin?
MemberJune 18, 2020 at 5:06 pm
AdministratorJune 18, 2020 at 5:55 pm
That’s correct! What is your solution? Betting strategy, recursion, or something else?
MemberOctober 15, 2020 at 5:46 pm
Let E(n) be the expected number of tosses until we get n heads with a fair coin.
So, E(n-1) is the expected number of tosses until we get (n-1) heads. So, After getting this (n-1) heads, If we get another head, We will get n heads. Otherwise We are back to the starting point. The experiment has to begin again till we get n heads.
So, E(n)= (E(n-1)+1)/2 + (E(n-1)+1+E(n))/2
The first portion is the case when we get head after (n-1) heads. So, Total number of tosses is E(n-1)+1 and that happens with the probability 1/2 . In the second portion, We get tail. So, Number of tosses is E(n-1)+1+E(n) . // 1 for tail. E(n) as the experiment begins again from the start//. That too happens with the probability 1/2.
Rearranging the equation gives E(n)=2(E(n-1)+1). Note that E(1)=2. That is the Expected number of tosses till we get one head.
To see that, Note It can happen like H, TH, TTH, TTTH and so on.
So, E(1) = 1*1/2 + 2*(1/2)^2 + 3*(1/2)^3 +…. = 2
So, We have E(n)=2(E(n-1)+1) with initial condition E(1)=2. Solving this recurrence equation, We get E(n)=2^(n+1)-2
When n=5, E(5)=2^6-2 = 62
Thanks for reminding the probability stuff, Puzzle Prime!
AdministratorOctober 15, 2020 at 6:05 pm
That’s a neat recursive solution @Vivek . Here is another one you may like, based on the optional stopping time theorem.
Bet $1 to get an H. If you get an H, bet $3 to get another H. If you get it right again, bet $7, and so on. If you have thrown T on the Nth move, then you would have lost exactly $N. Therefore, when you win the game with 5Hs in a row, you would end up with -N+1+3+7+15+31 = -N+57 dollars. Since you can’t trick the game, your expected profits must be equal to 0, and therefore you need N+5 = 57+5 = 62 moves.
MemberOctober 15, 2020 at 6:15 pm
Wow interesting…reading about optional stopping theorem…