Exercise 4 — Candidates who have followed the speciality course
We have two urns $U$ and $V$ each containing two balls. Initially, urn $U$ contains two white balls and urn $V$ contains two black balls. We perform successive draws from these urns as follows: each draw consists of taking at random, simultaneously, one ball from each urn and putting it in the other urn. For any non-zero natural number $n$, we denote by $X_n$ the random variable equal to the number of white balls in urn $U$ after $n$ draws.

Exercise 4 — Candidates who have followed the specialization course
For each of the following statements, say whether it is true or false by justifying the answer. One point is awarded for each correct justified answer. An unjustified answer will not be taken into account and the absence of an answer is not penalized.

• Consider the system $\left\{ \begin{array} { l l l l } n & \equiv & 1 & { [ 5 ] } \\ n & \equiv & 3 & { [ 4 ] } \end{array} \right.$ with unknown $n$ a relative integer.

Statement 1: If $n$ is a solution of this system then $n - 11$ is divisible by 4 and by 5. Statement 2: For all relative integer $k$, the integer $11 + 20 k$ is a solution of the system. Statement 3: If a relative integer $n$ is a solution of the system then there exists a relative integer $k$ such that $n = 11 + 20 k$.

• An automaton can be in one of two states A or B. At each second it can either remain in the state it is in or change it, with probabilities given by the probabilistic graph below. For all natural number $n$, we denote $a _ { n }$ the probability that the automaton is in state A after $n$ seconds and $b _ { n }$ the probability that the automaton is in state B after $n$ seconds. Initially, the automaton is in state B.

Consider the following algorithm:

\begin{tabular}{l} Variables: Initialization:

Processing:

Output:

&

$a$ and $b$ are real numbers

$a$ takes the value 0

$b$ takes the value 1

For $k$ going from 1 to 10

$a$ takes the value $0.8 a + 0.3 b$

$b$ takes the value $1 - a$

End For

Display $a$

Display $b$

\hline \end{tabular}
Statement 4: On output, this algorithm displays the values of $a _ { 10 }$ and $b _ { 10 }$. Statement 5: After 4 seconds, the automaton has an equal chance of being in state $A$ or being in state $B$.

Exercise 4 -- 5 points -- For candidates who have not followed the specialization course

We study a model of virus propagation in a population, week after week. Each individual in the population can be:

• either susceptible to being affected by the virus (``of type S'');
• either sick (affected by the virus);
• either immunized (cannot be affected by the virus).

For any natural integer $n$, the model of virus propagation is defined by the following rules:

• Among individuals of type S in week $n$, in week $n+1$: $85\%$ remain of type S, $5\%$ become sick and $10\%$ become immunized;
• Among sick individuals in week $n$, in week $n+1$: $65\%$ remain sick, and $35\%$ are cured and become immunized.
• Any individual immunized in week $n$ remains immunized in week $n+1$.

We randomly choose an individual from the population. We consider the following events: $S_{n}$: ``the individual is of type S in week $n$''; $M_{n}$: ``the individual is sick in week $n$''; $I_{n}$: ``the individual is immunized in week $n$''. In week 0, all individuals are considered ``of type S'', so: $$P(S_{0}) = 1 ; \quad P(M_{0}) = 0 \quad \text{and} \quad P(I_{0}) = 0.$$

Part A

We study the evolution of the epidemic during weeks 1 and 2.

1. Reproduce and complete the probability tree.
2. Show that $P(I_{2}) = 0.2025$.
3. Given that an individual is immunized in week 2, what is the probability, rounded to the nearest thousandth, that he was sick in week 1?

Part B

We study the long-term evolution of the disease. For any natural integer $n$, we have: $u_{n} = P(S_{n})$, $v_{n} = P(M_{n})$ and $w_{n} = P(I_{n})$.

Throughout part III, $N$ is a fixed non-zero natural integer and $(X_n)_{n \in \mathbb{N}}$ is a sequence of random variables taking values in $\llbracket 0, N \rrbracket$, forming a homogeneous Markov chain with transition matrix $Q$ where $q_{i,j} = P(X_{n+1} = j \mid X_n = i) > 0$ for all $(i,j) \in \llbracket 0,N \rrbracket^2$. Justify that $\forall i \in \llbracket 0, N \rrbracket, \sum_{j=0}^{N} q_{i,j} = 1$.

Throughout part III, $N$ is a fixed non-zero natural integer and $(X_n)_{n \in \mathbb{N}}$ is a sequence of random variables taking values in $\llbracket 0, N \rrbracket$, forming a homogeneous Markov chain with transition matrix $Q$ where $q_{i,j} = P(X_{n+1} = j \mid X_n = i) > 0$ for all $(i,j) \in \llbracket 0,N \rrbracket^2$. We denote $\Pi_n = \begin{pmatrix} P(X_n = 0) \\ \vdots \\ P(X_n = N) \end{pmatrix} \in \mathcal{M}_{N+1,1}(\mathbb{R})$. Justify that, for all $n \in \mathbb{N}^*, \Pi_{n+1} = Q^\top \Pi_n$.

Throughout part III, $N$ is a fixed non-zero natural integer and $(X_n)_{n \in \mathbb{N}}$ is a sequence of random variables taking values in $\llbracket 0, N \rrbracket$, forming a homogeneous Markov chain with transition matrix $Q$ where $q_{i,j} = P(X_{n+1} = j \mid X_n = i) > 0$ for all $(i,j) \in \llbracket 0,N \rrbracket^2$. We have $\Pi_{n+1} = Q^\top \Pi_n$. Deduce that the distribution of $X_1$ completely determines the distributions of all random variables $X_n, n \in \mathbb{N}^*$.

We consider the graph $G$ represented in Figure 2. We denote $S _ { 1 } = \{ 1,3,6,8 \}$ and $S _ { 2 } = \{ 2,4,5,7 \}$. We assume that initially, the point is on vertex 1, so that $P ^ { ( 0 ) } = ( 1,0,0,0,0,0,0,0 )$.
Is the sequence of vectors $\left( P ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ convergent?

We consider the matrix $K \in \mathscr{M}_N(\mathbf{R})$ defined by $\forall (i,j) \in \llbracket 1;N \rrbracket^2, K[i,j] = p_{ij}$, and the random variable $Z_k$ representing the state of the system after $k$ impulses, with $Z_0$ being the certain variable with value 1. Let $n \in \mathbf{N}$. Let $j \in \llbracket 1;N \rrbracket$, show that $P(Z_n = j) = K^n[1,j]$. One may proceed by induction.

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$

Xiaoming wrote a program to move a robot on a $2 \times 2$ chessboard, as shown in the figure. Each execution, the program selects one direction from ``up, down, left, right'' with equal probability for each direction, and instructs the robot to move one square in that direction. However, if the selected direction would move the robot off the board, the robot stays in place. Each execution starts from the robot's current position with a newly selected direction by the program. Assume the robot's initial position is $A$. Let $a _ { n } , b _ { n } , c _ { n }$, and $d _ { n }$ be the probabilities that the robot is at positions $A , B , C , D$ respectively after executing the program $n$ times. Select the correct options.
(1) $b _ { 1 } = \frac { 1 } { 4 }$
(2) $b _ { 2 } = \frac { 1 } { 8 }$
(3) $a _ { 2 } + d _ { 2 } = \frac { 3 } { 4 }$

$A$	$B$
$C$	$D$

(4) $b _ { 99 } = c _ { 99 }$
(5) $a _ { 100 } + d _ { 100 } > \frac { 1 } { 2 }$

Problem 6

Consider an electric vehicle charging station with a single charger installed and let us observe the number of vehicles at the station at regular time intervals.
Arriving vehicles at the station are lined up in the queue in the order of arrival, and only the first vehicle in the queue can be charged. In the interval between one observation and the next observation, assume that one new vehicle arrives with probability $p ( 0 < p < 1 )$, and that the vehicle charging at the head of the queue completes charging with probability $q ( 0 < q < 1 )$. Here, assume that $p$ and $q$ are constants and $p + q < 1$.
The queue can accommodate $N ( N \geq 2 )$ vehicles, including the vehicle being charged at the head of the queue, and the $( N + 1 )$-th vehicle shall give up and leave the station without queuing up. The vehicle which completes charging leaves the station immediately.
In the interval between one observation and the next observation, either only one or no vehicles arrive at the station and either only one or no vehicles complete charging. Moreover, assume that both arrival of new vehicle and completion of charging for the first vehicle do not occur together in any one interval.
I. When there are $i ( 0 < i < N )$ vehicles in the queue, find the probability for the following condition: no new vehicle arrives and the first vehicle does not leave in the interval between one observation and the next observation.
Let $\pi _ { i } ( 0 \leq i \leq N )$ be the probability that $i$ vehicles are in the queue in the steady state.
II. Express the relationship between $\pi _ { i }$ and $\pi _ { i + 1 }$. Here, $i \leq N - 1$.
III. Express $\pi _ { i }$ using $p , q$ and $N$.
IV. Find the expected value of the number of vehicles at the station in the steady state using $p , q$ and $N$. Here, $p < q$.