A certain online game offers a ``ten-draw'' card-pulling mechanism. ``Ten-draw'' means the system automatically performs ten card-pulling actions. If each ``ten-draw'' requires 1500 tokens, the probability of drawing a gold card is 2\% for the first nine draws and 10\% for the tenth draw. A certain student has 23000 tokens and continuously uses ``ten-draw'' until unable to draw anymore. The expected value of the number of gold cards drawn is (13-1)(13-2) cards.

There is a circular clock with numbers $1, 2 , \ldots , 12$ marked in clockwise order (as shown in the figure). Initially, a game piece is placed at the ``12'' o'clock position on this clock. Then, each time a fair coin is tossed, the game piece is moved according to the following rules:

• If heads appears, move the game piece 5 clock positions clockwise from its current position.
• If tails appears, move the game piece 5 clock positions counterclockwise from its current position.

For example: If the coin is tossed three times and all are heads, the game piece moves to the ``5'' o'clock position on the first move, the ``10'' o'clock position on the second move, and the ``3'' o'clock position on the third move.
For any positive integer $n$, let the random variable $X _ { n }$ represent the clock position of the game piece after $n$ moves according to the above rules, $P \left( X _ { n } = k \right)$ represents the probability that $X _ { n } = k$ (where $k = 1, 2 , \ldots , 12$), and let $E \left( X _ { n } \right)$ represent the expected value of $X _ { n }$. Select the correct options.
(1) $E \left( X _ { 1 } \right) = 6$
(2) $P \left( X _ { 2 } = 12 \right) = \frac { 1 } { 4 }$
(3) $P \left( X _ { 8 } = 5 \right) \geq \frac { 1 } { 2 ^ { 8 } }$
(4) $P \left( X _ { 8 } = 4 \right) = P \left( X _ { 8 } = 8 \right)$
(5) $E \left( X _ { 8 } \right) \leq 7$

A lottery game has a single-play winning probability of 0.1, and each play is an independent event. For each positive integer $n$, let $p_{n}$ be the probability of winning at least once in $n$ plays of this game. Select the correct options.
(1) $p_{n+1} > p_{n}$
(2) $p_{3} = 0.3$
(3) $\langle p_{n} \rangle$ is an arithmetic sequence
(4) Playing this game two or more times, the probability of not winning on the first play and winning on the second play equals $p_{2} - p_{1}$
(5) When playing this game $n$ times with $n \geq 2$, the probability of winning at least 2 times equals $2p_{n}$

A game company will hold a lottery activity. The company announces that each lottery draw requires using one token, and the winning probability for each draw is $\frac{1}{10}$. A certain person decides to save a certain number of tokens and start drawing after the activity begins, stopping only when all tokens are used. Select the correct options.
(1) The expected value of the number of draws needed for the person to win once is 10
(2) The probability that the person wins at least once in two draws is 0.2
(3) The probability that the person does not win in 10 draws is less than the probability of winning in 1 draw
(4) The person must save at least 22 tokens to guarantee a winning probability greater than 0.9
(5) If the person saves sufficiently many tokens, the winning probability can be guaranteed to be 1

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.
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$.

1. Find the expected value and the variance of the sum of the $X _ { 1 } , X _ { 2 } , \cdots , X _ { n }$.
2. 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$.

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$.

1. 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$.
2. Obtain the probability $P \left( X _ { 1 } = 1 \wedge X _ { 2 } = 0 \wedge X _ { 3 } = 1 \wedge X _ { 4 } = 0 \right)$.
3. Obtain the probability $P \left( X _ { 3 } = 1 \mid X _ { 1 } = 0 \wedge X _ { 2 } = 1 \wedge X _ { 4 } = 1 \right)$.

Consider a game where points are awarded in $n$ independent trials. In each trial, either $+1$ or $-1$ is awarded and both outcomes have the same probability of $1/2$. Let $X _ { k }$ be the point awarded in the $k ^ { \text {th } }$ trial $( 1 \leq k \leq n )$, and $S _ { k } = \sum _ { i = 1 } ^ { k } X _ { i }$. In the following questions, $n$ is an even integer such that $n \geq 4$, and $t$ is an even integer such that $2 \leq t \leq n$.
I. Obtain the probability for $S _ { 4 } = 0$.
II. Let $P _ { n } ( t )$ be the probability for $S _ { n } = t$. Find $P _ { n } ( t )$.
III. Let $P _ { n } ^ { + } ( t )$ be the probability for $S _ { 1 } = 1$ and $S _ { n } = t$. Find $P _ { n } ^ { + } ( t )$.
IV. Let $P _ { n } ^ { - } ( t )$ be the probability for $S _ { 1 } = - 1$ and $S _ { n } = t$. Find $P _ { n } ^ { - } ( t )$.
V. Let $Q _ { n } ( t )$ be the probability that all of the variables $\left\{ S _ { j } \right\}$ $( j = 1,2 , \cdots , n - 1 )$ are greater than zero and $S _ { n } = t$. Express $Q _ { n } ( t )$ with $P _ { n } ^ { + } ( t )$ and $P _ { n } ^ { - } ( t )$. Then, express $Q _ { n } ( t )$ with $P _ { n } ( t )$.
VI. Obtain the probability that all of the variables $\left\{ S _ { j } \right\} ( j = 1,2 , \cdots , n )$ are greater than zero.

Consider a discrete-time system where stochastic transitions between the two states (A and B) occur as shown in Figure 2.1. The transition probability in unit time from the state A to B is $\alpha$ and from the state B to A is $\beta$. Note that $0 < \alpha < 1$ and $0 < \beta < 1$. Variables $n$ and $k$ represent discrete time and are integers greater than or equal to 0.
Answer the following questions.

1. Let $P_{\mathrm{A}}(n)$ be the probability that the state is A at time $n$ and $P_{\mathrm{B}}(n)$ be the probability that the state is B at time $n$. Let $\boldsymbol{P}(n) = \binom{P_{\mathrm{A}}(n)}{P_{\mathrm{B}}(n)}$. Express matrix $\boldsymbol{M}$ using $\alpha$ and $\beta$, assuming $\boldsymbol{P}(n+1) = \boldsymbol{M}\boldsymbol{P}(n)$.
2. Obtain all eigenvalues and the corresponding eigenvectors of matrix $\boldsymbol{M}$.
3. As time tends towards infinity, the probability that the state is A and the probability that the state is B converge towards constant values. Obtain each value.
4. Assume $R_{\mathrm{A}}(n) = P_{\mathrm{A}}(n) - \lim_{k \rightarrow \infty} P_{\mathrm{A}}(k)$. Express $R_{\mathrm{A}}(n+1)$ by using $R_{\mathrm{A}}(n)$.

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 }$.

• $X _ { 1 }$ becomes $X _ { 1 } = 0$ with a probability $\frac { 2 } { 3 }$ and $X _ { 1 } = 1$ with a probability $\frac { 1 } { 3 }$.
• For an integer $n = 1,2 , \ldots$ in order, the following is repeated until the procedure terminates:
• 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.
• 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 }$.

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.

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

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)$.