Projects

Honors Project

I have worked with Gambler’s Ruin problem in Fall 2016 as part of my Probability & Statistics Honors project. I have solved the problem using Markov’s Chain.

Gambler’s Ruin Problem

Let N ≥ 2 be an integer and let 1 ≤ i ≤ N – 1. Consider a gambler who starts with an initial fortune of $i and then on each successive gamble either wins $1 or loses $1 independent of the past with probabilities p and q = 1 – p respectively. Let Xn denote the total fortune after the nth gamble. The gambler’s objective is to reach a total fortune of $N, without first getting ruined (running out of money). If the gambler succeeds, then the gambler is said to win the game. In any case, the gambler stops playing after winning or getting ruined, whichever happens first {Xn} yields a Markov chain (MC) on the state space S = {0, 1, · · · , N}.

The transition probabilities are given by $P_{i,i+1} = p$ , $P_{i,i-1} = q$ , 0 ≤ i ≤ N, and both 0 and N are absorbing states, $P_{00} = P_{NN}$ = 1. For example, when N = 4 the transition matrix is given by,

While the game proceeds, this MC forms a simple random walk, $X_{n} = i + \Delta_{1} + \cdots + \Delta_{n}, n \geq 1; X_{0} = i$ ; where $\{\Delta_{n}\}$ forms an i.i.d. sequence of r.v.s. distributed as, P( $\Delta$ = 1) = p, P( $\Delta$ = -1) = q = 1 – p, and represents the earnings on the successive gambles. Since the game stops when either $X_{n} = 0$ or $X_{n}$ = N, let $\tau_{i} = min\{n \geq 0 : X_{n} \in \{0,N\}|X_{0} = i\}$ , denote the time at which the game stops when $X_{0} = i$ . If $X_{\tau i}$ = N, then the gambler wins, if $X_{\tau i}$ = 0, then the gambler is ruined.

Let $P_i(N) = P(X_{\tau i} = N)$ denote the probability that the gambler wins when $X_{0} = i$ . $P_i(N)$ denotes the probability that the gambler, starting initially with $i, reaches a total fortune of N before ruin; 1 – $P_i(N)$ is thus the corresponding probability of ruin. Clearly $P_0(N) = 0$ and $P_N(N)$ = 1 by definition, and we next proceed to compute $P_i(N); 1 \leq i \leq N - 1.$ Let $P_i = P_i(N)$ , that is, we suppress the dependence on N for ease of notation. The key idea is to condition on the outcome of the first gamble, $\Delta_{1}$ = 1 or $\Delta_{1}$ = -1, yielding

The derivation of this recursion is as follows: If $\Delta_{1}$ = 1, then the gambler’s total fortune increases to $X_{1} = i + 1$ and so, by the Markov property the gambler will now win with probability $P_{i+1}$ . Similarly, if $\Delta_{1} = -1$ , then the gambler’s fortune decreases to $X_{1} = i - 1$ and so by the Markov property the gambler will now win with probability, $P_{i-1}$ . The probabilities corresponding to the two outcomes are p and q yielding (2). Since p + q = 1, (2) can be re-written as p $P_{i} + qP_{i}$ = $pP_{i+1} + qP_{i-1}$ , yielding

In particular, $P_{2} - P_{1}$ = ( $\frac{q}{p})(P_{1} - P_{0}$ ) = ( $\frac{q}{p})P_{1}$ (since $P_{0}$ = 0), so that $P_{3} - P_{2}$ = ( $\frac{q}{p})(P_{2} - P_{1}$ ) = ( $\frac{q}{p})^{2}P_1$ , and more generally $P_{i+1} - P_{i}$ = ( $\frac{q}{p})^{i}P_{i}$ , $0 \le i \le N$ . Thus,

yielding,

(1)

(Here we are using the “geometric series” equation $\sum_{n=0}^{i}{\vphantom{\sum}}(a)^i$ = $\frac{1 - a^{i + 1}}{1 - a}$ , for any number a and any integer $i \geq1$ )

Choosing i = N – 1 and using the fact that $P_N = 1$ yields,

(2)

from which we conclude that,

(3)

thus obtaining from (3) (after algebra) the solution,

(4)

Code Magic

CodeMagic is an Android app that teaches elementary school students how to code using animation and etc. This should include Blockly to teach them Javascript and Python. Games and levels are going to be added gradually. Anyone is welcome to give new game ideas or add certain levels.

Code Magic Repository

Honors Project

Share this: