Yet Another Unfair Game

Relevant wiki: Conditional Probability - Problem Solving

Let $p_n$ be the probability of breaking even, given that your current indebtedness is $ $n$ . The friendly game owner allows you have indebtedness of arbitrarily large $n$ . Then $p_0 = 1$ and $p_n \; = \; \tfrac13p_{n-1} + \tfrac23p_{n+1} \qquad \qquad n \ge 1\;.$ Solving this recurrence relation by trying $p_n = \lambda^n$ we see that we need $2\lambda^2 - 3\lambda + 1 = 0$ , so that $\lambda = \tfrac12,1$ . Thus $p_n \; = \; A + B2^{-n}$ where $p_0 = A + B = 1$ . Where to go from here is not totally obvious. It may seem reasonable to assume that $p_n$ must tend to $0$ as $n \to \infty$ , giving the (correct) answer $p_n = 2^{-n}$ , but let us actually prove this.

For any $N \ge 1$ , let $p_{n,N}$ be the probability of breaking even, given that your initial indebtedness is $ $n$ , and you are never more than $ $N$ in debt. Then it is clear that $p_{n,N} \; =\; \tfrac13p_{n-1,N} + \tfrac23p_{n+1,N} \qquad \qquad 1 \le n \le N$ while $p_{0,N} = 1$ and $p_{N+1,N} = 0$ . We can solve this recurrence relation exactly, obtaining $p_{n,N} \; =\; \frac{2^{N+1} - 2^n}{2^n(2^{N+1} - 1)} \qquad \qquad 0 \le n \le N+1$ Now $\begin{array}{rcl} p_n & = & \displaystyle \mathbb{P}\big[\mathrm{Clear\, debts}\,\big|\,\mathrm{Initial\, debt\, is\, \$}n\big] \\ & =& \displaystyle \sum_{N=n}^\infty \mathbb{P}\big[\mathrm{Clear\,debts\, while\, accruing\, a\, maximum\, debt\, of\, \$}N\,\big|\,\mathrm{Initial\, debt\,is\, \$}n\big] \\ & = & \displaystyle \sum_{N=n}^\infty \left(\begin{array}{l}\mathbb{P}\big[\mathrm{Clear\, debts\, while\, accruing\, a\, maximum\, debt\, of\, at\, most\, \$}N\,\big|\,\mathrm{Initial\, debt\, is\, \$}n\big] \\ - \mathbb{P}\big[\mathrm{Clear\, debts\, while\, accruing\, a\, maximum\, debt\, of\, at\, most\, \$}(N-1)\,\big|\,\mathrm{Initial\, debt\, is\, \$}n\big]\end{array} \right) \\ & = & \displaystyle \sum_{N=n}^\infty \big(p_{n,N} - p_{n,N-1}\big) \; = \; \lim_{N \to \infty}\big(p_{n,N} - p_{n.n-1}\big) \\ & = & \displaystyle 2^{-n} \end{array}$ The probability we want is $P = p_2 = \tfrac14$ , and $\big\lfloor 10^{10}e^P + 0.5\big\rfloor \,=\, \boxed{12840254167}$ .

In every round, the probability of earning one dollar is $\frac{2}{6} = \frac{1}{3}$ , and the probability of losing one dollar is $\frac{4}{6} = \frac{2}{3}$ . As you arleady lost $2$ dollars, your profit is $-2$ dollars. You want to recover your money, that is, you want a profit of $0$ dollars. As the owner accepted to lend you as much money as you want, your profit can be arbitrarily low, and the game can go on indefinitely. This fact is unchanged by your actual profit, and for this reason, the probability $P_1$ of increasing your actual profit by $1$ dollar is independent of your actual profit. Suppose your actual profit is $p$ dollars, and you want to achieve a profit of $p+1$ dollars. There are two ways for this to happen: either you win the first round, or you lose the first round and then you increase your profit by $1$ dollar twice. Therefore, $P_1$ can be defined recursively as: $P_1 = \frac{1}{3} + \frac{2}{3}P_1 P_1 \\ 0 = 2P_1 ^2 - 3P_1 + 1 \\ 0 = \left( {2P_1 - 1} \right)\left( {P_1 - 1} \right) \\ P_1 = 1 \vee P_1 = \frac{1}{2}$ It can be proved by contradiction that $P_1 = 1$ is not a valid solution. Let $Q$ be the probability of losing in the first round and then recovering your initial profit. $Q$ can be expressed as: $Q = \frac{2}{3}P_1$ Notice that all the ways of losing in the first round and then recovering your initial profit are also ways of NOT increasing your initial profit by $1$ dollar, whose probability is $1-P_1$ . Therefore, the event with probability $Q$ is a sub-event of the event with probability $1-P_1$ , and thus: $Q \le 1 - P_1$ Let $P_1 = 1$ , then $Q = \frac{2}{3}$ and $\frac{2}{3} \le 0$ . This is a contradiction, so our initial assumption $P_1 = 1$ is false. Finally, the only solution left for $P_1$ is: $P_1 = \frac{1}{2}$ Your initial profit is $-2$ dollars, and you want a profit of $0$ dollars. That is equivalent to raising your profit by $1$ dollar twice, and thus the probability of achieving your goal is $P = P_1 ^2 = \frac{1}{4}$ . Then the final answer is: $\left\lfloor {10^{10} e^P + 0.5} \right\rfloor = \left\lfloor {10^{10} e^{\frac{1}{4}} + 0.5} \right\rfloor \approx \left\lfloor {{\rm 12840254167}{\rm .377414}} \right\rfloor = \boxed{12840254167}$ Another way of solving this problem is by directly calculating the probability $Q$ defined above. Remember that $Q$ is the probability of losing in the first round and then recovering your initial profit. Suppose $1$ represents a winning round and $-1$ a losing round. Then a set of rounds can be expressed as a sequence of $1$ 's and $-1$ 's. Let $S$ be the set of all the set of rounds in which you lose the first round and in the end you recover your initial profit. An element of $S$ must be of the form $\left( { - 1, \ldots ,1} \right)$ , whose sum of numbers must be zero (because in the end you recover your initial profit), so each element must have a even amount of numbers in the sequence. For a sequence in $S$ , the subsequence of each element formed with the second to the penultimate number is equivalent to a Dyck word of length $2n$ , because you only reach your initial profit in the last round. For this reason, the number of sequences of length $2n+2$ in $S$ is equal to the number of Dyck words of length $2n$ . Notice that the probability of a sequence in $S$ of length $2n+2$ happening is $\left( {\frac{2}{3}} \right)^{n + 1} \left( {\frac{1}{3}} \right)^{n + 1} = \left( {\frac{2}{9}} \right)^{n + 1}$ because the number of losing rounds is the same as the number of winning rounds. Finally, $Q$ can be calculated as: $Q = \sum\limits_{n = 0}^\infty {\left( {number~of~Dyck~words~of~length~2n} \right)\left( {\frac{2}{9}} \right)^{n + 1} }$ The number of Dyck words of length $2n$ corresponds to the Catalan number $n$ , $C_n$ . Now $Q$ can be expressed as: $Q = \frac{2}{9}\sum\limits_{n = 0}^\infty {C_n \left( {\frac{2}{9}} \right)^n }$ The generating function for the Catalan numbers is $c\left( x \right) = \sum\limits_{n = 0}^\infty {C_n x^n }$ which converges to $\frac{{1 - \sqrt {1 - 4x} }}{{2x}}$ for $\left| x \right| < \frac{1}{4}$ , as proven here . Therefore, $Q$ can be calculated as: $Q = \frac{2}{9}c\left( {\frac{2}{9}} \right) = \frac{1}{3}$ Remember that, as explained in the first solution, $Q = \frac{2}{3}P_1$ , where $P_1$ is the probability of increasing your initial profit by $1$ dollar. Then $P_1=\frac{1}{2}$ and: $P = P_1 ^2 = \frac{1}{4}$ The rest of the problem follows.