This question was asked in an interview of a Quantitative finance company.
You have $\textit{n}$ fair coins with either heads or tails facing up arranged in a row.
You play a game in rounds described as follows:
In each round check the number of coins having heads. Let it be $\textit{k}$. Now flip the $\textit{k}^{th}$, i.e., if it is head change it to tail, or if it is tail change it to head.
Continue this game until all the coins facing up are tails.
Find the expected number of flips to get the desired arrangement of coins.
I was using the approach that if I have k heads at any instant:
$E_{k}$ describes the expected number of steps to reach k heads. We need to find the value of $E_0$.
\begin{equation}
E_k=\frac{k}{n}E_{k-1}+\frac{n-k}{n}E_{k+1}
\end{equation}
I don't know whether this approach is right. Please suggest some better methods.
Asked
Active
Viewed 102 times
1
Jose Avilez
- 12,710
Md Kaif Faiyaz
- 320
-
1Is there anything random in this game aside from the initial arrangement of coins? – user6247850 Nov 20 '23 at 17:59
-
1Hi! I think it's better if you try figuring out the dynamics of the situation. Suppose $n = 10$ and initially coins $1$, $3$, $8$, and $10$ are heads. Figure out the progression toward the all-tails state. After you figure that out, see if you can generalize how this progression happens. – Brian Tung Nov 20 '23 at 19:49
-
@user6247850 no there is no other random than the initial arrangement – Md Kaif Faiyaz Nov 20 '23 at 20:01
-
@BrianTung I am unable to arrive at a general result. It would be great if you could help me out. – Md Kaif Faiyaz Nov 20 '23 at 20:02
-
What is the sequence of $k$ in the example scenario I described? – Brian Tung Nov 20 '23 at 20:58
-
Your approach is likely wrong, because the number of flips is dependent on the arrangement, and not just the number of heads that are up. (Also, note that you forgot to +1 for the current flip) – Calvin Lin Nov 21 '23 at 02:48
-
@CalvinLin could you please suggest what should be the approach? I am unable to arrive at the answer – Md Kaif Faiyaz Nov 21 '23 at 16:21
-
I suggest to condition on "largest index $k$ that is a heads". – Calvin Lin Nov 21 '23 at 16:23
-
Do you have any information on how the coins are initially distributed, i.e. are they distributed uniformly? – H. sapiens rex Nov 22 '23 at 05:48
-
@CalvinLin They are distributed in any possible way initially like they can have any possible number of heads initially in any possible manner. Like there are $2^n$ initial states possible. – Md Kaif Faiyaz Nov 22 '23 at 09:40
-
@H.sapiensrex please look at the above comment – Md Kaif Faiyaz Nov 22 '23 at 09:41
-
@MdKaifFaiyaz At which firm was this asked ? – Gabriel Romon Nov 22 '23 at 13:39