# Flip coin until more heads

Suppose we flip a coin until we get more heads than tails. What is our expected number of flips?

I'm struggling with my approach here. Suppose our expected number of flips is $$X$$. We can say $$X = \frac12\cdot1 + \frac12(1 + Y)$$ where $$Y$$ is the number of flips needed to get $$2$$ more heads than tails. The problem is I think $$Y = 2X$$ which does not leave me with a solvable equation. Any guidance would be appreciated.

• It is worth reading the Dyck words section of Catalan numbers. This gives use, if $X$ is the random variable of the number of such terms, then $$P(X=2n+1)=\dfrac{\frac1{n+1} \binom{2n}n}{2^{2n+1}}$$ and $P(X=2n)=0.$ I'm having trouble getting this in closed form, though. en.wikipedia.org/wiki/Catalan_number?wprov=sfti1 Sep 9, 2023 at 2:26
• By "this," I meant I can't get a closed form for $\sum_n (2n+1)P(X=2n+1).$ Sep 9, 2023 at 2:42
• I'll take what I can get lol. Kind of just want to get a better understanding of the question and if there are approaches to either @minorChaos Sep 9, 2023 at 2:57
• If your equations are correct, and if they do not have (finite) solution, the expectation value must be infinite. This fits well with some of the answers. @shrizzy Sep 9, 2023 at 3:49
• The expected revisit time on a symmetric random walk is infinite, so the answer to this question too is infinite. Sep 9, 2023 at 5:13

Actually, the expected number of flips is $$\infty$$. Let $$n$$ denote (the number of tails $$-$$ the number of heads). Let $$X_{n+1}$$ denote the expected number of flips when you have $$n$$ more tails than heads. Suppose the process also ends when $$n+1=w>0$$, then \begin{align} X_{0}&=0&\\ X_{1}&=1+\frac12X_{0}+\frac12X_2&\\ X_{n}&=1+\frac12X_{n-1}+\frac12X_{n+1}&\\ \dots&=\dots\\ X_{w}&=0& \end{align} The solution of this inhomogeneous system of equations is $$X_n=n(w-n)$$ The expected number of flips is $$X_1=w-1\to\infty\:(w\to\infty)$$ if the flipping can continue indefinitely. The process ends with probability $$1$$ (eventually we will get more heads than tails), but the expected number of flips is infinite.

• This is what I was starting to believe from a direct computation using Catalan numbers, but it seemed wrong. I guess I should have trusted my math. Sep 9, 2023 at 3:43

For 3 tosses ....
HHH, HHT, HTH, HTT, THH, THT, TTH, TTT

X = 2 or more heads

$$P(X) = \frac{4}{8} = \frac{1}{2}$$

That is to say you'll need at least 2 sets of 3 tosses each to get just one set (3 tosses) with more heads than tails.

N tosses, H = the number of heads $$H> \frac{1}{2}N$$

The number of heads H = $$^NC _H + ^NC_{H+1}+ ... + ^NC_N$$

The probability of H number of heads = $$\frac{^NC_H + ^NC_{H+1}+ ... + ^NC_N}{2^N}$$

The random variable (X) here is the number of tosses needed to get more heads than tails.

We could do a simulation or use a random numbers table and calculate the arithmetic mean of the number of tosses. This would be an experimental probability but the question is about theoretical probability.

$$E_2$$ = 2 tosses are required: HH
$$P(E_1) = \frac{1}{4}$$
$$E_3$$ = 3 tosses are required: HTH, THH
$$P(E_3) = \frac{2}{8} = \frac{1}{4}$$
$$E_4$$ = 4 tosses are required: HTHH, HHTH
$$P(E_4) = \frac{2}{16} = \frac{1}{8}$$
$$E_5$$ = 5 tosses are required: HTTHH, THTHH, TTHHH, HHTTH
$$P(E_5) = \frac{4}{32} = \frac{1}{8}$$

Is there a pattern?
Over the interval 2 tosses to 5 tosses, the number of tosses you'll need so that you have more heads than tails is, on average, $$\frac{1 \times 2 + 2 \times 3 + 2 \times 4 + 4 \times 5}{9} = \frac{36}{9} = 4$$

• This is not at all clear what you are saying. The number of heads is equal t9 that binomial sum which depends on $H?$ Also, use braces around expressions to get complex subscripts: C_{H+1} Sep 9, 2023 at 2:46
• Or you can write \binom N{H+1} for $\binom N{H+1}.$ Sep 9, 2023 at 2:48
• The sum you call a probability isn't even $\leq 1$ in most cases. You want $2^N$ in the denominator. But it is far from clear how this can be used to compute the expected value. This is a trickier problem than this. For example, if you want the first time you have more heads than tails, you want $N+1$ heads and $N$ tails for some $N,$ but you also want to ensure it didn't happen any prior toss. So knowing the probability of just having $N+1$ heads out of $2N+1$ tosses doesn't give you what you want. Sep 9, 2023 at 3:28
• In any event, you mean "the number of ways of getting $H$ heads in $N$ tosses is..." not "the number of heads $H$ $=,$" which is just wrong and hard to fathom what you are trying to say. Sep 9, 2023 at 3:33
• Yeah, that isn't going to work. If you think you can make it work, write a full answer. As it is now, this answer, even reading it as you seem to intend it, gives no way to answer the question. Sep 9, 2023 at 3:58