Example 1: The Frog Walk

Imagine 20 lily pads arranged in a circle. Suppose a frog starts at pad 20. Each second, it either stays where it is, or jumps one pad in the clockwise direction, or jumps one pad in the counter-clockwise direction, each with probability 1/3. (See Figure 1).

Figure 1

Exercise 1 (20pts). For the Frog Walk, compute P(at pad #1 after 2 steps).

Solution

\[ P(\mbox{at pad 1 after two steps})=\frac{1}{3}\cdot \frac{1}{3}+\frac{1}{3}\cdot \frac{1}{3}=\frac{2}{9}. \]

Example 2: Simple finite Markiv chain}

Let \(S=\{1,2,3\}\), and \(\nu=(1/7, 2/7, 4/7)\), and (see Figure 2) \[ (p_{ij})= \left( \begin{array}{lll} p_{11} & p_{12} & p_{13} \\ p_{21} & p_{22} & p_{23} \\ p_{31} & p_{32} & p_{33} \end{array} \right) = \left( \begin{array}{lll} 0 & 1/2 & 1/2 \\ 1/3 & 1/3 & 1/3 \\ 1/4 & 1/4 & 1/2 \end{array} \right) \]

Figure 2

Exercise 2 (25pts). For the above example:

  1. Compute \(P(X_0=1, X_1=2)\).

  2. Compute \(P(X_0=1, X_1=1, X_2=1)\).

  3. Compute \(P(X_0=1, X_1=1, X_2=1, X_3=2)\).

Solution \[ (a)\ P(X_0=1, X_1=2)=\nu_1p_{12}=\frac{1}{7}\cdot \frac{1}{2}=\frac{1}{14}. \] \[ (b)\ P(X_0=1, X_1=1,X_2=1)=\nu_1p_{11}p_{11}=\frac{1}{7}\cdot 0\cdot 0=0.\\ \] \[ (c)\ P(X_0=1, X_1=1,X_2=1,X_3=2)=\nu_1p_{11}p_{11}p_{12}=\frac{1}{7}\cdot 0\cdot 0\cdot \frac{1}{2}=0. \]

Example 3: Simple Random Walk (s.r.w.)}

Let \(0<p<1\), (e.g., \(p=1/2\)). Suppose you repeatedly bet $1. Each time you have probability \(p\) of winning $1, and probability \(1-p\) of loosing $1. Let \(X_n\) be the net gain (in dollars) after \(n\) bets. Then \(\{X_n\}\) is a Markov chain, with \(S={\bf Z}\), and (see Figure 3) \[ p_{ij}= \left\{ \begin{array}{ll} p, & j=i+1\\ 1-p, & j=i-1 \\ 0, & \mbox{otherwise}. \end{array} \right. \]

Figure 3

Usually we take the initial value \(X_0=0\), so \(\nu_0=1\), but sometimes we instead take \(X_0=a\) for some other \(a\in {\bf Z}\), so \(\nu_a=1\).

Exercise 3 (25pts). For the s.r.w. with \(p=2/3\) and \(X_0=0\) with probability 1:

  1. Compute \(P(X_0=0, X_1=1)\).

  2. Compute \(P(X_0=0, X_1=1, X_2=0)\).

  3. Compute \(P(X_0=0, X_2=2\)).

Solution

\[ (a)\ P(X_0=0, X_1=1)=\frac{2}{3}. \] \[ (b)\ P(X_0=0, X_1=1, X_2=0)=\frac{2}{3}\cdot \frac{1}{3}=\frac{2}{9}. \] \[ (c)\ P(X_0=0, X_2=2)=\frac{2}{3}\cdot \frac{2}{3}=\frac{4}{9}. \]

Exercise 4(30pts) Consider a branching process with initial value \(X_0=1\), and offspring distribution \[ p_0=\frac{4}{7}, \qquad p_1=\frac{2}{7}, \qquad p_{2}=\frac{1}{7}. \] Calculate

  1. \(P(X_1=0)\).

  2. \(P(X_1=2)\).

  3. \(P(X_2=2)\).

Solution

\[ (a)\ P(X_1=0)=p_0=\frac{4}{7}. \] \[ (b)\ P(X_1=2)=p_2=\frac{1}{7}. \] (c) Here \(X_2=2\) if we have either: (i) the first individual has 1 offspring who then has 2 offspring; or (ii) the first individual has 2 offspring who then have 1 offspring each; or (iii) the first individual has 2 offspring who then have 0 and 2 offspring respectively, in either order. Therefore, \[ (c)\ P(X_2=2)=p_1P_2+p_2p_1p_1+p_2p_0p_2+p_2p_2p_0=\frac{2}{7}\cdot\frac{1}{7}+\frac{1}{7}\cdot \frac{2}{7}\cdot \frac{2}{7}+\frac{1}{7}\cdot\frac{4}{7}\cdot\frac{1}{7}+\frac{1}{7}\cdot\frac{1}{7}\cdot\frac{4}{7}=\frac{26}{343}. \]