3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Sep 9, 2023 at 2:26
  • $\begingroup$ By "this," I meant I can't get a closed form for $\sum_n (2n+1)P(X=2n+1).$ $\endgroup$ Sep 9, 2023 at 2:42
  • $\begingroup$ 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 $\endgroup$
    – shrizzy
    Sep 9, 2023 at 2:57
  • 1
    $\begingroup$ 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 $\endgroup$
    – minorChaos
    Sep 9, 2023 at 3:49
  • $\begingroup$ The expected revisit time on a symmetric random walk is infinite, so the answer to this question too is infinite. $\endgroup$
    – Brian Tung
    Sep 9, 2023 at 5:13

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 9, 2023 at 3:43
-2
$\begingroup$

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.

Generalize ad lib

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 $

$\endgroup$
7
  • 3
    $\begingroup$ 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} $\endgroup$ Sep 9, 2023 at 2:46
  • 2
    $\begingroup$ Or you can write \binom N{H+1} for $\binom N{H+1}.$ $\endgroup$ Sep 9, 2023 at 2:48
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 9, 2023 at 3:28
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 9, 2023 at 3:33
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 9, 2023 at 3:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .