\textbf{Problem 6}

Consider $n$ random variables $X _ { 1 } , X _ { 2 } , \cdots , X _ { n }$ that can take the values 0 and 1. Here, $n$ is an integer greater than or equal to 4. The probability of an event $A$ is denoted by $P ( A )$, and the conditional probability of the event $A$ given an event $B$ is denoted by $P ( A \mid B )$. The intersection between the event $A$ and the event $B$ is denoted by $A \wedge B$. Answer the following questions.

\textbf{I.} Let us assume that the $X _ { 1 } , X _ { 2 } , \cdots , X _ { n }$ are independent. In addition, assume that each $X _ { k } \quad ( k = 1, 2 , \cdots , n )$ takes the value 1 with the probability $p$ and the value 0 with the probability $1 - p$, i.e., $P \left( X _ { k } = 1 \right) = p$ and $P \left( X _ { k } = 0 \right) = 1 - p$.
\begin{enumerate}
  \item Find the expected value and the variance of the sum of the $X _ { 1 } , X _ { 2 } , \cdots , X _ { n }$.
  \item The random variables $X _ { 1 } , X _ { 2 } , \cdots , X _ { n }$ are arranged in the row $X _ { n } \cdots X _ { 2 } X _ { 1 }$. Let $Y$ be the integer value obtained by regarding that row as an $n$-digit binary number. For example, in the case that $n = 4$, $Y = 5$ when the row $X _ { 4 } X _ { 3 } X _ { 2 } X _ { 1 }$ is 0101, and $Y = 13$ when the row $X _ { 4 } X _ { 3 } X _ { 2 } X _ { 1 }$ is 1101. $Y$ is a random variable that takes integer values from 0 to $2 ^ { n } - 1$. Obtain the expected value and variance of $Y$.
\end{enumerate}

\textbf{II.} The values of the random variables $X _ { 1 } , X _ { 2 } , \cdots , X _ { n }$ are obtained sequentially according to the following steps. First, $X _ { 1 }$ takes the value 1 with the probability $p$ and the value 0 with the probability $1 - p$. Then, $X _ { k } \quad ( k = 2, 3 , \cdots , n )$ takes the same value as $X _ { k - 1 }$ with the probability $q$ and the value different from $X _ { k - 1 }$ with the probability $1 - q$, i.e., $P \left( X _ { k } = 1 \mid X _ { k - 1 } = 1 \right) = P \left( X _ { k } = 0 \mid X _ { k - 1 } = 0 \right) = q$ and $P \left( X _ { k } = 1 \mid X _ { k - 1 } = 0 \right) = P \left( X _ { k } = 0 \mid X _ { k - 1 } = 1 \right) = 1 - q$.
\begin{enumerate}
  \item Let $P \left( X _ { k } = 1 \right)$ be represented by $r _ { k }$, where $k$ is an integer varying from 1 to $n$. Derive a recurrence equation for $r _ { k }$. Solve this recurrence equation to express $r _ { k }$ with $p , q$, and $k$.
  \item Obtain the probability $P \left( X _ { 1 } = 1 \wedge X _ { 2 } = 0 \wedge X _ { 3 } = 1 \wedge X _ { 4 } = 0 \right)$.
  \item Obtain the probability $P \left( X _ { 3 } = 1 \mid X _ { 1 } = 0 \wedge X _ { 2 } = 1 \wedge X _ { 4 } = 1 \right)$.
\end{enumerate}