We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. The sequence $\left( M ^ { k } \right)$ converges to a stochastic matrix $B$ all of whose rows are equal to $P ^ { \infty } = \left( b _ { 1 } , \ldots , b _ { n } \right)$.
Prove that $P ^ { \infty }$ is the unique probability distribution $P$ invariant by $M$, that is, satisfying $P M = P$.

Let $\theta$ be the unique antiderivative of $\psi$ vanishing at 0. Show that $\theta$ is of class $\mathcal{C}^\infty$, constant on $]-\infty, -1]$ (we denote this constant by $A$) and constant on $[1, +\infty[$ (we denote this constant by $B$). Verify that $A \neq B$.

Deduce from the above that $$\lim_{n \rightarrow +\infty} \mathbb{E}\left(\frac{1}{n} \sum_{i=1}^{n} \Lambda_{i,n}^{k}\right) = C_{k/2}$$

Construct a function $\rho \in \mathcal{C}^\infty(\mathbb{R})$, constant equal to 1 on $[-1,1]$ and constant equal to 0 on $\mathbb{R} \setminus [-2,2]$.

Let $\rho$ be the function constructed in question 30. Let $r$ be the function from $\mathbb{R}$ to $\mathbb{C}$ such that, for all real $x$, $$r(x) = \frac{1}{2\pi} \int_{-\infty}^{+\infty} \mathrm{e}^{\mathrm{i}x\xi} \rho(\xi)\,\mathrm{d}\xi$$ Show that $r$ is differentiable on $\mathbb{R}$ and give an expression for its derivative function (possibly involving an integral).

Let $\rho$ be the function constructed in question 30. Let $r$ be the function from $\mathbb{R}$ to $\mathbb{C}$ such that, for all real $x$, $$r(x) = \frac{1}{2\pi} \int_{-\infty}^{+\infty} \mathrm{e}^{\mathrm{i}x\xi} \rho(\xi)\,\mathrm{d}\xi$$ Show that $x \mapsto x^2 r(x)$ is bounded on $\mathbb{R}$ and deduce that $r$ is integrable and bounded on $\mathbb{R}$.

Let $A > 2$. Show that $$\lim_{n \rightarrow +\infty} \frac{1}{n} \mathbb{E}\left(\sum_{\substack{1 \leqslant i \leqslant n \\ |\Lambda_{i,n}| \geqslant A}} |\Lambda_{i,n}|^{p}\right) = 0.$$

We model the web by a directed graph with $n$ vertices. The matrix $A$ is the stochastic matrix described in question 29. We define $$B = ( 1 - \alpha ) A + \frac { \alpha } { n } J _ { n }$$ where $J _ { n }$ is the matrix in $\mathcal { M } _ { n } ( \mathbb { R } )$ whose coefficients are all equal to $1$, $A$ is the stochastic matrix described in question 29 and $\alpha$ is a real number in $] 0,1 [$, called the damping factor.
Let $Q$ be a probability distribution. We define the sequence $\left( Q ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ by $Q ^ { ( k ) } = Q B ^ { k }$ for every natural number $k$. Prove that the sequence $\left( Q ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ converges and that its limit $Q ^ { \infty }$ satisfies conditions (i) and (ii) described in the introduction to this part. It thus provides relevance scores for the $n$ pages of the web. The relevance of each page $j$ will be expressed as a function of those of the pages pointing to it, distinguishing between pages that point to another page and the others.

Let $\lambda > 0$ and let $f \in L^1(\mathbb{R}) \cap \mathcal{C}^1(\mathbb{R})$ such that $\hat{f} \in L^1(\mathbb{R})$ and such that $\hat{f}$ is zero outside the segment $[-\lambda, \lambda]$. We denote by $r_\lambda$ the function from $\mathbb{R}$ to $\mathbb{C}$ such that $r_\lambda(x) = r(\lambda x)$ for all real $x$, where $r(x) = \frac{1}{2\pi}\int_{-\infty}^{+\infty} \mathrm{e}^{\mathrm{i}x\xi}\rho(\xi)\,\mathrm{d}\xi$ and $\rho$ is the function from question 30. We admit that $f * r_\lambda$ is integrable. Show that $f = \lambda f * r_\lambda$.

Let $A > 2$. Let $f$ be a continuous and bounded function from $\mathbb{R}$ to $\mathbb{R}$ and $P$ a polynomial of degree $p$. Justify that there exists a constant $K$ such that $$\forall x \in \mathbb{R} \setminus ]-A, A[, \quad |f(x) - P(x)| \leqslant K|x|^{p}.$$

We assume that the numpy module of Python has been imported using the instruction \texttt{import numpy as np}. This thus gives access to the following functions:

• \texttt{np.identity( n )} creates $I _ { n }$, the identity matrix of order n;
• \texttt{A.shape} gives, in the form of a tuple, the size of array A, for example \texttt{np.identity(5).shape} $\rightarrow ( 5,5 )$;
• \texttt{np.dot(A, B)} computes the matrix product of A and B if A and B are two-dimensional arrays compatible with matrix multiplication.

The naive algorithm for computing $B ^ { k }$ is based on its definition, namely: $$\left\{ \begin{array} { l } B ^ { 0 } = I _ { n } \\ B ^ { k } = B B ^ { k - 1 } \quad \forall k \geqslant 1 \end{array} \right.$$ Write a Python function \texttt{puissance1(B, k)} that takes as arguments a square matrix $B$ and a natural number k and returns the matrix $B ^ { k }$ computed using the naive algorithm.

Let $\lambda > 0$ and let $f \in L^1(\mathbb{R}) \cap \mathcal{C}^1(\mathbb{R})$ such that $\hat{f} \in L^1(\mathbb{R})$ and such that $\hat{f}$ is zero outside the segment $[-\lambda, \lambda]$. Deduce that, if $f \in L^\infty(\mathbb{R})$, there exists a constant $C \in \mathbb{R}_+^*$, independent of $\lambda$ and of $f$, such that $$\left\|f'\right\|_\infty \leqslant C\lambda \|f\|_\infty$$

Let $A > 2$. Deduce that $$\lim_{n \rightarrow +\infty} \frac{1}{n} \mathbb{E}\left(\sum_{\substack{1 \leqslant i \leqslant n \\ |\Lambda_{i,n}| \geqslant A}} |f - P|\left(\Lambda_{i,n}\right)\right) = 0.$$

We assume that the numpy module of Python has been imported using the instruction \texttt{import numpy as np}. This thus gives access to the following functions:

• \texttt{np.identity( n )} creates $I _ { n }$, the identity matrix of order n;
• \texttt{A.shape} gives, in the form of a tuple, the size of array A, for example \texttt{np.identity(5).shape} $\rightarrow ( 5,5 )$;
• \texttt{np.dot(A, B)} computes the matrix product of A and B if A and B are two-dimensional arrays compatible with matrix multiplication.

The fast exponentiation algorithm is based on the following principle: $$\begin{cases} B ^ { 0 } = I _ { n } & \\ B ^ { k } = \left( B ^ { 2 } \right) ^ { \frac { k } { 2 } } & \text { if } k \text { is even } \\ B ^ { k } = B \left( B ^ { 2 } \right) ^ { \frac { k - 1 } { 2 } } & \text { if } k \text { is odd.} \end{cases}$$ Write a Python function \texttt{puissance2(B, k)} that takes as arguments a square matrix B and a natural number $k$ and returns the matrix $B ^ { k }$ computed using the fast exponentiation algorithm.

Let $f$ be a continuous and bounded function from $\mathbb{R}$ to $\mathbb{R}$. Show that $$\lim_{n \rightarrow +\infty} \mathbb{E}\left(\frac{1}{n} \sum_{i=1}^{n} f\left(\Lambda_{i,n}\right)\right) = \frac{1}{2\pi} \int_{-2}^{2} f(x) \sqrt{4 - x^{2}} \, \mathrm{d}x$$

We assume that the numpy module of Python has been imported using the instruction \texttt{import numpy as np}. This thus gives access to the following functions:

• \texttt{np.identity( n )} creates $I _ { n }$, the identity matrix of order n;
• \texttt{A.shape} gives, in the form of a tuple, the size of array A, for example \texttt{np.identity(5).shape} $\rightarrow ( 5,5 )$;
• \texttt{np.dot(A, B)} computes the matrix product of A and B if A and B are two-dimensional arrays compatible with matrix multiplication.

The naive algorithm for computing $B^k$ uses: $$\left\{ \begin{array} { l } B ^ { 0 } = I _ { n } \\ B ^ { k } = B B ^ { k - 1 } \quad \forall k \geqslant 1 \end{array} \right.$$ The fast exponentiation algorithm uses: $$\begin{cases} B ^ { 0 } = I _ { n } & \\ B ^ { k } = \left( B ^ { 2 } \right) ^ { \frac { k } { 2 } } & \text { if } k \text { is even } \\ B ^ { k } = B \left( B ^ { 2 } \right) ^ { \frac { k - 1 } { 2 } } & \text { if } k \text { is odd.} \end{cases}$$ We assume that $k \geqslant 2$ and we denote by $p$ the unique integer such that $2 ^ { p } \leqslant k < 2 ^ { p + 1 }$. For each of the calls \texttt{puissance1(B, k)} and \texttt{puissance2(B, k)}, compute the number of calls to the function \texttt{np.dot}, in the worst case and in the best case.

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

Let $X$ be a discrete random variable with finite expectation. Show that $$\mathbb{E}\left(X \mathbb{1}_{|X| \leqslant C}\right) \xrightarrow{C \rightarrow +\infty} \mathbb{E}(X).$$

Let $V$ and $V^{\prime}$ be two subspaces of $E$ of dimension $p$ (we recall that $p \geqslant 1$).
(a) Show that there exist $u_1 \in V$ and $u_1^{\prime} \in V^{\prime}$ of norm 1 such that $$\left\langle u_1, u_1^{\prime}\right\rangle = \sup\left\{\left\langle a, a^{\prime}\right\rangle \mid\left(a, a^{\prime}\right) \in V \times V^{\prime},\|a\|=\left\|a^{\prime}\right\|=1\right\}.$$
(b) Extend this result by showing that there exist a family $u = (u_1, \ldots, u_p)$ of vectors of $V$ and a family $u^{\prime} = (u_1^{\prime}, \ldots, u_p^{\prime})$ of vectors of $V^{\prime}$ such that $u$ and $u^{\prime}$ are orthonormal and satisfy the following two conditions:
(i) For $k = 1$, we have $$\left\langle u_1, u_1^{\prime}\right\rangle = \sup\left\{\left\langle a, a^{\prime}\right\rangle \mid\left(a, a^{\prime}\right) \in V \times V^{\prime},\|a\|=\left\|a^{\prime}\right\|=1\right\}.$$
(ii) For $k \in \llbracket 2, p \rrbracket$, we have $$\left\langle u_k, u_k^{\prime}\right\rangle = \sup\left\{\left\langle a, a^{\prime}\right\rangle \mid\left(a, a^{\prime}\right) \in V \times V^{\prime},\|a\|=\left\|a^{\prime}\right\|=1,\right.$$ $$\left.\left\langle a, u_l\right\rangle=\left\langle a^{\prime}, u_l^{\prime}\right\rangle=0 \text{ for all } l \in \llbracket 1, k-1 \rrbracket\right\}.$$
(Hint: One may construct the vectors $u_k$ and $u_k^{\prime}$ by induction on the integer $k$.)

Let $f$ be a power series and $z$ a complex number such that $\hat{f}(|z|) < \infty$. Show then that the series $f$ converges at $z$ and that $|f(z)| \leqslant \hat{f}(|z|)$. Give an example where this inequality is strict.

Let $\ell$ be a strictly positive integer. We are given a sequence $\left( v _ { n } \right) _ { n \geqslant 0 }$ of vectors in $\mathbb { R } ^ { \ell }$ such that the series $\sum _ { n } \left\| v _ { n + 1 } - v _ { n } \right\|$ converges.
(a) Show that the sequence $\left( v _ { n } \right) _ { n \geqslant 0 }$ is convergent.
(b) Let $v ^ { * }$ denote the limit of this sequence. Bound $\left\| v _ { n } - v ^ { * } \right\|$ by means of a remainder of the sum of the series $\sum _ { n } \left\| v _ { n + 1 } - v _ { n } \right\|$.

Let $\ell$ be a strictly positive integer. We are given a sequence $\left( v _ { n } \right) _ { n \geqslant 0 }$ of vectors in $\mathbb { R } ^ { \ell }$ such that the series $\sum _ { n } \left\| v _ { n + 1 } - v _ { n } \right\|$ converges.
(a) Show that the sequence $\left( v _ { n } \right) _ { n \geqslant 0 }$ is convergent.
(b) Let $v ^ { * }$ denote the limit of this sequence. Bound $\left\| v _ { n } - v ^ { * } \right\|$ by means of a remainder of the sum of the series $\sum _ { n } \left\| v _ { n + 1 } - v _ { n } \right\|$.

Show the interpolation inequality $$\forall f \in \mathcal{C}^{1}([0,1]), \quad \|f\|_{\infty} \leqslant \left\|f^{\prime}\right\|_{\infty} + C\left|f\left(x_{1}\right)\right|$$ with $C = 1$.

We denote by $\mathcal{C}([-1,1])$ the vector space of continuous functions from $[-1,1]$ to $\mathbb{C}$ and $\mathcal{T}([-1,1])$ the complex vector subspace of $\mathcal{C}([-1,1])$ generated by the functions $$e_k : t \mapsto e^{i\pi k t}, \quad k \in \mathbb{Z}.$$ Show that $\mathcal{T}([0,1])$ is a subalgebra of $\mathcal{C}([-1,1])$ for the usual multiplication law of functions.

We denote by $\mathcal{C}([-1,1]^2)$ the space of continuous functions from $[-1,1]^2$ to $\mathbb{C}$ and $\mathcal{T}([-1,1]^2)$ the subspace generated by the functions $$e_{u,v} : (s,t) \mapsto e^{i\pi us}e^{i\pi vt}, \quad (u,v) \in \mathbb{Z}^2.$$ Let $a,b,c,d \in [-1,1]$ such that $a < b$ and $c < d$. Show that for every $\varepsilon < \min\left(\frac{b-a}{2}, \frac{d-c}{2}\right)$, there exists $f_\varepsilon \in \mathcal{T}([-1,1]\times[-1,1])$ satisfying the following properties:

1. $f_\varepsilon(s,t) \in [0,1]$ for all $(s,t) \in [-1,1]^2$,
2. $f_\varepsilon(s,t) \leq \varepsilon$ for $(s,t) \notin [a,b]\times[c,d]$,
3. $f_\varepsilon(s,t) \geq 1-\varepsilon$ for $(s,t) \in [a+\varepsilon,b-\varepsilon]\times[c+\varepsilon,d-\varepsilon]$.