Exercise 3 (Candidates who have NOT followed the specialization course)
5 POINTS
We have a fair die with 6 faces numbered 1 to 6 and 2 coins A and B each having one heads side and one tails side. A game consists of rolling the die one or more times. After each die roll, if we get 1 or 2, then we flip coin A, if we get 3 or 4, then we flip coin B and if we get 5 or 6, then we flip neither of the two coins. At the beginning of the game, both coins are on the tails side.
- In the algorithm below, 0 codes the tails side of a coin and 1 codes the heads side. If $a$ codes the side of coin A at a given moment, then $1 - a$ codes the side of coin A after flipping it.
\begin{verbatim} Variables: a, b, d, s are integers i, n are integers greater than or equal to 1 Initialization: a takes the value 0 b takes the value 0 Input n Processing: For i going from 1 to n do d takes the value of a random integer between 1 and 6 If d <= 2 then a takes the value 1 - a else If d <= 4 | then b takes the value 1 - b EndIf EndIf s takes the value a + b EndFor Output: Display s \end{verbatim}
a. We execute this algorithm by inputting $n = 3$ and assuming that the random values generated successively for $d$ are $1; 6$ and 4. Copy and complete the table given below containing the state of the variables during the execution of the algorithm:
| variables | $i$ | $d$ | $a$ | $b$ | $s$ |
| initialization | | | | | |
| $1^{\text{st}}$ loop iteration | | | | | |
| $2^{\text{nd}}$ loop iteration | | | | | |
| $3^{\text{rd}}$ loop iteration | | | | | |
b. Does this algorithm allow us to decide whether at the end both coins are on the heads side?
2. For every natural integer $n$, we denote:
- $X_{n}$ the event: ``After $n$ die rolls, both coins are on the tails side''
- $Y_{n}$ the event: ``After $n$ die rolls, one coin is on the heads side and the other is on the tails side''
- $Z_{n}$ the event: ``After $n$ die rolls, both coins are on the heads side''.
Moreover, we denote $x_{n} = P(X_{n}); y_{n} = P(Y_{n})$ and $z_{n} = P(Z_{n})$ the respective probabilities of events $X_{n}, Y_{n}$ and $Z_{n}$. a. Give the probabilities $x_{0}, y_{0}$ and $z_{0}$ respectively that at the beginning of the game there are 0, 1 or 2 coins on the heads side. b. Justify that $P_{X_{n}}(X_{n+1}) = \frac{1}{3}$. c. Copy the tree below and complete the probabilities on its branches, some of which may be zero. d. For every natural integer $n$, express $z_{n}$ as a function of $x_{n}$ and $y_{n}$. e. Deduce that, for every natural integer $n$, $y_{n+1} = -\frac{1}{3} y_{n} + \frac{2}{3}$. f. We set, for every natural integer $n$, $b_{n} = y_{n} - \frac{1}{2}$.
Show that the sequence $(b_{n})$ is geometric. Deduce that, for every natural integer $n$, $y_{n} = \frac{1}{2} - \frac{1}{2} \times \left(-\frac{1}{3}\right)^{n}$. g. Calculate $\lim_{n \rightarrow +\infty} y_{n}$.
Interpret the result.