5
$\begingroup$

The coin is tossed until the number of heads is exactly equal to twice the number of tails. The coin lands on heads with probability 𝑝. What is the probability that a coin will be tossed forever? A similar problem (A coin lands heads with probability 𝑝. The coin is tossed until the first heads will come up. What is the probability that an even number of tosses will be made?) was solved by reducing the result to an infinite sum, which was an infinite sum of a geometric progression: $$(1-p)*p + (1-p)^3*p +\ldots = (1-p)*p*(1+(1-p)^2+(1-p)^4 + \ldots) = (1-p)*p/(1-(1-p)^2)=(1-p)/(2-p)$$ I assume, if I’m not mistaken, that there should be a similar approach here, but I’m a little confused about how exactly this should be decided: I first thought to subtract from 1 the probability of events when the coin toss stops, that is, when the number of heads becomes equal to twice the number of tails (when you get 1 tail and 2 heads, 2 tails and 4 heads, and so on), but the problem is that there are several sequences in which, for example, 2 tails and 4 heads, because tails and heads can occur in different orders: $$1 - (\binom{3}{1}*(1-p)*p^2+\binom{6}{2}*(1-p)^2*p^4+\ldots)$$ I can’t apply the formula of an infinite geometric progression here and I don’t really understand how to apply the formula of a power series here, although maybe this formula is needed here. Maybe I'm deciding in the wrong way altogether? Please tell me what to do here, because unfortunately I have no more ideas...

$\endgroup$
3
  • 1
    $\begingroup$ I don't suppose you allow that you can stop after zero tosses? $\endgroup$
    – paw88789
    Feb 25 at 23:14
  • 1
    $\begingroup$ Your formula involves a lot of double counting. For eg. for the case of $4H2T$, you are considering the combinations $HHTTHH, HHTHTH, HHTHHT$, but note that in all of these, you would have stopped after the third toss. You need to condition that any proper prefix of the string of $2nH, nT$ must have: no of $H$ ≠ $2 \cdot$ no of $T$ $\endgroup$ Feb 26 at 6:50
  • $\begingroup$ You can get properly sized parentheses (and other paired delimiters) that adjust to the size of their content by preceding them with \left and \right. $\endgroup$
    – joriki
    Feb 27 at 0:45

2 Answers 2

3
$\begingroup$

As pointed out in the comment, your formula involves double counting.

Sketch:

Let $S_n$ be the number of sequences of length $3n$ having $n$ tails and $2n$ heads.

Let $T_n$ be the number of sequences with $n$ tails and $2n$ heads, such that there is no prefix of length $3m<3n$ (starting from the first element) having $m$ tails and $2m$ heads (that is, the sequence is the first one having the desired property).

Then $$S_n = T_n +T_{n-1} {3 \choose 1} +T_{n-2} {6 \choose 2} \cdots + T_1 {3(n-1) \choose n-1} ={3n \choose n}\tag1$$

And the probabilty of ending is

$$T_1 a + T_2 a^2 + T_3 a^3 +\cdots \tag 2$$

where $a = p^2 q = p^2(1-p)$

I remains to compute $T_n$ explicitly from $(1)$, plug it in $(2)$ and see if you can express it in some simple analytic form.

PS: Plugging the first terms, I found https://oeis.org/A024485 :$$T_n={3n \choose n} \frac{2}{3n−1} \tag3$$ I guess we might prove it by induction. To tackle $(2)$, perhaps this is useful.

$\endgroup$
2
  • $\begingroup$ Thank you very much! Thanks to you, most of this task is now clear! But I have one question regarding the calculations of Tn: do you mean to express Tn only through n in such a way that substituting 1, get T1 and substitute it into (2), then substitute 2, get T2 and substitute it into (2) and so on? $\endgroup$ Feb 26 at 20:52
  • $\begingroup$ @user Of course, fixed, thanks $\endgroup$
    – leonbloy
    Mar 1 at 11:35
1
$\begingroup$

Too long for comment. In the previous answer the hypothesis $$ T_k=\frac{2}{3k-1}\binom{3k}k\tag1 $$ was suggested. It was also assumed that it can be proved by induction. This is indeed the case. Assume $(1)$ is valid for all $k$: $1\le k\le n-1$. Then the expression is valid for $k=n$ as well: $$\begin{align} T_n&=\binom{3n}{n}-\sum_{k=1}^{n-1}T_k\binom{3(n-k)}{n-k}\\ &=\binom{3n}{n}-\sum_{k=1}^{n-1}\frac{2}{3k-1}\binom{3k}k\binom{3n-3k}{n-k}\tag2\\ &=\binom{3n}{n}+\frac2{3n-1}\binom{3n}n-\sum_{k=1}^{n}\frac{2}{3k-1}\binom{3k}k\binom{3n-3k}{n-k}\tag3\\ &=\frac{3n+1}{3n-1}\binom{3n}{n}-\sum_{k=1}^{n}\frac{2\cdot3}{3k-1}\binom{3k-1}{k-1}\binom{3(n-1)-3(k-1)}{(n-1)-(k-1)}\tag4\\ &=\frac{3n+1}{3n-1}\binom{3n}{n}-3\sum_{k=0}^{n-1}\frac{2}{3k +2}\binom{3k+2}{k}\binom{3n-3-3k}{n-1-k}\tag5\\ &=\frac{3n+1}{3n-1}\binom{3n}{n}-3\binom{3n-1}{n-1}\tag6\\ &=\frac{3n+1}{3n-1}\binom{3n}{n}-\binom{3n}{n}\tag7\\ &=\frac{2}{3n-1}\binom{3n}{n}\tag8. \end{align}$$

Explanations

$(2)$: induction hypothesis

$(3)$: $\pm \frac2{3n-1}\binom{3n}n$

$(4)$: $\binom{3k}k=3\binom{3k-1}{k-1}$

$(5)$: $k-1\to k$

$(6)$: particular case ($a=2,b=3,c=3n-3$) of the Rothe–Hagen identity:

$$ \sum_{k=0}^n\frac a{a+bk}\binom{a+bk}k\binom{c-bk}{n-k}=\binom{a+c}n, $$ valid for any complex numbers $a,b,c$.

$(7)$: $3\binom{3n-1}{n-1}=\binom{3n}{n}$

$(8)$: summation.


According to Mathematica the expression for the probability to finish the game in the finite number of steps take on a rather simple form: $$ P(x)=\sum_{n=1}^\infty T_n x^n=4\sin^2\left(\frac13\arcsin\sqrt{\frac{27}4x}\right), $$ where $x=p^2(1-p)$. The probability is equal to $1$ only if $p=\frac23$.

$\endgroup$

You must log in to answer this question.

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