Let $x = (x_0, \ldots, x_{n-1}) \in \{0,1\}^n$ and consider a noisy observation $$O(x) = \left(O_0(x), O_1(x), \ldots, O_{n-1}(x)\right)$$ of source $x$.
a. If $0 \leq j \leq k \leq n-1$, show that $\mathbb{P}\left(N \geq j \text{ and } I_j = k\right) = p\binom{k}{j}p^j(1-p)^{k-j}$.
b. Show that, for all $0 \leq j \leq n-1$, $$\mathbb{E}\left[O_j(x)\right] = p\sum_{k=j}^{n-1} x_k \binom{k}{j} p^j (1-p)^{k-j}.$$
c. Show that for all $\omega \in \mathbb{C}$, $$\mathbb{E}\left[\sum_{j=0}^{n-1} O_j(x) \omega^j\right] = p \sum_{k=0}^{n-1} x_k (p\omega + 1 - p)^k.$$

Let $(U_n)_{n \geqslant 1}$ be a sequence of mutually independent random variables following a Bernoulli distribution with parameter $1/2$. We set $$\forall n \in \mathbb{N}^{\star}, \quad Y_n = \sum_{k=1}^{n} \frac{U_k}{2^k}.$$
Justify $$\forall n \in \mathbb{N}^{\star}, \quad \mathbb{P}(Y_n \in [0,1[) = 1.$$

In the general model of a Pólya urn ($b = c = 0$, $a = d$), using the results established so far (in particular that $H = G$ on $D_{\rho}$), conclude that, for all integers $n$ and for all $k \in \llbracket 0, n \rrbracket$, $$P(X_{n} = a_{0} + ka) = \binom{n}{k} \frac{L_{k}(a_{0}/a) L_{n-k}(b_{0}/a)}{L_{n}(a_{0}/a + b_{0}/a)}$$

In the general model of a Pólya urn ($b = c = 0$, $a = d$), using the result of question 26, recover the result of question 10.

Let $Z$ be a discrete real random variable such that $\exp(\lambda Z)$ has finite expectation for all $\lambda > 0$. Show that for all $\lambda > 0$ and $t \in \mathbb{R}$, $$P[Z \geqslant t] \leqslant \exp(-\lambda t) E[\exp(\lambda Z)].$$

Let $n \geqslant 1$ be a natural integer, and let $(X_1, \ldots, X_n)$ be discrete real random variables that are mutually independent such that, for all $k \in \{1, \ldots, n\}$, $$P[X_k = 1] = P[X_k = -1] = \frac{1}{2}$$ We define $$S_n = \frac{1}{n} \sum_{k=1}^{n} X_k$$ Show that $P[S_n \geqslant 0] \geqslant \frac{1}{2}$.

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

We fix a real random variable $X : \Omega \rightarrow \mathbb { R }$, whose image $X ( \Omega )$ is a countable set, with $X ( \Omega ) = \left\{ x _ { n } , n \in \mathbb { N } \right\}$ and $a _ { n } = \mathbb { P } \left( X = x _ { n } \right)$. Let $k \in \mathbb { N } ^ { * }$. We assume that $X$ admits a moment of order $k$. Let $j$ be an integer such that $1 \leqslant j \leqslant k$. Show that for all real $x , | x | ^ { j } \leqslant 1 + | x | ^ { k }$ and deduce that $X$ admits a moment of order $j$.

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

Throughout part III, $N$ is a fixed non-zero natural integer and $(X_n)_{n \in \mathbb{N}}$ is a homogeneous Markov chain on $\llbracket 0, N \rrbracket$ with transition matrix $Q$ where $q_{i,j} = P(X_{n+1} = j \mid X_n = i) > 0$. We define $a_{i,j}(t) = q_{i,j} \mathrm{e}^{jt}$ and $A(t) = \left(a_{i,j}(t)\right)_{0 \leqslant i,j \leqslant N} \in \mathcal{M}_{N+1}(\mathbb{R})$. Justify that $A(t)$ possesses a dominant eigenvalue $\gamma(t) > 0$.

Throughout part III, $N$ is a fixed non-zero natural integer and $(X_n)_{n \in \mathbb{N}}$ is a homogeneous Markov chain on $\llbracket 0, N \rrbracket$ with transition matrix $Q$ where $q_{i,j} = P(X_{n+1} = j \mid X_n = i) > 0$. We define $a_{i,j}(t) = q_{i,j} \mathrm{e}^{jt}$, $A(t) = \left(a_{i,j}(t)\right)_{0 \leqslant i,j \leqslant N}$, $z_j(t) = P(X_1 = j)\mathrm{e}^{jt}$, $Z(t) = \begin{pmatrix} z_0(t) \\ \vdots \\ z_N(t) \end{pmatrix}$, and $Y^{(n)}(t) = (A(t))^{n-1} Z(t)$ so that $E\left(\mathrm{e}^{tS_n}\right) = \sum_{j=0}^N Y_j^{(n)}(t)$. Let $\gamma(t)$ be the dominant eigenvalue of $A(t)$. Show that $\lim_{n \rightarrow +\infty} \frac{\ln\left(E\left(\mathrm{e}^{tS_n}\right)\right)}{n} = \lambda(t)$ where $\lambda(t) = \ln(\gamma(t))$.

What is the distribution of $Y _ { n }$ ? Deduce the expectation and variance of $Y _ { n }$.

Let $E$ be an infinite countable subset of $\mathbb{R}$. Let $(\Omega, \mathscr{A}, P)$ be a probability space. Let $X$ be a random variable defined on $(\Omega, \mathscr{A}, P)$ and taking values in $E$. We call the law of the variable $X$ and we denote $\mu_X$ the application where $\{X \in A\} = \{\omega \in \Omega \text{ such that } X(\omega) \in A\}$. Verify that $\mu_X$ is a probability on $E$.

Let $E$ be an infinite countable subset of $\mathbb{R}$. Let $(\Omega, \mathscr{A}, P)$ be a probability space. Let $\mathscr{B}(\mathscr{P}(E), \mathbb{R})$ be the $\mathbb{R}$-vector space of bounded functions from $\mathscr{P}(E)$ to $\mathbb{R}$ with norm $\|f\| = \sup\{|f(A)|, \; A \in \mathscr{P}(E)\}$. Show that for all random variables $X$ and $Y$ on $(\Omega, \mathscr{A}, \mathbf{P})$ and for all subset $A$ of $E$: $$\left|\mu_X(A) - \mu_Y(A)\right| \leqslant \mathbf{E}\left(\left|\mathbf{1}_{\{X \in A\}} - \mathbf{1}_{\{Y \in A\}}\right|\right)$$ and deduce that $\left\|\mu_X - \mu_Y\right\| \leqslant \mathbf{P}(X \neq Y)$, where $\{X \neq Y\} = \{\omega \in \Omega \text{ such that } X(\omega) \neq Y(\omega)\}$.

Let $E$ be an infinite countable subset of $\mathbb{R}$. Let $(\Omega, \mathscr{A}, P)$ be a probability space. Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of random variables defined on $(\Omega, \mathscr{A}, P)$, taking values in $E$, such that for all $\omega \in \Omega$, the sequence $(X_n(\omega))_{n \in \mathbb{N}}$ is stationary and converges to $X(\omega)$. We define the random variable: $$L : \Omega \longrightarrow \mathbb{N}, \quad \omega \longmapsto \begin{cases} 0 & \text{if } \forall n \in \mathbb{N}, X_n(\omega) = X(\omega) \\ \max\{n \in \mathbb{N}, X_n(\omega) \neq X(\omega)\} & \text{otherwise.} \end{cases}$$ Justify that the application $L$ is well defined.

Let $E$ be an infinite countable subset of $\mathbb{R}$. Let $(\Omega, \mathscr{A}, P)$ be a probability space. Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of random variables defined on $(\Omega, \mathscr{A}, P)$, taking values in $E$, such that for all $\omega \in \Omega$, the sequence $(X_n(\omega))_{n \in \mathbb{N}}$ is stationary and converges to $X(\omega)$. Let $L$ be the random variable defined in 15a. Show that $\mathbf{P}(X_n \neq X) \leqslant \mathbf{P}(L \geqslant n)$ for all integer $n$ in $\mathbb{N}$.

Let $E$ be an infinite countable subset of $\mathbb{R}$. Let $(\Omega, \mathscr{A}, P)$ be a probability space. Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of random variables defined on $(\Omega, \mathscr{A}, P)$, taking values in $E$, such that for all $\omega \in \Omega$, the sequence $(X_n(\omega))_{n \in \mathbb{N}}$ is stationary and converges to $X(\omega)$. Let $\mathscr{B}(\mathscr{P}(E), \mathbb{R})$ be the $\mathbb{R}$-vector space of bounded functions from $\mathscr{P}(E)$ to $\mathbb{R}$ with norm $\|f\| = \sup\{|f(A)|, \; A \in \mathscr{P}(E)\}$. Using the results of 14 and 15b, deduce that $\lim_{n \rightarrow +\infty} \left\|\mu_{X_n} - \mu_X\right\| = 0$.

If $N \in \mathbb{N}^*$ and $p$ is a prime number, we denote $\nu_p(N)$ the $p$-adic valuation of $N$. For $n \in \mathbb{N}^*$, we define the application $$\psi_n : \mathbb{N}^* \longrightarrow \mathbb{N}^*, \quad x \longmapsto \prod_{i=1}^{n} p_i^{\nu_{p_i}(x)}$$ where $(p_i)_{i \in \mathbb{N}^*}$ is the sequence of prime numbers, ordered in increasing order. Let $X$ be a random variable defined on $(\Omega, \mathscr{A}, P)$ and taking values in $\mathbb{N}^*$. Show that $$\forall x \in \mathbb{N}^*, \quad \mathbf{P}(X = x) = \lim_{n \rightarrow +\infty} \mathbf{P}(\psi_n(X) = x)$$

If $X$ follows the distribution $\mathcal { R }$ (where $X ( \Omega ) = \{ - 1,1 \}$, $\mathbb { P } ( X = - 1 ) = \mathbb { P } ( X = 1 ) = \frac { 1 } { 2 }$), specify the distribution of the random variable $\frac { 1 } { 2 } ( X + 1 )$.

Let $(a_n)_{n \in \mathbb{N}}$ be a real sequence such that the series $\sum a_n^2$ converges. Justify the existence of a strictly increasing sequence of natural integers $(\phi(j))_{j \in \mathbb{N}}$ satisfying $$\forall j \in \mathbb{N}, \quad \sum_{n > \phi(j)}^{+\infty} a_n^2 \leqslant \frac{1}{8^j}.$$

Let $X$ and $Y$ be two independent real random variables, each following the distribution $\mathcal { R }$ (where $X ( \Omega ) = \{ - 1,1 \}$, $\mathbb { P } ( X = - 1 ) = \mathbb { P } ( X = 1 ) = \frac { 1 } { 2 }$). Determine the distribution of their product $X Y$.

Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of mutually independent random variables satisfying $\mathbb{P}(X_n = -1) = \mathbb{P}(X_n = 1) = \frac{1}{2}$ for all $n \in \mathbb{N}$, and let $(a_n)_{n \in \mathbb{N}}$ be a real sequence such that $\sum a_n^2$ converges. For all $N \in \mathbb{N}$, let $S_N = \sum_{n=0}^N X_n a_n$. Express the expectation and variance of $S_{\phi(j+1)} - S_{\phi(j)}$ in terms of the terms of the sequence $(a_n)_{n \in \mathbb{N}}$.

Let $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ be $n ^ { 2 }$ real random variables that are mutually independent, all following the distribution $\mathcal { R }$. The matrix random variable $M _ { n } = \left( m _ { i , j } \right) _ { 1 \leqslant i , j \leqslant n }$ takes values in $\mathcal { V } _ { n , n }$. We set $\tau _ { n } = \operatorname { tr } \left( M _ { n } \right)$.
Calculate the expectation and the variance of the variable $\tau _ { n }$.

Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of mutually independent random variables satisfying $\mathbb{P}(X_n = -1) = \mathbb{P}(X_n = 1) = \frac{1}{2}$ for all $n \in \mathbb{N}$, and let $(a_n)_{n \in \mathbb{N}}$ be a real sequence such that $\sum a_n^2$ converges. Let $S_N = \sum_{n=0}^N X_n a_n$ and let $A_j = \{|S_{\phi(j+1)} - S_{\phi(j)}| > 2^{-j}\}$. Using the sequence $(\phi(j))_{j \in \mathbb{N}}$ satisfying $\sum_{n > \phi(j)}^{+\infty} a_n^2 \leqslant \frac{1}{8^j}$, deduce the bound $\mathbb{P}(A_j) \leqslant 2^{-j}$.