0
$\begingroup$

Imagine a game scenario in which you toss a coin indefinitely until the cumulative number of heads exceeds the cumulative number of tails, upon which you stop. Given the general case that there is a $\frac{1}{p}$ chance of getting heads on each toss, what is the probability that the game will EVER stop?

It is hypothesized that there is a $\frac{1}{p-1}$ chance of ever achieving more heads than tails, when $p\geq 2$(doesn't need to be an integer). This is on the basis of spreadsheet experiments.

Can anybody prove this? Thanks.

$\endgroup$
  • 1
    $\begingroup$ Condition on the first result: it is heads with probability $1/p$ and then you win with probability $1$, and it is tails with probability $1-1/p$ and then you have to win twice. Thus the probability $w$ to win solves $$w=1\cdot1/p+w^2\cdot(1-1/p),$$ that is, $(w-1)((p-1)w-1)=0$. If $p>2$, there is positive probability to never win hence $w\ne1$, which implies that indeed $w=1/(p-1)$. If $1\leqslant p\leqslant2$, $w=1$ (only root between $0$ and $1$). This avoids summing infinite series or requiring extrinsic knowledge. $\endgroup$ – Did Jun 26 '15 at 13:12
0
$\begingroup$

We just have to count the number of strings over the alphabet $\{H,T\}$ with the property that the number of heads is exactly one more than the number of tails, and in every prefix the number of heads is $\leq $ the number of tails. Let $E$ be such a set. This is clearly related with the ballot theorem and Catalan numbers.

In particular, there are $\frac{1}{n+1}\binom{2n}{n}$ elements of $E$ with length $2n+1$, every one of them occurring with probability $\frac{1}{p^{n+1}}\left(1-\frac{1}{p}\right)^n$. So, assuming $p\geq 2$, we have that the probability that the game stops, soon or later, is given by:

$$ \frac{1}{p}\sum_{n\geq 0}\frac{1}{n+1}\binom{2n}{n}\left(\frac{1}{p}-\frac{1}{p^2}\right)^n =\frac{1}{p-1}$$ as conjectured.

$\endgroup$
  • $\begingroup$ Thanks for this proof. I understood most of it, but could you elaborate on the last part, where I haven't been able to see how LHS simplifies to RHS. $\endgroup$ – Thomas Delaney Jun 27 '15 at 1:06
  • $\begingroup$ @ThomasDelaney: oh, sure. That happens because: $$\sum_{n\geq 0}\frac{1}{n+1}\binom{2n}{n}x^n = \frac{1-\sqrt{1-4x}}{2}. $$ Plugging in $x=\frac{1}{p}-\frac{1}{p^2}$ and simplifying you have my claim. You can find many proof of the last line here on MSE. $\endgroup$ – Jack D'Aurizio Jun 27 '15 at 9:06

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.