A box contains 5 identical balls labeled $1$ to $5$. Drawing with replacement three times, let $X$ denote the number of distinct balls drawn at least once. Then the mathematical expectation $E(X) = $ $\_\_\_\_$ .

A box contains 5 balls labeled $1$ to $5$. If we draw with replacement three times, let $X$ denote the number of distinct balls drawn at least once. Then $E(X) = $ $\_\_\_\_$ .

We assume $m>1$. We study the Galton-Watson process starting with $k$ individuals in generation 0, with $W_n$ the number of individuals in generation $n$. We define $u_n$ and $u_n^{(r)}$ as above.
Let $n\in\mathbb{N}^*$ and $r$ a natural integer greater than or equal to 2. Show the relation $$u_n^{(r)}=\sum_{i=1}^{n-1}u_i u_{n-i}^{(r-1)}$$

Let $p \in ]0,1[$, $q = 1-p$, $m = n^2$. We denote by $N$ the smallest index $k$ for which the matrix $M_k$ is completely filled.
a) Propose an approach to approximate the expectation of $N$ using a computer simulation with the functions above.
b) Give an expression for the exact value of this expectation involving $q$ and $m$.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$.
Determine the expectation and variance of $S_{n}$.

Let $S$ and $T$ be two finite real random variables that are independent and defined on $(\Omega, \mathcal{A}, P)$. We assume that $T$ and $-T$ have the same distribution.
Show that $E(\cos(S + T)) = E(\cos(S)) E(\cos(T))$.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$.
We consider the function $\varphi_{n}$ from $\mathbb{R}$ to $\mathbb{R}$ such that $\varphi_{n}(t) = E\left(\cos\left(S_{n} t\right)\right)$ for all real $t$.
Show that $\varphi_{n}(t) = (\cos t)^{n}$ for all integers $n \in \mathbb{N}^{*}$ and all real $t$.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$, and $u_{n} = \int_{0}^{\infty} \frac{1 - (\cos t)^{n}}{t^{2}} \mathrm{~d}t$.
Show, for all $n \in \mathbb{N}^{*}$, $$E\left(\left|S_{n}\right|\right) = \frac{2}{\pi} u_{n}$$ We will use the integral expression for the absolute value obtained in question I.A.5.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$, and $u_{n} = \int_{0}^{\infty} \frac{1 - (\cos t)^{n}}{t^{2}} \mathrm{~d}t$.
Deduce from the previous question that, for all $n \in \mathbb{N}$, $u_{2n+1} = u_{2n+2}$.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$ and $U_{n} = \left(\frac{S_{n}}{n}\right)^{4}$.
Show that $E\left(S_{n}^{4}\right) = 3n^{2} - 2n$ for all $n \in \mathbb{N}^{*}$.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$ and $U_{n} = \left(\frac{S_{n}}{n}\right)^{4}$.
Show that, for all $n \in \mathbb{N}^{*}$, $$P\left(U_{n} \geqslant \frac{1}{\sqrt{n}}\right) \leqslant \frac{3}{n^{3/2}}$$

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$, $U_{n} = \left(\frac{S_{n}}{n}\right)^{4}$, and $$\mathcal{Z}_{n} = \left\{\omega \in \Omega, \exists k \geqslant n, U_{k}(\omega) \geqslant \frac{1}{\sqrt{k}}\right\}$$ Show that $\mathcal{Z}_{n} \in \mathcal{A}$ for all $n \in \mathbb{N}^{*}$ and that $\lim_{n \rightarrow \infty} P\left(\mathcal{Z}_{n}\right) = 0$.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$, $U_{n} = \left(\frac{S_{n}}{n}\right)^{4}$, and $$\mathcal{Z}_{n} = \left\{\omega \in \Omega, \exists k \geqslant n, U_{k}(\omega) \geqslant \frac{1}{\sqrt{k}}\right\}$$ By considering $Z = \bigcap_{n \in \mathbb{N}^{*}} \mathcal{Z}_{n}$, show that $\left(\frac{S_{n}}{n}\right)$ converges almost surely to $0$.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$. We also consider a sequence $\left(a_{n}\right)_{n \in \mathbb{N}^{*}}$ of non-negative real numbers. For all $n \in \mathbb{N}^{*}$, we set $T_{n} = \sum_{k=1}^{n} a_{k} X_{k}$.
Show that the sequence $\left(E\left(\left|T_{n}\right|\right)\right)_{n \in \mathbb{N}^{*}}$ is increasing.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$. We also consider a sequence $\left(a_{n}\right)_{n \in \mathbb{N}^{*}}$ of non-negative real numbers. For all $n \in \mathbb{N}^{*}$, we set $T_{n} = \sum_{k=1}^{n} a_{k} X_{k}$.
Show that if the series $\sum a_{n}^{2}$ is convergent, then the sequence $\left(E\left(\left|T_{n}\right|\right)\right)_{n \in \mathbb{N}^{*}}$ is convergent.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$. We also consider a sequence $\left(a_{n}\right)_{n \in \mathbb{N}^{*}}$ of non-negative real numbers. For all $n \in \mathbb{N}^{*}$, we set $T_{n} = \sum_{k=1}^{n} a_{k} X_{k}$.
We assume $a_{1} \geqslant a_{2} + \cdots + a_{n}$. Show $E\left(\left|T_{n}\right|\right) = E\left(\left|T_{1}\right|\right) = a_{1}$.

Justify that for all $\ell \geqslant 0$ and $n \in \mathbb{N}$, $(N(0,\ell) = n+1) = (S_n \leqslant \ell < S_{n+1})$ up to a negligible set. Deduce that, up to negligible sets, $$\left(S_n \leqslant \ell\right) = (N(0,\ell) \geqslant n+1) \quad \text{and} \quad \left(S_n \geqslant \ell\right) \subset (N(0,\ell) \leqslant n+1).$$

Let $Y$ be a random variable taking values in $\mathbb{N}$ almost surely, and which admits an expectation. Show that $$\mathbb{E}(Y) = \sum_{k=1}^{+\infty} \mathbb{P}(Y \geqslant k)$$

Show that for all $n \in \mathbb{N}$ and $\ell \geqslant 0$, $$\mathbb{P}\left(S_n \leqslant \ell\right) \leqslant \mathbb{E}\left(\exp\left(\ell - S_n\right)\right)$$ then that $$\mathbb{P}\left(S_n \leqslant \ell\right) \leqslant e^{\ell} \mathbb{E}(\exp(-X))^n$$

Deduce that $\mathbb{P}\left(S_n \leqslant \ell\right)$ tends to 0 when $n \rightarrow +\infty$ and that $$\mathbb{E}(N(0,\ell)) \leqslant \frac{e^{\ell}}{1 - \mathbb{E}(\exp(-X))}$$

Show that for all $x \in \mathbb{R}, \ell \geqslant 0, k \in \mathbb{N}^*$ and $n \in \mathbb{N}^*$, $$\mathbb{P}\left(S_{n-1} < x \leqslant S_n, N(x, x+\ell) \geqslant k\right) \leqslant \mathbb{P}\left(S_{n-1} < x \leqslant S_n\right) \mathbb{P}(N(0,\ell) \geqslant k)$$ then that $$\mathbb{E}(N(x, x+\ell)) \leqslant \frac{e^{\ell}}{1 - \mathbb{E}(\exp(-X))}$$

Let $K > 0$ and $g : \mathbb{R} \rightarrow \mathbb{R}$ be a positive bounded function with support in $[0, K]$. The sequence of functions $f_n : \mathbb{R} \rightarrow \mathbb{R}$ is defined for $n \geqslant 0$ by $$f_n(x) = \sum_{k=0}^{n} \mathbb{E}\left(g\left(x - S_k\right)\right)$$ Show that for all $x \in \mathbb{R}$, the sequence $\left(f_n(x)\right)_{n \geqslant 0}$ is increasing. We denote by $f(x)$ its limit in $\mathbb{R} \cup \{+\infty\}$.

Let $K > 0$ and $g : \mathbb{R} \rightarrow \mathbb{R}$ be a positive bounded function with support in $[0, K]$. The sequence of functions $f_n : \mathbb{R} \rightarrow \mathbb{R}$ is defined for $n \geqslant 0$ by $$f_n(x) = \sum_{k=0}^{n} \mathbb{E}\left(g\left(x - S_k\right)\right)$$ Show that if $g = \mathbb{1}_{[0,K]}$, then $f(x) = \mathbb{E}(N(x-K, x))$.

Let $K > 0$ and $g : \mathbb{R} \rightarrow \mathbb{R}$ be a positive bounded function with support in $[0, K]$. The sequence of functions $f_n : \mathbb{R} \rightarrow \mathbb{R}$ is defined for $n \geqslant 0$ by $$f_n(x) = \sum_{k=0}^{n} \mathbb{E}\left(g\left(x - S_k\right)\right)$$ Deduce that for all $x \in \mathbb{R}$ and $n \in \mathbb{N}$, $$0 \leqslant f_n(x) \leqslant \|g\|_{\infty} \frac{e^K}{1 - \mathbb{E}(\exp(-X))}$$

Let $K > 0$ and $g : \mathbb{R} \rightarrow \mathbb{R}$ be a positive bounded function with support in $[0, K]$. The sequence of functions $f_n : \mathbb{R} \rightarrow \mathbb{R}$ is defined for $n \geqslant 0$ by $$f_n(x) = \sum_{k=0}^{n} \mathbb{E}\left(g\left(x - S_k\right)\right)$$ Conclude that the sequence of functions $f_n$ converges pointwise to a positive bounded function $f$ whose support is included in $\mathbb{R}^+$.