Exercice 1 2620 Correction

Soit ${(X_{n})}_{n \in ℕ}$ une suite de variables aléatoires suivant chacune une loi de Bernoulli de paramètre $p_{n} \in [0; 1]$ . On suppose qu’il existe deux réels $a, b \in] 0; 1 [$ tels que

P (X_{n + 1} = 1 ∣ X_{n} = 1) = a et P (X_{n + 1} = 1 ∣ X_{n} = 0) = b .

Déterminer la limite de $(p_{n})$ .

Solution

Par la formule des probabilités totales,

	$p_{n + 1}$	$= P (X_{n + 1} = 1)$
		$= P (X_{n + 1} = 1 ∣ X_{n} = 1) P (X_{n} = 1) + P (X_{n + 1} = 1 ∣ X_{n} = 0) P (X_{n} = 0)$
		$= a p_{n} + b (1 - p_{n}) .$

Si la suite $(p_{n})$ admet une limite finie $ℓ$ , celle-ci doit vérifier

ℓ = a ℓ + b (1 - ℓ)

et donc

ℓ = \frac{b}{1 + b - a} .

Considérons cette valeur. On remarque

p_{n + 1} - ℓ = (a - b) (p_{n} - ℓ)

et donc, par récurrence,

\forall n \in ℕ, | p_{n} - ℓ | \leq {| a - b |}^{n} | p_{0} - ℓ | .

Puisque $| a - b | < 1$ , on obtient que $(p_{n})$ tend vers $ℓ$ .

Exercice 2 5468 MINES (PSI)Correction

Soit ${(X_{n})}_{n \geq 1}$ une suite de variables aléatoires indépendantes et identiquement distribuées selon la loi d’une variable $X$ telle que

P (X = 1) = P (X = - 1) = \frac{1}{2} .

Pour tout $n \in ℕ^{*}$ , on pose $S_{n} = X_{1} + \dots + X_{n}$ et $S_{0} = 0$ .

(a)

Déterminer $P (S_{n} = 0)$ .

Pour $k \in ℕ$ , on introduit l’événement

E_{k} = ⋃_{n \in ℕ} (S_{n} \geq k) et q_{k} = P (E_{k}) .

(b)

Pour $k \in ℕ^{*}$ . Déterminer la probabilité conditionnelle $P (E_{k} ∣ X_{1} = 1)$ .
(c)

Justifier

$q_{k} = \frac{1}{2} (q_{k - 1} + q_{k + 1}) pour tout k \in ℕ^{*} .$
(d)

En déduire que $q_{k} = 1$ pour tout $k \in ℕ$ .
(e)

Soit $k \in ℤ$ . Que vaut

$P (⋃_{n \in ℕ} (S_{n} \leq k)) ?$
(f)

Soit $k \in ℤ$ . Montrer que, presque sûrement, la suite $(S_{n})$ prend une infinité de fois la valeur $k$ .

Solution

(a)

La variable $Y = (X + 1) / 2$ suit une loi de Bernoulli de paramètre $p = 1 / 2$ , la variable $T_{n} = (S_{n} + n) / 2$ suit alors une loi binomiale de paramètres $n$ et $p = 1 / 2$ . On obtient alors

$P (S_{n} = 0) = P (T_{n} = n / 2) = {\begin{matrix} (\binom{n}{n / 2}) \frac{1}{2^{n}} & si n est pair \\ 0 & sinon. \end{matrix}$
(b)

Pour $k \in ℕ^{*}$ ,

$(E_{k} \cap X_{1} = 1)$ $= ⋃_{n \in ℕ} ((S_{n} \geq k) \cap (X_{1} = 1))$

$= ⋃_{n \in ℕ^{*}} ((X_{2} + \dots + X_{n} \geq k - 1) \cap (X_{1} = 1))$

$= (⋃_{n \in ℕ^{*}} (X_{2} + \dots + X_{n} \geq k - 1)) \cap (X_{1} = 1) .$

Par indépendance,

$P (E_{k} ∣ X_{1} = 1) = \frac{P (E_{k} \cap X_{1} = 1)}{P (X_{1} = 1)} = P (⋃_{n \in ℕ^{*}} (X_{2} + \dots + X_{n} \geq k - 1)) .$

Par symétrie de l’expérience,

$P (E_{k} ∣ X_{1} = 1) = P (⋃_{n \in ℕ^{*}} (X_{1} + \dots + X_{n - 1} \geq k - 1)) = q_{k - 1} .$
(c)

De la même façon,

$P (E_{k} ∣ X_{1} = 1) = P (⋃_{n \in ℕ^{*}} (X_{1} + \dots + X_{n - 1} \geq k + 1)) = q_{k + 1} .$

En considérant le système complet d’événements constitué de $(X_{1} = 1)$ et $(X_{1} = - 1)$ , la formule des probabilités totales donne

$P (⋃_{n \in ℕ} (S_{n} \geq k)) = \frac{1}{2} (q_{k - 1} + q_{k}) .$
(d)

La suite ${(q_{k})}_{k \in ℕ}$ est une suite récurrente linéaire d’ordre $2$ d’équation caractéristique $r^{2} - 2 r + 1 = 0$ de racine double $1$ . Le terme général de la suite ${(q_{k})}_{k \in ℕ}$ est donc de la forme

$q_{k} = λ k + μ avec (λ, μ) \in ℝ^{2} .$

La suite ${(q_{k})}_{k \in ℕ}$ est une suite de probabilités, elle est donc bornée et l’on en déduit $λ = 0$ . De plus, on a évidemment $q_{0} = 1$ et donc $q_{k} = 1$ pour tout $k \in ℕ$ .
(e)

Pour $k \geq 0$ , on a immédiatement

$P (⋃_{n \in ℕ} (S_{n} \leq k)) = 1 .$

Pour $k < 0$ , on observe que $S_{n}$ et $- S_{n}$ suivent la même loi pour employer le résultat qui précède

$P (⋃_{n \in ℕ} (S_{n} \leq k)) = P (⋃_{n \in ℕ} (- S_{n} \geq - k)) = 1 .$
(f)

Pour $k \in ℤ$ , on introduit

$r_{k} = P (⋂_{N \in ℕ} ⋃_{n \geq N} (S_{n} = k))$

qui mesure la probabilité que la suite $(S_{n})$ prend une infinité de fois la valeur $k$ . Comme au-dessus, on établit $r_{k} = \frac{1}{2} (r_{k - 1} + r_{k + 1})$ ce qui montre que la suite ${(r_{k})}_{k \in ℤ}$ est constante. Il reste à déterminer $r_{0}$ ce que l’on résout en étudiant l’événement contraire

$⋃_{N \in ℕ} ⋂_{n \geq N} (S_{n} \neq 0) .$

Pour $N \in ℕ$ , on remarque

$⋂_{n \geq N} (S_{n} \neq 0) \subset (⋂_{n \geq N} (S_{n} > 0)) \cup (⋂_{n \geq N} (S_{n} < 0))$

et

$⋂_{n \geq N} (S_{n} > 0) \subset ⋂_{n \geq 0} (S_{n} \neq - N)$

avec

$P (⋂_{n \geq 0} (S_{n} \neq - N)) = 1 - P (⋃_{n \geq 0} (S_{n} = - N)) = 0 .$

Ainsi,

$P (⋂_{n \geq N} (S_{n} > 0)) = 0$

et de même

$P (⋂_{n \geq N} (S_{n} < 0)) = 0 .$

Par réunion dénombrable d’événements négligeables et passage à l’événement contraire, on conclut que la suite ${(r_{k})}_{k \in ℤ}$ est constante égale à $1$ .

Exercice 3 5097

(Marche aléatoire sur $Z^{2}$ )

Soit ${(Z_{n})}_{n \geq 1}$ une suite de variables aléatoires indépendantes et identiquement distribuées selon une loi uniforme sur ${(1,0), (- 1,0), (0,1), (0, - 1)}$ .

Pour $n \in ℕ^{*}$ , on pose¹¹ 1 La suite $(S_{n})$ s’interprète comme une marche aléatoire sur la grille $ℤ^{2}$ amorcée en $(0,0)$ et qui, à chaque étape, passe aléatoirement d’une case à une case voisine. $S_{n} = Z_{1} + \dots + Z_{n}$ ainsi que $S_{0} = (0,0)$ .

On note $X_{n}$ et $Y_{n}$ les variables aléatoires déterminées par $Z_{n} = (X_{n}, Y_{n})$ et l’on introduit

U_{n} = X_{n} + Y_{n} et V_{n} = X_{n} - Y_{n} .

(a)

Les variables $X_{n}$ et $Y_{n}$ sont-elles indépendantes?
(b)

Les variables $U_{n}$ et $V_{n}$ sont-elles indépendantes?
(c)

Plus généralement, établir que les variables $U_{1}, \dots, U_{n}, V_{1}, \dots, V_{n}$ sont indépendantes.
(d)

Calculer $P (S_{n} = (0,0))$ .

On note $N_{n}$ le nombre de $k \in ⟦ 1; n ⟧$ pour lesquels $S_{k} = (0,0)$ .

(e)

Montrer que $E (N_{n})$ tend²² 2 Autrement dit, la marche aléatoire passe en moyenne une infinité de fois par $(0,0)$ . On peut aussi montrer, et cela est plus fort, qu’il est presque sûr que la marche passe une infinité de fois par $(0,0)$ . vers $+ \infty$ lorsque $n$ tend vers $+ \infty$ .

Exercice 4 4169 CENTRALE (MP)Correction

Un pion se déplace sur des cases numérotées par les entiers naturels. Initialement, il se trouve sur la case $0$ et à chaque instant, il se déplace d’un nombre strictement positif de cases. On note $Y_{i}$ la variable aléatoire donnant le nombre de cases parcourues lors de la $i$ -ème étape. On suppose que les $Y_{i}$ sont indépendantes et suivent la même loi. On pose

S_{n} = \sum_{i = 1}^{n} Y_{i}

qui donne la position du pion à l’instant $n$ ,

f_{i} = P (Y_{1} = i) et f (t) = \sum_{i = 1}^{+ \infty} f_{i} t^{i} .

Enfin, on introduit $k \in ℕ^{*}$ .

(a)

On suppose que $Y_{1} - 1$ suit la loi de Bernoulli de paramètre $p \in] 0; 1 [$ .

Écrire en Python une fonction qui prend un paramètre entier $k$ et qui renvoie $1$ si le pion atteint la case $k$ et $0$ sinon.

Écrire une fonction qui, sur une trentaine d’essais, renvoie la proportion de fois où le pion atteint la case $k$ . Comparer à $1 / E (Y_{1})$ .

On note $E_{k}$ l’événement: « le pion atteint la case $k$ » et $u_{k} = P (E_{k})$ .

(b)

Décrire l’événement $E_{k}$ à l’aide des variable aléatoires $S_{n}$ .
(c)

Calculer $P (E_{k} \cap {Y_{1} = j})$ pour $1 \leq j \leq k$ .
(d)

En déduire

$\forall k \in ℕ^{*}, u_{k} = \sum_{j = 1}^{k} u_{k - j} f_{j} .$
(e)

Justifier la définition de

$u (t) = \sum_{k = 0}^{+ \infty} u_{k} t^{k} pour t \in [0; 1]$

et montrer que $u (t) = \frac{1}{1 - f (t)}$ .
(f)

Calculer $u$ dans le cas où $Y_{1} - 1$ suit une loi de Bernoulli de paramètre $p \in] 0; 1 [$ et en déduire les $u_{k}$ .
(g)

On suppose que $Y_{1}$ prend un nombre fini de valeurs et que les entiers $k$ tels que $P (Y_{1} = k) \neq 0$ sont premiers entre eux dans leur ensemble. Montrer que $(u_{k})$ tend vers $1 / E (Y_{1})$ .

Solution

(a)

import random as rnd

def atteint(k,p):
    Y = 0
    while Y < k:
        x = rnd.random()
        if x < p:
            Y = Y + 2
        else:
            Y = Y + 1
    if Y == k:
        return 1
    else:
        return 0

def repete(k,p,N):
    x = 0
    for i in range(N):
        x = x + atteint(k,p)
    return x/N,1/(1+p)

(b)

$E_{k} = ⋃_{n \in ℕ} (S_{n} = k) .$
(c)

Si $j = k$ ,

$P (E_{k} \cap (Y_{1} = j)) = P (Y_{1} = k) .$

Si $j < k$ , par incompatibilité des événements $(S_{n} = k)$ (car les $Y_{i}$ prennent des valeurs strictement positives)

$P (E_{k} \cap (Y_{1} = j))$ $= \sum_{n = 1}^{+ \infty} P (S_{n} = k, Y_{1} = j)$

$= \sum_{n = 1}^{+ \infty} P (S_{n} = k ∣ Y_{1} = j) P (Y_{1} = j)$

$= \sum_{n = 2}^{+ \infty} P (S_{n} = k ∣ Y_{1} = j) P (Y_{1} = j)$

$= \sum_{n = 2}^{+ \infty} P S_{n - 1} = k - j P (Y_{1} = j)$

$= P (E_{k - j}) P (Y_{1} = j) .$
(d)

La famille des $(Y_{1} = j)$ avec $j \in ℕ^{*}$ est un système complet d’événements et donc

$P (E_{k})$ $= \sum_{j = 1}^{+ \infty} P (E_{k} \cap (Y_{1} = j))$

$= \sum_{j = 1}^{k} P (E_{k} \cap (Y_{1} = j)) + 0$

$= \sum_{j = 1}^{k} P (E_{k - j}) P (Y_{1} = j) + P (Y_{1} = k) = \sum_{j = 1}^{k} u_{k - j} f_{j}$

en posant $u_{0} = 1$ .
(e)

La suite $u_{k}$ est une suite de probabilité: elle est bornée et la série entière $\sum u_{k} t^{k}$ est de rayon de convergence au moins égale à $1$ .

Par produit de Cauchy de série absolument convergentes

$f (t) u (t) = \sum_{i = 1}^{+ \infty} f_{i} t^{i} \sum_{k = 0}^{+ \infty} u_{k} t^{k} = \sum_{n = 1}^{+ \infty} \sum_{i + k = n} f_{i} u_{k} t^{n} = \sum_{n = 1}^{+ \infty} u_{n} t^{n} = u (t) - 1 .$

On en déduit la relation proposée.
(f)

Si $Y_{1}$ suit une loi de Bernoulli

$f (t) = (1 - p) t + p t^{2} et u (t) = \frac{1}{1 - (1 - p) t - p t^{2}} = \frac{1}{(1 - t) (1 + p t)} .$

Par décomposition en éléments simples

$u (t) = \frac{1}{1 + p} \cdot \frac{1}{1 - t} + \frac{p}{1 + p} \cdot \frac{1}{1 + p t}$

et donc

$u_{k} = \frac{1 + {(- 1)}^{k} p^{k + 1}}{(1 + p)} .$
(g)

La fonction $f$ est un polynôme qui prend la valeur $1$ en $1$ :

$f (t) = \sum_{i = 1}^{n} f_{i} t^{i} .$

Vérifions que $f (t) - 1$ ne possède pas d’autres racines que $1$ de module inférieur à $1$ .

Supposons $| t | \leq 1$ . Si $f (t) = 1$ , on a par inégalité triangulaire

$1 = | \sum_{i = 1}^{n} f_{i} t^{i} | \leq \sum_{i = 1}^{n} f_{i} {| t |}^{i} \leq \sum_{i = 1}^{n} f_{i} = 1 .$

On en déduit $f_{i} {| t |}^{i} = f_{i}$ pour tout $i$ compris entre $1$ et $n$ . Les indices $i$ tels que les $f_{i}$ sont non nuls étant premiers dans leur ensemble, il vient¹¹ 1 Si $i_{1}, \dots, i_{p}$ sont les indices pour lesquels $f_{i} \neq 0$ , il suffit d’écrire $| t | = {| t |}^{i_{1} u_{1} + \dots + i_{p} u_{p}}$ avec $u_{1}, \dots, u_{p}$ entiers tels que $i_{1} u_{1} + \dots + i_{p} u_{p} = 1$ . $| t | = 1$ . De plus, par égalité dans l’inégalité triangulaire complexe, les $f_{i} t^{i}$ ont le même argument lorsqu’ils sont non nuls. Aussi, leur somme est égale à $1$ et l’on en tire que les $t^{i}$ sont tous égaux à $1$ . Par le même argument qu’au-dessus, il vient $t = 1$ .

$1$ est racine simple de la fraction $u$ et ses autres racines complexes sont de modules strictement supérieurs à $1$ . La décomposition en éléments simples de $u$ donne l’écriture

$u (t) = \frac{a}{1 - t} + v (t)$

avec $a = f^{'} (1) = E (Y_{1})$ et $v (t)$ dont la décomposition en série entière est de rayon de convergence $> 1$ et dont les coefficients sont donc de limite nulle. On en déduit que $u_{k}$ tend vers $E (Y_{1})$ quand $k$ tend vers l’infini.

Exercice 5 5688 Correction

Une matrice $M = {(m_{i, j})}_{1 \leq i, j \leq n} \in ℳ_{n} (ℝ)$ est dite strictement stochastique si tous les $m_{i, j}$ sont strictement positifs et

\forall i \in ⟦ 1; n ⟧, m_{i,1} + \dots + m_{i, n} = 1 .

(a)

Écrire une fonction stocha(n) qui renvoie une matrice strictement stochastique aléatoire de taille $n$ .

On fixe B = stoch(3).

(b)

Trouver des colonnes $x$ et $y$ de coordonnées strictement positifs telles que $B x = x$ et $B^{⊤} y = y$ .
(c)

On pose $L = \frac{x y^{⊤}}{x^{⊤} y}$ . Observer que $(B^{k})$ converge vers $L$ .

Une particule se déplace aléatoire sur $d$ points numérotés de $1$ à $d$ . À l’instant $n$ , la particule reste à la place qu’elle occupe avec une probabilité $p \in] 0; 1 [$ ou se déplace sur les autres points avec une probabilité uniforme. On note $X_{n}$ la variable aléatoire qui donne la position de la particule à l’instant $n$ et

P_{n} = {(\begin{matrix} P (X_{n} = 1) & \dots & P (X_{n} = d) \end{matrix})}^{⊤} .

(d)

Montrer qu’il existe une matrice strictement stochastique $Q$ telle que $P_{1} = Q P_{0}$ et expliciter celle-ci.
(e)

En déduire une expression de $P_{n}$ en fonction de $n$ , $Q$ et $P_{0}$ .
(f)

Sans calculs, justifier que $Q$ est diagonalisable. Expliciter ses valeurs propres et ses sous-espaces propres.
(g)

Déterminer la limite de $(P_{n})$ .

Solution

(a)

On forme un tableau aléatoire de valeurs strictement positives puis on divise les coefficients par la somme de la ligne qui les contient:

import numpy as np
import numpy.random as rd
import numpy.linalg as alg

def stocha(n):
    M = rd.random((n, n))
    for i in range(n):
        S = sum(M[i, :])
        M[i, :] = M[i, :] / S
    return M

(b)

On peut récupérer les valeurs de x et y à la main ou bien de façon plus programmée comme ci-dessous.

B = stocha(3)
vp, P = alg.eig(B)
x = P[:,np.where(np.isclose(vp,1.))[0]]
C = B.T
vp, P = alg.eig(C)
y = P[:,np.where(np.isclose(vp,1.))[0]]

(c)

On vérifie l’affirmation avec une valeur de $k$ suffisante.

L = np.dot(x, y.T) / np.dot(x.T, y)
print(L - alg.matrix_power(B,100))

On pourrait aussi calculer la norme euclidienne de la matrice différence puis tracer son évolution lorsque $k$ varie.

import matplotlib.pyplot as plt

plt.plot([alg.norm(L - alg.matrix_power(B,k)) for k in range(100)])
plt.show()

(d)

En vertu de l’expérience

$Q = (\begin{matrix} p & q & \dots & q \\ q & p & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & q \\ q & \dots & q & p \end{matrix})$

avec $q$ déterminé par $p + (n - 1) q = 1$ .
(e)

On remarque $P_{n + 1} = Q P_{n}$ et par récurrence $P_{n} = Q^{n} P_{0}$ .
(f)

La matrice $Q$ est symétrique réelle donc diagonalisable.

Après calculs, son polynôme caractéristique est

$χ_{Q} = (X - 1) {(X - (p - q))}^{n - 1} .$

Les sous-espaces propres de $Q$ sont

$E_{1} (Q) = Vect ((1, \dots,1)) et E_{p - q} (Q) = {(E_{1} (Q))}^{⊥} = {(x_{1}, \dots, x_{q}) | x_{1} + \dots + x_{d} = 0} .$
(g)

Par orthodiagonalisation et sachant $| p - q | < 1$ , on montre

$Q^{n} \to_{n \to + \infty}^{} P D P^{⊤} avec P = (\begin{matrix} 1 / \sqrt{d} & * & \dots & * \\ 1 / \sqrt{d} & * & \dots & * \\ ⋮ & ⋮ & ⋮ \\ 1 / \sqrt{d} & * & \dots & * \end{matrix}) et D = (\begin{matrix} 1 & 0 & \dots & 0 \\ 0 & 0 & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & 0 \\ 0 & \dots & 0 & 0 \end{matrix}) .$

Donc

$Q^{n} \to_{n \to + \infty}^{} (\begin{matrix} 1 / d & \dots & 1 / d \\ ⋮ & ⋮ \\ 1 / d & \dots & 1 / d \end{matrix}) .$

Puisque la somme des coefficients de $P_{0}$ vaut $1$ ,

$P_{n} \to_{n \to + \infty}^{} (\begin{matrix} 1 / d \\ ⋮ \\ 1 / d \end{matrix}) .$

[<] Calcul d'espérance par les fonctions génératrices [>] Convergences

Édité le 29-08-2023

	$(E_{k} \cap X_{1} = 1)$	$= ⋃_{n \in ℕ} ((S_{n} \geq k) \cap (X_{1} = 1))$
		$= ⋃_{n \in ℕ^{*}} ((X_{2} + \dots + X_{n} \geq k - 1) \cap (X_{1} = 1))$
		$= (⋃_{n \in ℕ^{*}} (X_{2} + \dots + X_{n} \geq k - 1)) \cap (X_{1} = 1) .$

	$P (E_{k} \cap (Y_{1} = j))$	$= \sum_{n = 1}^{+ \infty} P (S_{n} = k, Y_{1} = j)$
		$= \sum_{n = 1}^{+ \infty} P (S_{n} = k ∣ Y_{1} = j) P (Y_{1} = j)$
		$= \sum_{n = 2}^{+ \infty} P (S_{n} = k ∣ Y_{1} = j) P (Y_{1} = j)$
		$= \sum_{n = 2}^{+ \infty} P S_{n - 1} = k - j P (Y_{1} = j)$
		$= P (E_{k - j}) P (Y_{1} = j) .$

	$P (E_{k})$	$= \sum_{j = 1}^{+ \infty} P (E_{k} \cap (Y_{1} = j))$
		$= \sum_{j = 1}^{k} P (E_{k} \cap (Y_{1} = j)) + 0$
		$= \sum_{j = 1}^{k} P (E_{k - j}) P (Y_{1} = j) + P (Y_{1} = k) = \sum_{j = 1}^{k} u_{k - j} f_{j}$

Marches aléatoires