2
$\begingroup$

If a player plays a game until he wins twice in a row, what is the probability that he will play exactly 20 games? The probability that he will win one game is P.

I interpreted this as a sequence of 0 and 1 where 0 is loss and 1 is win. So the last two have to be 1. I assume this can then be viewed as Bernoullis problem, but I don't know how to count the remaining 18 spaces.

$\endgroup$
1
  • 1
    $\begingroup$ I think this should be solved by recursion. $\endgroup$
    – user560461
    Commented Apr 7, 2019 at 11:45

2 Answers 2

3
$\begingroup$

As you correctly assumed the 19th and 20th entries should be '1'. The previous 18 should not contain any sequence of two '1'. In other words any '1' should be followed by a '0'. This is the same as you would place '10' instead.

Let $k$ be the number of '10' pairs in the sequence, the rest $18-2k$ places being filled with '0'.

This gives for the probability in question the result: $$ \sum_{k=0}^9\binom{18-k}{k}p^k(1-p)^k(1-p)^{18-2k}p^2=\sum_{k=0}^9\binom{18-k}{k}p^{k+2}(1-p)^{18-k}, $$ where $\binom{18-k}{k}$ is the overall number of sequences with $k$ '10' pairs in the first 18 places, $p^k(1-p)^k$ is the probability to have $k$ '10' pair, $(1-p)^{18-2k}$ is the probability that the rest $18-2k$ places are filled with '0', $p^2$ is the probability that the last two places are filled with '1'.

$\endgroup$
2
$\begingroup$

Let $q_{n, 0}$ be probability of not having two wins in row on the first $n$ games and losing $n$-th game, and $q_{n, 1}$ the same but winning the $n$-th, and define $q_{0, 0} = 1$, $q_{0, 1} = 0$ (we can assume we lost the game before first).

Then we have $q_{n, 0} = (1 - p) \cdot (q_{n - 1, 0} + q_{n - 1, 1})$ and $q_{n, 1} = p \cdot q_{n - 1, 0}$. Now it's standard linear recurrence problem, which can be reduced to single variable, for example $q_{n, 0} = (1 - p) q_{n - 1, 0} + p (1 - p) q_{n - 2, 0}$, and then solving this recurrence using characteristic polynomial (it's some very boring arithmetic).

Or, if you are writing a program, just compute corresponding power of matrix $$\left(\begin{array}{l}1 - p & 1 - p\\1 &0\end{array}\right)$$ (that transforms $(q_{n - 1, 0}, q_{n - 1, 1})$ to $(q_{n, 0}, q_{n, 1})$) and multiply it by vector $(1, 0)$.

$\endgroup$
2
  • 1
    $\begingroup$ Isn't $q_{n,1} = p \cdot q_{n-1,0}$? For otherwise we would have two consecutive wins. OP actually needs to find out $q_{18,0}.$ $\endgroup$
    – little o
    Commented Apr 7, 2019 at 13:27
  • $\begingroup$ It is, thanks! (the later part used correct equality) $\endgroup$
    – mihaild
    Commented Apr 7, 2019 at 13:29

You must log in to answer this question.

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