Problem Analysis #5

Consider the following procedure that generates a sequence of random variables that take the value $0$ or $1$. For an integer $n \ge 1$, we denote the $n$-th random variable of a sequence generated by the procedure as $X_n$.

• $X_1$ becomes $X_1 = 0$ with probability $\dfrac{2}{3}$ and $X_1 = 1$ with probability $\dfrac{1}{3}$.

• For integers $n = 1,2,\ldots$ in order, the following is repeated until the procedure terminates:

• The procedure terminates with probability $p$ ($0 < p < 1$) if $X_n = 0$, and with probability $q$ ($0 < q < 1$) if $X_n = 1$. Here $p$ and $q$ are fixed constants.

• If the procedure does not terminate at step $n$, then $X_{n+1}$ becomes $0$ with probability $\dfrac{2}{3}$ and $1$ with probability $\dfrac{1}{3}$.

When the procedure terminates at $n = \ell$, a sequence of length $\ell$, composed of random variables $(X_1,\ldots, X_\ell)$, is generated, and no further random variables are generated.\subsection*{I.}For an integer $k \ge 1$, consider the matrix$P_k =\begin{pmatrix}\Pr(X_{n+k} = 0 \mid X_n = 0) & \Pr(X_{n+k} = 1 \mid X_n = 0) \\\Pr(X_{n+k} = 0 \mid X_n = 1) & \Pr(X_{n+k} = 1 \mid X_n = 1)\end{pmatrix}.$

• [(1)] Express $P_1$ and $P_2$ in terms of $p$ and $q$.

• [(2)] Express $P_3$ using $P_1$.

• [(3)] The matrix $P_k$ can be expressed in the form $P_k = \gamma_k P_1$ for a real number $\gamma_k$. Find $\gamma_k$. \subsection*{II.}For an integer $m \ge 2$, find the respective probabilities that $X_m = 0$ and $X_m = 1$, given that the procedure does not terminate before $n = m$.\subsection*{III.}Let $\ell$ be the length of the sequence generated by the procedure. Find the expected value and the variance of $\ell$. If necessary, you may use$\sum_{m=1}^{\infty} m r^{m-1} = \frac{1}{(1-r)^2},\qquad\sum_{m=1}^{\infty} m^2 r^{m-1} = \frac{1+r}{(1-r)^3}$for a real number $r$ with $|r| < 1$.\subsection*{IV.}For an integer $k \ge 1$, find the probability $\Pr(X_n = 0 \mid X_{n+k} = 1)$.\subsection*{V. Final quantity}In this part, assume $p = \dfrac{1}{2}$ and $q = \dfrac{1}{3}$.

• Let $\alpha$ be the probability in {\rm IV} for these values of $p$ and $q$: $\alpha := \Pr(X_n = 0 \mid X_{n+k} = 1).$

• Let $\beta$ be the expected value of $\ell$ obtained in {\rm III}, and let $\sigma^2$ be the variance of $\ell$ in {\rm III}.

• In {\rm I(3)}, $P_2$ can be written as $P_2 = \gamma_2 P_1$. Let $\lambda := \gamma_2$ for $p = \dfrac{1}{2}$ and $q = \dfrac{1}{3}$. Define$\mathcal{K}= 13 \cdot 320\left( \alpha \beta + \frac{\sigma^2}{\lambda} \right) + 7.$Compute the integer $\mathcal{K}$.\