Expected number of coinflips needed until you get all heads or tails

expected valueprobability

I've been trying to figure out this question using the recursive method.

What is the expected value of number of flips to get 4 coins to all
land on heads, where once a coin lands on heads you dont have the
reflip it, Also, if you had a wand that could flip any pair of identically facing coins with unlimited uses what would the new expected value be?

For the first question, my attempt is as follows:

For one coin case, expected flip is 2, which is clear.
For 2 coins, you flip them first. There are 3 possible scenarios: 1/4 chance of having 0 head, 1/2 chance of having 1 head, 1/4 chance of having 2 heads.

If we set $a$ as the expected number of tosses needed for 2 coins, then we could set the equation as this:

$a = 1 + (1/4)*a + (1/2)*2 + (1/4) * 0 $
so that $a$ would be 8/3.

However, my intuition tells me that: by using simpler method: if we toss 2 coins, that expected number of head is 1, assuming the fair coin. And then since 1 coin is left, we add 2 since expected tosses for getting head with one coin is 2. So the total expected number would be $1 + 2
= 3$

So I'm confused which approach is right, and if one is wrong, why would it be?

Best Answer

I am not completely sure about my understanding of the question (please check).

My understanding described with $n$ replacing $4$ to make things more general:

Let there be $n$ coins. The first flip is a flip of all coins and if $k$ head appears then we put these coins aside so that the next flip will be a flip of $n-k$ coins. The process ends if all coins are put aside.

To be found is then $\mu_4$.

This can be done on base of the following equalities:

  • $\mu_4=1+\frac4{16}\mu_1+\frac6{16}\mu_2+\frac4{16}\mu_3+\frac1{16}\mu_4$
  • $\mu_3=1+\frac38\mu_1+\frac38\mu_2+\frac18\mu_3$
  • $\mu_2=1+\frac24\mu_1+\frac14\mu_2$
  • $\mu_1=1+\frac12\mu_1$

This is based on: $$\mu_n=\sum_{k=0}^nP(n-k\text{ heads appear by throwing }n\text{ coins})(1+\mu_k)$$where $\mu_0:=0$.

It is handsome to start with the last one and find $\mu_1,\mu_2,\mu_3,\mu_4$ respectively.

For the second question I have no answer mainly because I do not understand what they mean (what exactly is a "wand"?).

Edit on second problem:

The wand (a new word for me) reduces things to the question: is the number of tails that appear even or odd? Then for every $n\geq1$ we have the equality:$$\mu_n=1+\frac12\mu_1$$

Consequently $\mu_n=2$ for every $n$.

Related Question