\section*{Problem 6}
Consider the following procedure that generates a sequence of random variables that take the value 0 or 1. For an integer $n \geq 1$, we denote the $n$-th random variable of a sequence generated by the procedure as $X _ { n }$.

\begin{itemize}
  \item $X _ { 1 }$ becomes $X _ { 1 } = 0$ with a probability $\frac { 2 } { 3 }$ and $X _ { 1 } = 1$ with a probability $\frac { 1 } { 3 }$.
  \item For an integer $n = 1,2 , \ldots$ in order, the following is repeated until the procedure terminates:
  \item The procedure terminates with a probability $p ( 0 < p < 1 )$ if $X _ { n } = 0$ and with a probability $q ( 0 < q < 1 )$ if $X _ { n } = 1$. Here, $p$ and $q$ are constants.
  \item If the procedure does not terminate as above, $X _ { n + 1 }$ becomes $X _ { n + 1 } = 0$ with a probability $\frac { 2 } { 3 }$ and becomes $X _ { n + 1 } = 1$ with a probability $\frac { 1 } { 3 }$.
\end{itemize}

When the procedure terminates at $n = \ell$, a sequence of length $\ell$, composed of random variables $\left( X _ { 1 } , \ldots , X _ { \ell } \right)$, is generated, and no further random variables are generated. Answer the following questions.

I. For an integer $k \geq 1$, consider the following matrix:

$$\boldsymbol { P } _ { k } = \left( \begin{array} { c c } 
\operatorname { Pr } \left( X _ { n + k } = 0 \mid X _ { n } = 0 \right) & \operatorname { Pr } \left( X _ { n + k } = 1 \mid X _ { n } = 0 \right) \\
\operatorname { Pr } \left( X _ { n + k } = 0 \mid X _ { n } = 1 \right) & \operatorname { Pr } \left( X _ { n + k } = 1 \mid X _ { n } = 1 \right)
\end{array} \right)$$

Here, $\operatorname { Pr } ( A \mid B )$ is the conditional probability of an event $A$ given that an event $B$ has occurred.

\begin{enumerate}
  \item Express $\boldsymbol { P } _ { 1 }$ and $\boldsymbol { P } _ { 2 }$ using $p$ and $q$.
  \item Express $\boldsymbol { P } _ { 3 }$ using $\boldsymbol { P } _ { 1 }$.
  \item $\boldsymbol { P } _ { k }$ can be expressed as $\boldsymbol { P } _ { k } = \gamma _ { k } \boldsymbol { P } _ { 1 }$ using a real number $\gamma _ { k }$. Find $\gamma _ { k }$.
\end{enumerate}

II. For an integer $m \geq 2$, find the respective probabilities that $X _ { m } = 0$ and $X _ { m } = 1$, given that the procedure does not terminate before $n = m$.

III. Find the expected value and the variance of the length of the sequence, $\ell$, generated by the procedure. If necessary, you may use $\sum _ { m = 1 } ^ { \infty } m r ^ { m - 1 } = \frac { 1 } { ( 1 - r ) ^ { 2 } }$ and $\sum _ { m = 1 } ^ { \infty } m ^ { 2 } r ^ { m - 1 } = \frac { 1 + r } { ( 1 - r ) ^ { 3 } }$ for a real number $r$ whose absolute value is smaller than 1.

IV. For an integer $k \geq 1$, find the probability $\operatorname { Pr } \left( X _ { n } = 0 \mid X _ { n + k } = 1 \right)$.