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) = $ $\_\_\_\_$ .

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 are given an enumeration of the set $\Lambda_X = \{y_i \mid i \in \mathbb{N}\}$. Deduce that there exists a sequence of positive reals $\left(q_i\right)_{i \geqslant 0}$ such that for all $x \in \mathbb{R}$, $$f(x) = \sum_{i=0}^{+\infty} q_i g\left(x - y_i\right), \quad \text{and} \quad \sum_{i \in \mathbb{N},\, y_i \in [x-K, x]} q_i = \mathbb{E}(N(x-K, x)).$$

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 = \sum_{i=1}^{pA} Y_i$ be the number of white balls drawn. Deduce the value of the variance of $Y$. Compare it to that of $Z$ (where $Z \sim \mathcal{B}(n,p)$).

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 $\delta _ { n } = \operatorname { det } \left( M _ { n } \right)$.
Prove that the variance of the variable $\delta _ { n }$ is equal to $n!$
One may expand $\delta _ { n }$ along a row and reason by induction.

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$. Let $X _ { n } ^ { 0 }$ be the discrete real random variable defined on $\mathcal{E}_n$ such that for $G \in \Omega_n$, the integer $X_n^0(G)$ equals the number of copies of $G_0$ contained in $G$. Express $X _ { n } ^ { 0 }$ using random variables of the type $X _ { H }$, and show that : $$\mathbf { E } \left( X _ { n } ^ { 0 } \right) = \sum _ { H \in \mathcal { C } _ { 0 } } \mathbf { P } ( H \subset G ) \leq n ^ { s _ { 0 } } p _ { n } ^ { a _ { 0 } } .$$

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$. We now assume that $\lim _ { n \rightarrow + \infty } \left( n ^ { \omega _ { 0 } } p _ { n } \right) = + \infty$. Show that the expectation $\mathbf { E } \left( \left( X _ { n } ^ { 0 } \right) ^ { 2 } \right)$ satisfies : $$\mathbf { E } \left( \left( X _ { n } ^ { 0 } \right) ^ { 2 } \right) = \sum _ { \left( H , H ^ { \prime } \right) \in C _ { 0 } ^ { 2 } } \mathbf { P } \left( H \cup H ^ { \prime } \subset G \right) = \sum _ { \left( H , H ^ { \prime } \right) \in C _ { 0 } ^ { 2 } } p _ { n } ^ { 2 a _ { 0 } - a _ { H \cap H ^ { \prime } } } .$$

We consider a sequence of random variables $(X_n : \Omega \longrightarrow \{-1,1\})_{n \in \mathbf{N}}$ defined on the same probability space $(\Omega, \mathscr{A}, P)$, taking values in $\{-1,1\}$, mutually independent and centered. For every $n \in \mathbf{N}^*$, we denote $S_n = \sum_{k=1}^n X_k$. We fix the integer $n \geqslant 1$. The random variable $N_n : \Omega \longrightarrow \mathbf{N}$ counts, for every $\omega \in \Omega$, the number of equality indices of the path $(X_1(\omega), \cdots, X_{2n}(\omega))$. For every integer $i$ between $1$ and $n$, the event $A_i$ is defined by: $$A_i = \left\{\omega,\; 2i \text{ is an equality index of } (X_1(\omega), \cdots, X_{2n}(\omega))\right\}.$$ Show that the random variable $N_n$ has finite expectation and that its expectation $\mathbb{E}(N_n)$ equals: $$\mathbb{E}(N_n) = \sum_{i=1}^n \frac{\binom{2i}{i}}{4^i}.$$ [Hint: one may express the variable $N_n$ using indicator functions associated with the events $A_i$.]

In an urn containing $n$ white balls and $n$ black balls, we proceed to draw balls without replacement, until the urn is completely empty. The draws are equally likely at each draw. For every integer $k$ between $1$ and $2n$, we say that the integer $k$ is an equality index if, after drawing the first $k$ balls without replacement, there remain as many black balls as white balls in the urn. We note that the integer $2n$ is always an equality index. We denote by $M_n$ the random variable counting the number of equality indices $k$ between $1$ and $2n$.
By using for example the events $B_i$: ``the integer $i$ is an equality index'', show that the variable $M_n$ has finite expectation equal to: $$\mathbb{E}(M_n) = \sum_{i=0}^{n-1} \frac{\binom{2i}{i} \cdot \binom{2n-2i}{n-i}}{\binom{2n}{n}}.$$

For $n$ a natural integer greater than or equal to 2, we consider the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability. We define a random variable $Z_{n}$ by $Z_{n}(\sigma) = \nu(\sigma)$.
Determine the average number of fixed points of a random permutation and its limit as $n$ tends to $+\infty$.

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$. We thus obtain a map $\omega : \mathfrak{S}_{n} \rightarrow \mathbb{N}$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_{n}$ such that $\omega(\sigma) = k$. We then consider, on the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability, the random variable $X_{n}$ defined by $X_{n}(\sigma) = \omega(\sigma)$.
Calculate, for $n \in \{2, 3, 4\}$, the quantity $\frac{1}{n!} \sum_{\sigma \in \mathfrak{S}_{n}} \omega(\sigma)$.

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_{n}$ such that $\omega(\sigma) = k$. We consider, on the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability, the random variable $X_{n}$ defined by $X_{n}(\sigma) = \omega(\sigma)$.
Deduce that $$\frac{1}{n!} \sum_{k=1}^{n} k^{2} s(n,k) = \mathbb{E}\left[X_{n}\right] + \left(\sum_{i=1}^{n} \sum_{j=1}^{n} \frac{1}{ij} - \sum_{i=1}^{n} \frac{1}{i^{2}}\right).$$

For $n$ a natural integer greater than or equal to 2, we consider the probability space $(\mathfrak{S}_n, \mathscr{P}(\mathfrak{S}_n))$ equipped with the uniform probability. We define a random variable $Z_n$ by $Z_n(\sigma) = \nu(\sigma)$.
Determine the average number of fixed points of a random permutation and its limit as $n$ tends to $+\infty$.

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_n$, we recall that there exists, up to order, a unique decomposition $\sigma = c_1 c_2 \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^*$ and $c_1, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_1 \leqslant \ell_2 \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_1 + \ell_2 + \cdots + \ell_{\omega(\sigma)} = n$. We thus obtain a map $\omega : \mathfrak{S}_n \rightarrow \mathbb{N}$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_n$ such that $\omega(\sigma) = k$. We consider, on the probability space $(\mathfrak{S}_n, \mathscr{P}(\mathfrak{S}_n))$ equipped with the uniform probability, the random variable $X_n$ defined by $X_n(\sigma) = \omega(\sigma)$.
Calculate, for $n \in \{2, 3, 4\}$, the quantity $\frac{1}{n!} \sum_{\sigma \in \mathfrak{S}_n} \omega(\sigma)$.

Let $n$ be a non-zero natural integer. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_n$ such that $\omega(\sigma) = k$.
Show that $$\frac{1}{n!} \sum_{k=1}^{n} k(k-1) s(n,k) = \sum_{i=1}^{n} \sum_{j=1}^{n} \frac{1}{ij} - \sum_{i=1}^{n} \frac{1}{i^2}.$$

Let $n$ be a non-zero natural integer. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_n$ such that $\omega(\sigma) = k$. We consider, on the probability space $(\mathfrak{S}_n, \mathscr{P}(\mathfrak{S}_n))$ equipped with the uniform probability, the random variable $X_n$ defined by $X_n(\sigma) = \omega(\sigma)$.
Deduce that $$\frac{1}{n!} \sum_{k=1}^{n} k^2 s(n,k) = \mathbb{E}\left[X_n\right] + \left(\sum_{i=1}^{n} \sum_{j=1}^{n} \frac{1}{ij} - \sum_{i=1}^{n} \frac{1}{i^2}\right).$$

Let $k$ be an even integer in $\{2, \ldots, N\}$. We assume in this question that the random variables $X_1, \ldots, X_N$ are $k$-independent.
We introduce the following notations: $\mathcal{T}$ denotes the set $\{1, \ldots, N\}^k$. If $T = (n_1, \ldots, n_k) \in \mathcal{T}$ and $n \in \{1, \ldots, N\}$, we denote by $m_T(n)$ the multiplicity of $n$ in $T$, that is $$m_T(n) = \operatorname{Card}\left\{i \in \{1, \ldots, k\}; n_i = n\right\}$$ For $\ell \in \{1, \ldots, k\}$, we denote by $\mathcal{T}_\ell$ the set of $T$ in $\mathcal{T}$ involving exactly $\ell$ distinct indices, where each has multiplicity at least 2, namely: $T \in \mathcal{T}_\ell$ if $$\operatorname{Card}\left(\left\{n \in \{1, \ldots, N\}; m_T(n) > 0\right\}\right) = \ell,$$ and $$\forall n \in \{1, \ldots, N\}, \quad m_T(n) > 0 \Rightarrow m_T(n) \geq 2$$ Finally, we denote by $|\mathcal{T}_\ell|$ the cardinality of $\mathcal{T}_\ell$.
I.5.a) Determine $|\mathcal{T}_1|$ and $|\mathcal{T}_\ell|$ for $\ell > k/2$.
I.5.b) Justify $$\mathbb{E}\left[(S_N)^k\right] = \sum_{T \in \mathcal{T}} \prod_{n=1}^N \mathbb{E}\left[X_n^{m_T(n)}\right]$$ then $$\mathbb{E}\left[(S_N)^k\right] = \sum_{\ell=1}^{k/2} \sum_{T \in \mathcal{T}_\ell} \prod_{n=1}^N \mathbb{E}\left[X_n^{m_T(n)}\right]$$
I.5.c) Prove that $$\mathbb{E}\left[(S_N)^k\right] \leq \sum_{\ell=1}^{k/2} K^{k-2\ell} |\mathcal{T}_\ell|$$
I.5.d) Let $\ell \in \{1, \ldots, k/2\}$. Justify the following estimate: $$|\mathcal{T}_\ell| \leq \binom{N}{\ell} \ell^k \leq \frac{N^\ell}{\ell!} \ell^k$$ One may consider the set of $T \in \mathcal{T}$ involving at most $\ell$ distinct elements.
I.5.e) For $\ell \in \{1, \ldots, k/2\}$, prove that $$\ell! \geq \ell^\ell e^{-\ell}$$ then deduce that $$|\mathcal{T}_\ell| \leq (Ne)^\ell \left(\frac{k}{2}\right)^{k-\ell}$$
I.5.f) Prove that $$\mathbb{E}\left[(S_N)^k\right] \leq \left(\frac{Kk}{2}\right)^k \sum_{\ell=1}^{k/2} \left(\frac{2Ne}{kK^2}\right)^\ell$$
I.5.g) We assume $$kK^2 \leq N.$$ Prove that $$\mathbb{E}\left[(S_N)^k\right] \leq \frac{\theta}{\theta - 1} \left(\frac{Nek}{2}\right)^{k/2} \leq 2\left(\frac{Nek}{2}\right)^{k/2},$$ where $$\theta := \frac{2Ne}{kK^2}$$
I.5.h) Prove (under hypothesis (27)) the following estimate: for all $t > 0$, $$\mathbb{P}\left(|S_N| \geq t\sqrt{N}\right) \leq 2\left(\frac{\sqrt{ek/2}}{t}\right)^k$$

Consider a particle moving on the coordinate plane, and denote the location of the particle at time $t \in \{ 0,1,2 , \ldots \}$ by $\left( X _ { t } , Y _ { t } \right)$. The initial location of the particle is $\left( X _ { 0 } , Y _ { 0 } \right) = ( 0,0 )$. Also, if $\left( X _ { t } , Y _ { t } \right) = ( a , b )$, then $\left( X _ { t + 1 } , Y _ { t + 1 } \right) = ( a + 1 , b )$ with probability $p , \left( X _ { t + 1 } , Y _ { t + 1 } \right) = ( a , b + 1 )$ with probability $q$, and $\left( X _ { t + 1 } , Y _ { t + 1 } \right) = ( a , b )$ with probability $1 - p - q$. Here, it is assumed that $p , q > 0 , p + q < 1$, and the movements of the particle at different time points are independent. Let $( X , Y )$ denote the location of the particle such that $\left( X _ { t + 1 } , Y _ { t + 1 } \right) = \left( X _ { t } , Y _ { t } \right)$ for the first time. Answer the following questions.
(1) Show that the probability that $( X , Y ) = ( 1,2 )$ is $3 p q ^ { 2 } ( 1 - p - q )$.
(2) For non-negative integers $n$, find the probability that $X + Y = n$.
(3) For non-negative integers $n$, let $f _ { n }$ denote the probability that $X = n$.
(a) Find $f _ { 0 }$.
(b) Express the probability that $X \geq n + 1$ given the condition $X \geq n$, using $f _ { 0 }$.
(c) Show that $f _ { n } = \left( 1 - f _ { 0 } \right) ^ { n } f _ { 0 }$.
(4) Express the expectation of $X$ using $p$ and $q$.
(5) Express the correlation coefficient between $X$ and $Y$ $$\frac { E \left[ \left( X - \mu _ { X } \right) \left( Y - \mu _ { Y } \right) \right] } { \sqrt { E \left[ \left( X - \mu _ { X } \right) ^ { 2 } \right] E \left[ \left( Y - \mu _ { Y } \right) ^ { 2 } \right] } }$$ using $p$ and $q$, where $\mu _ { X } = E [ X ]$ denotes the expectation of $X$ and $\mu _ { Y } = E [ Y ]$ denotes the expectation of $Y$.