5
$\begingroup$

Assume there are $n$ coins in a circle. They show Heads with probability $1/2$ and Tails with probability $1/2$.

--Iterative step---

One of the coins that shows Heads is randomly chosen and this coin and its two neighbors (the coin on the right and the one on the left from it) are flipped again. The probability of showing Heads for any coin from now on is $p$.


This procedure repeats.

We need to find the function of the expected number of iterations to get all Tails in the circle.

Can you help me with this? Is there any elegant way to proceed?

$\endgroup$
  • $\begingroup$ "One of the coins that shows Heads"-- is this chosen at random? $\endgroup$ – CommonerG Mar 29 '16 at 22:22
  • $\begingroup$ After the iterative step your event is ill defined. Probability of what showing heads is now p? All 3? $\endgroup$ – kodlu Mar 29 '16 at 22:23
  • $\begingroup$ @CommonerG: yes, at random. I editied the question. $\endgroup$ – Vika Mar 29 '16 at 22:28
  • $\begingroup$ @kodlu: all three, and this will be the probability from that step and all subsequent steps. I edited the question. $\endgroup$ – Vika Mar 29 '16 at 22:29
  • $\begingroup$ Does the first flip (when the probabilities are 1/2) count as an iteration? $\endgroup$ – CommonerG Mar 29 '16 at 22:33
1
$\begingroup$

This isn't a complete answer, just a note that is too long for the comments.

This can be represented using a Markov process with "All Tails" as an absorbing state. Being clever about how to leverage symmetry in representing the states can probably make the problem a bit easier. For instance, when there are 3 coins, there are only two states that matter: all tails, not all tails. The probability of moving to the "all tails" state is the same from any "not all tails" state since you flip all three coins anyway. Clearly, things get much more complicated as the number of coins increases.

For 3 coins:

Conditional on not having all tails in the first place, the number of iterations is geometrically distributed with success probability $(1-p)^3$. You need an average of $\frac{1}{(1-p)^3}$ iterations. The probability of not having all tails in the first place is $\frac{7}{8}$ so the average number of iterations you need is $\frac{7}{8(1-p)^3}$.

When $p=\frac{1}{2}$, you need an average of 7 iterations.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.