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

We consider a general balanced urn. For all real $u$ and $v$, we set $P_{0}(u,v) = u^{a_{0}} v^{b_{0}}$ and $P_{n}(u,v) = \sum_{\omega \in \Omega_{n}} u^{b(\omega)} v^{n(\omega)}$. We denote by $g_{n}$ the generating function of $X_{n}$ (the number of white balls after $n$ draws).
Justify the equalities $$\begin{aligned} & g_{n}(t) = \frac{1}{\operatorname{card}(\Omega_{n})} P_{n}(t, 1) \\ & E(X_{n}) = \frac{1}{\operatorname{card}(\Omega_{n})} \frac{\partial P_{n}}{\partial u}(1,1) \end{aligned}$$

Let $n$ be a non-zero natural number and let $X_n$ be a random variable that follows a uniform distribution on $D_n$. Show that there exist random variables $V_1, \ldots, V_n$ mutually independent, each following a Bernoulli distribution with parameter $1/2$, and such that $$X_n = \sum_{k=1}^{n} \frac{V_k}{2^k}.$$

We denote $D_n = \left\{ \sum_{j=1}^{n} \frac{x_j}{2^j},\, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n \right\}$.
Conversely, let $n$ be a non-zero natural number and let $X_n$ be a random variable that follows a uniform distribution on $D_n$. Show that there exist random variables $V_1, \ldots, V_n$ mutually independent, each following a Bernoulli distribution with parameter $1/2$, and such that $$X_n = \sum_{k=1}^{n} \frac{V_k}{2^k}.$$

In Friedman's urn model ($a_{0} = 1, b_{0} = 0, a = d = 0, b = c = 1$), fix an integer $n \geqslant 2$.
Using the Taylor expansion of $g_{n}$ to order $n$ at 0, deduce that, for all $m$ in $\llbracket 1, n \rrbracket$, $$P(X_{n} = m) = \frac{1}{n!} \sum_{k=0}^{m-1} (-1)^{k} \binom{n+1}{k} (m-k)^{n}.$$

For every integer $n \geqslant 2$, equip the set $\Omega_n$ of permutations of $\llbracket 1, n \rrbracket$ with the uniform probability. Let $p_i$ denote the probability that a permutation is alternating up (with $p_0 = p_1 = 1$). Define the random variable $M_n$ on $\Omega_n$ by: $M_n(\sigma) = k+1$ where $k$ is the largest integer such that $(\sigma(1), \ldots, \sigma(k))$ is alternating up. For every $i \in \llbracket 0, n \rrbracket$, show $\mathbb{P}(M_n > i) = p_i$.

In Friedman's urn model ($a_{0} = 1, b_{0} = 0, a = d = 0, b = c = 1$), an algorithm constructs a permutation of $S_{n}$ from an outcome of $n$ draws. Using question 33, compare, for any outcome, the number of white balls in the final composition of the urn with the number of ascents of the permutation associated with it by the algorithm above.

For every integer $n \geqslant 2$, equip the set $\Omega_n$ of permutations of $\llbracket 1, n \rrbracket$ with the uniform probability. Let $p_i$ denote the probability that a permutation is alternating up (with $p_0 = p_1 = 1$). Define the random variable $M_n$ on $\Omega_n$ by: $M_n(\sigma) = k+1$ where $k$ is the largest integer such that $(\sigma(1), \ldots, \sigma(k))$ is alternating up. Express $\mathbb{E}(M_n)$ as a function of $p_0, p_1, \ldots, p_n$. Deduce $\lim_{n \rightarrow \infty} \mathbb{E}(M_n) = \frac{\sin(1) + 1}{\cos(1)}$.

In this part, $d$ equals 1 and we simply denote $0_d = 0$. Moreover, $p$ is an element of $]0,1[$, $q = 1 - p$ and the distribution of $X$ is given by $$P ( X = 1 ) = p \quad \text{and} \quad P ( X = - 1 ) = q .$$ For $n \in \mathbb{N}$, determine $P \left( S _ { 2 n + 1 } = 0 \right)$ and justify the equality: $$P \left( S _ { 2 n } = 0 \right) = \binom { 2 n } { n } ( p q ) ^ { n }$$

In this part, $d$ equals 1 and we simply denote $0_d = 0$. Moreover, $p$ is an element of $]0,1[$, $q = 1 - p$ and the distribution of $X$ is given by $$P ( X = 1 ) = p \quad \text{and} \quad P ( X = - 1 ) = q .$$ We consider the functions $F$ and $G$ defined by the formulas $$\begin{aligned} & \forall x \in ]-1,1[ , \quad F ( x ) = \sum _ { n = 0 } ^ { + \infty } P \left( S _ { n } = 0 _ { d } \right) x ^ { n } \\ & \forall x \in [ - 1,1 ] , \quad G ( x ) = \sum _ { n = 1 } ^ { + \infty } P ( R = n ) x ^ { n } \end{aligned}$$ For $x \in ]-1,1[$, give a simple expression for $G ( x )$.
Express $P ( R = + \infty )$ as a function of $| p - q |$.
Determine the distribution of $R$.

In this part, $d$ equals 1 and we simply denote $0_d = 0$. Moreover, $p$ is an element of $]0,1[$, $q = 1 - p$ and the distribution of $X$ is given by $$P ( X = 1 ) = p \quad \text{and} \quad P ( X = - 1 ) = q .$$ We assume that $$p = q = \frac { 1 } { 2 }$$ Give a simple equivalent of $P ( R = 2 n )$ as $n$ tends to $+ \infty$. Deduce a simple equivalent of $E \left( N _ { n } \right)$ as $n$ tends to $+ \infty$.

A message is transmitted over a channel where each bit is inverted independently with probability $1-p \in ]0,1[$. Blocks of $r$ bits are transmitted. $X$ denotes the number of inversions during the transmission of a block of $r$ bits. We consider $\alpha \in ]0,1[$ and the condition $$\mathbb{P}(X \geqslant 2) \leqslant 1 - \alpha. \tag{II.2}$$ We set $a = \frac{p \ln(p)}{p-1}$ and $x = r\ln(p) - a$. Prove that condition (II.2) is equivalent to the condition $$x \mathrm{e}^{x} \leqslant -\alpha a \mathrm{e}^{-a}.$$

Let $n \in \mathbb{N}^{*}$. Show that $$1 = \sum _ { k = 0 } ^ { n } P \left( S _ { k } = 0 _ { d } \right) P ( R > n - k )$$

A message is transmitted over a channel where each bit is inverted independently with probability $1-p \in ]0,1[$. Blocks of $r$ bits are transmitted. $X$ denotes the number of inversions during the transmission of a block of $r$ bits. We consider $\alpha \in ]0,1[$ and the condition $$\mathbb{P}(X \geqslant 2) \leqslant 1 - \alpha. \tag{II.2}$$ With $a = \frac{p\ln(p)}{p-1}$ and $x = r\ln(p) - a$, condition (II.2) is equivalent to $xe^x \leqslant -\alpha a e^{-a}$. Let $V$ and $W$ be the Lambert functions defined in Part I. Using one of the functions $V$ and $W$ and Question 10, study the existence of a largest natural integer $r$ satisfying condition (II.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$.

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

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

Let $n \in \mathbb { N } ^ { * }$ and let $\gamma = \left( \gamma _ { 1 } , \ldots , \gamma _ { 2 n } \right)$ be a Dyck path of length $2 n$. For $t \in \mathbb { N }$, express $\mathbb { P } \left( A _ { t , \gamma } \right)$ as a function of $n$ and $p$, where $A _ { t , \gamma } = \bigcap _ { k = 1 } ^ { m } \left( X _ { t + k } = \gamma _ { k } \right)$.

Let $T$ be the random variable, defined on $\Omega$ and taking values in $\mathbb { N }$, equal to the first instant when the particle returns to the origin, if this instant exists, and equal to 0 if the particle never returns to the origin: $$\forall \omega \in \Omega , \quad T ( \omega ) = \begin{cases} 0 & \text { if } \forall k \in \mathbb { N } ^ { * } , S _ { k } ( \omega ) \neq 0 \\ \min \left\{ k \in \mathbb { N } ^ { * } \mid S _ { k } ( \omega ) = 0 \right\} & \text { otherwise } \end{cases}$$ Show that $T$ takes even values and that, for all $n \in \mathbb { N } , \mathbb { P } ( T = 2 n + 2 ) = 2 C _ { n } p ^ { n + 1 } ( 1 - p ) ^ { n + 1 }$.

We consider the graph $G$ represented in Figure 2. We denote $S _ { 1 } = \{ 1,3,6,8 \}$ and $S _ { 2 } = \{ 2,4,5,7 \}$.
Show that, if the point is on a vertex of part $S _ { 1 }$ at a given step, it will be on a vertex of part $S _ { 2 }$ at the next step and that, if it is on a vertex of $S _ { 2 }$ at a given step, it will be on a vertex of $S _ { 1 }$ at the next step.

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 an urn containing $A$ balls of which $pA$ are white and $qA$ are black. We draw simultaneously $n$ balls from the urn. We number from 1 to $pA$ each of the white balls and, for any natural integer $i \in \llbracket 1, pA \rrbracket$, we define $$Y_i = \begin{cases} 1 & \text{if the ball numbered } i \text{ was drawn,} \\ 0 & \text{otherwise.} \end{cases}$$ Let $Y$ denote the number of white balls drawn. Express $Y$ using the $Y_i$ and recover the value of the expectation of $Y$. Compare it to that of $Z$ (where $Z \sim \mathcal{B}(n,p)$ is the number of white balls in $n$ draws with replacement).

We consider an urn containing $A$ balls of which $pA$ are white and $qA$ are black. We draw simultaneously $n$ balls from the urn. We number from 1 to $pA$ each of the white balls and, for any natural integer $i \in \llbracket 1, pA \rrbracket$, we define $$Y_i = \begin{cases} 1 & \text{if the ball numbered } i \text{ was drawn,} \\ 0 & \text{otherwise.} \end{cases}$$ For $1 \leqslant i < j \leqslant pA$, prove that the random variable $Y_i Y_j$ follows a Bernoulli distribution whose parameter we will specify.

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