Events and Probability Spaces · Recursive Probability Computation (Optional)

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

Below, we will find the probability that the player wins, that is, increases the capital to \(t\). In the case of a symmetrical game (\(p=\frac{1}{2}\)), this probability, as we will see, is equal to \(\frac{n}{t}\). Intuitively, this seems natural: the higher the initial capital, the higher the chances of winning (and the chances grow proportionally). For example, with initial capital \(n=100\), the player will reach capital \(t=200\) with probability \(\frac{1}{2}\). And from \(n=500\) to \(t=600\), they will reach it with probability \(\frac{5}{6}\). It is unusual that the same target profit \((t-n)=100\) is obtained in the second case with a much higher probability. This happens because the player risks losing a larger amount.

Theorem. Let \(0<n<t\) be integers and \(0<p\le 1\). A player with initial capital \(n\) and target capital \(t\) makes a series of bets, each of which wins with probability \(p\). \[\Pr[\text{player wins}]= \begin{cases}\frac{n}{t}, & \text{if \(p=0.5\),}\\ \frac{r^{n}-1}{r^{t}-1} & \text{otherwise, where \(r=(1-p)/p\).}\end{cases}\]

Proof. Let \(A_{n}\) denote the event “with capital \(n\), the player will win”. It is easy to see that the values \(\Pr[A_{n}]\) satisfy the following recurrence relation: \[\Pr[A_{n}]=p \cdot \Pr[A_{n+1}]+q\cdot \Pr[A_{n-1}] \ .\] Indeed, from the point \(n\), with probability \(p\), we move to point \(n+1\), and with probability \(q\), we move to point \(n-1\). After that, the same game continues, and we need to calculate the same probability of winning, that is, reaching the target capital \(t\). (We use the law of total probability here, which we will consider shortly.) For this recurrence relation, the following boundary conditions hold: \[\Pr[A_{0}]=0, \ \Pr[A_{t}]=1.\]

For the curious 🤓

This recurrence relation can be solved using standard methods. To do this, we rewrite the relation as \[\Pr[A_{n+1}]=\frac{1}{p}\Pr[A_{n}]-\frac{q}{p}\Pr[A_{n-1}].\] Its characteristic polynomial is \[x^{2}-x/p+q/p=(x-1)(x-r).\] If \(r=1\) (i.e., the characteristic polynomial has a repeated root), the general solution will be \(c_{1}1^{n}+c_{2}n1^{n}=c_{1}+c_{2}n\). If \(r \neq 1\), the general solution will be \(c_{1}1^{n}+c_{2}r^{n}=c_{1}+c_{2}r^{n}\). The constants \(c_{1}\) and \(c_{2}\) are determined from the boundary conditions. Below, we will derive the formulas directly.

To solve this recurrence relation, we use the fact that \(p+q=1\) and replace \(\Pr[A_{n}]\) in the relation with \((p+q)\Pr[A_{n}]\): \[p\cdot \Pr[A_{n}]+q\cdot \Pr[A_{n}]=p \cdot \Pr[A_{n+1}]+q\cdot \Pr[A_{n-1}].\] Then \[q(\Pr[A_{n}]-\Pr[A_{n-1}])=p(\Pr[A_{n+1}]-\Pr[A_{n}]) \ .\] We see that the neighboring differences of the form \(\Pr[A_{i}]-\Pr[A_{i-1}]\) differ by \(r=q/p\). Let \(\delta_{n}=\Pr[A_{n}]-\Pr[A_{n-1}]\). Then \[\delta_{n+1}=r\delta_{n}=r^{2}\delta_{n-1}=\dotsb=r^{n}\delta_{1} \ .\] Thus, \[\Pr[A_{n}]=\sum_{i=1}^{n}(\Pr[A_{i}]-\Pr[A_{i-1}])+\Pr[A_{0}]=\sum_{i=1}^{n}\delta_{i}=\delta_{1}\sum_{i=1}^{n}r^{i-1}\ .\]

Now, let's consider two cases.

\(r=1\) (i.e., \(p=q=\frac{1}{2}\)). Then \(\Pr[A_{n}]=n\delta_{1}\). When \(n=t\), we get \(1=t\delta_{1}\), so \(\delta_{1}=1/t\). Thus, \(\Pr[A_{n}]=n/t\).

\(r \neq 1\). Then \[\Pr[A_{n}]=\delta_{1}\sum_{i=0}^{n-1}r^{i}=\delta_{1}\frac{r^n-1}{r-1}\ .\] When \(n=t\), we get \(1=\delta_{1}\frac{r^t-1}{r-1}\), so \(\delta_{1}=\frac{r-1}{r^t-1}\). Thus, \[\Pr[A_{n}]=\frac{r-1}{r^t-1}\cdot \frac{r^n-1}{r-1}=\frac{r^{n}-1}{r^{t}-1}.\]

◼