Marches aléatoires

{{ % variance % covariance

}}

L’objet de ce chapitre est de faire une première introduction à un exemple intéressant de processus stochastique, soit la marche aléatoire simple symétrique, et ce avec un minimum de formalisme.

Dans la partie Section 1, on définit la marche aléatoire simple symétrique, et on étudie l’allure de ses trajectoires. La partie Section 2 est dédiée à son comportement en temps long. La partie Section 3 présente une première application vers les mathématiques financières avec l’étude d’un problème de ruine.

Trajectoires de la marche aléatoire

Un processus stochastique est une suite de variables aléatoires indexée par le temps. Il permet de modéliser l’évolution temporelle d’un phénomène comme la richesse d’une joueuse ou la valeur d’un portefeuille d’actions par exemple. La marche aléatoire simple symétrique est le modèle le plus simple de processus à temps discret.

Dans toute la suite, on se place sur un espace probabilisé $(\Omega, \mathcal{F}, \mathbb{P})$.

Définition

Commençons par définir la marche aléatoire simple symétrique.

Définition 1 Une marche aléatoire simple symétrique sur $\mathbb{Z}$ est une suite $(S_n)_{n\in\mathbb{N}}$ de variables aléatoires telles que

1. $S_0=x\in\mathbb{Z}$ est déterministe,
2. $S_{n+1}=S_n+X_{n+1}$ pour tout $n\in\mathbb{N}$,

où $(X_n)_{n\geq 1}$ est une suite de variables aléatoires indépendantes et de même loi de Rademacher de paramètre $\frac 1 2$ : $$\mathbb{P}(X_1=-1)=\mathbb{P}(X_1=1)=\frac{1}{2}.$$

On parle de marche car ce processus peut représenter la position d’une personne qui se déplace en ligne droite par pas d’une unité avec équiprobabilité d’aller vers l’avant ($+1$) ou vers l’arrière ($-1$). Cette marche est dite simple car on ne fait que des pas d’amplitude $1$ et symétrique car il y a la même probabilité de tirer $1$ et $-1$ pour chaque incrément.

Ce processus peut également servir à modéliser la richesse d’une joueuse qui joue à pile ou face avec une pièce équilibrée. Partant d’une richesse initiale $S_0=x>0$, à chaque pas de temps elle perd ou gagne $1$ en fonction du tirage obtenu. Les variables $X_n$ représentent alors le gain du $n$-ème jeu, et $S_n$ la richesse totale de la joueuse après le $n$-ème tirage.

Plotly = require("https://cdn.plot.ly/plotly-2.34.0.min.js")
dists = require( 'https://cdn.jsdelivr.net/gh/stdlib-js/stats-base-dists@umd/browser.js' );
jstat = require('jstat');
seedrandom = require('seedrandom@3.0.5');
math = require("mathjs");
// see source here: https://github.com/stdlib-js/stats-base-dists/tree/umd
// continuous case

viewof inputs = Inputs.form([
  Inputs.range([-10, 10], {label: tex`x`, step: 1}, {value: 3}),
  Inputs.range([1, 100], {label: tex`n`, step: 1}),
  Inputs.button("Re-Tirage")
])

mu = inputs[0];
n_samples = inputs[1];
seed = 44 + inputs[2];

{

const rng = seedrandom(seed)

function random_walk(n=100){
    var samples = Array.from({length: n}, () => {
         if (rng.double() > 0.5) {
            return 1;
        } else {
            return -1;
            }
    });

    return samples;
}
var samples = random_walk(100);


// create a cumsum function:
function cumsum(array) {
  var result = [];
  array.reduce(function(a,b,i) { return result[i] = a+b; },0);
  return result;
}


var npoints=100, mini = 0, maxi=100;
var x = new Array(npoints), walk = new Array(npoints), zeros = new Array(npoints), z = new Array(npoints), i, j;

//  Densité:s
for(var i = 0; i < npoints; i++) {
    x[i] = i ;
    zeros[i] = 0;
    }

{
    // points lower
var trace1 = {
        x: x.slice(1, n_samples+1),
        y: zeros.slice(1, n_samples+1),
        z: samples.slice(0, n_samples),
        // mode: 'markers',
        type: 'heatmap',
            xaxis: 'x2',

        // marker: {
        //     color: samples2.slice(0, n_samples2).map((x) => x > 0 ? 'blue' : 'red'),
        //     size: 5,
        // },
        showscale: false,
        colorscale: [[0, "rgb(66, 139, 202)"], [1, "rgb(255,0,0)"]],

  }

walk = cumsum(samples);
for(var i = 0; i < npoints; i++) {
    walk[i] = walk[i] + mu ;
    }


var trace22 = {
        x: x.slice(0, n_samples),
        y: walk.slice(0, n_samples),
        type: "scatter",
        mode: "lines",
        name: 'Marche aléatoire',
        line: {color: 'black'},
        yaxis: 'y2',
        xaxis: 'x2',
        }



var data = [
  trace1,
  trace22,
  ];


var layout = {
    width: 600,
  xaxis: {range: [0, n_samples+1],
          showticklabels: false,
          autorange: false},
    yaxis: {domain: [0, 0.08],
            showticklabels: false,
      ticks:"",
            range: [-0.5, 0.5],
            autorange: false},
    xaxis2: {matches: 'x',
              range: [0, n_samples+1],
          autorange: true},
    yaxis2: {domain: [0.29, 0.99],
              range: [-20, 20]},

  showlegend: false,

};

    var config = {responsive: true}
    const div = DOM.element('div');
    Plotly.react(div, data, layout, config);
    return div;
    }
}

Plotly = Object {version: "2.34.0", register: ƒ(t), newPlot: ƒ(t, r, n, i), restyle: ƒ(t, r, n, i), relayout: ƒ(t, e, r), redraw: ƒ(t), update: ƒ(t, r, n, i), react: ƒ(t, r, n, i), extendTraces: ƒ(r, n, i, a), prependTraces: ƒ(r, n, i, a), addTraces: ƒ(r, n, i), deleteTraces: ƒ(r, n), moveTraces: ƒ(r, n, i), purge: ƒ(t), addFrames: ƒ(t, e, r), deleteFrames: ƒ(t, e), animate: ƒ(t, e, r), setPlotConfig: ƒ(t), deleteActiveShape: ƒ(t), toImage: ƒ(t, e), …}

dists = Object {arcsine: Object, bernoulli: Object, beta: Object, betaprime: Object, binomial: Object, cauchy: Object, chi: Object, chisquare: Object, cosine: Object, degenerate: Object, discreteUniform: Object, erlang: Object, exponential: Object, f: Object, frechet: Object, gamma: Object, geometric: Object, gumbel: Object, hypergeometric: Object, invgamma: Object, …}

jstat = ƒ()

seedrandom = ƒ(n, t, r)

math = Object {isNumber: ƒ(e), isComplex: ƒ(e), isBigNumber: ƒ(e), isBigInt: ƒ(e), isFraction: ƒ(e), isUnit: ƒ(e), isString: ƒ(e), isArray: ƒ(), isMatrix: ƒ(e), isCollection: ƒ(e), isDenseMatrix: ƒ(e), isSparseMatrix: ƒ(e), isRange: ƒ(e), isIndex: ƒ(e), isBoolean: ƒ(e), isResultSet: ƒ(e), isHelp: ƒ(e), isFunction: ƒ(e), isDate: ƒ(e), isRegExp: ƒ(e), …}

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

Figure 1: Marche aléatoire simple symétrique et son chemin, initialisée en $(0,x)$.

À partir de la définition, on obtient très facilement le comportement moyen de la marche.

Proposition 1 Pour tout $n\in\mathbb{N}$, on a $$\mathbb{E}[S_n]=S_0,\quad \mathop{\mathrm{Var}}(S_n)=n.$$

Preuve. Remarquons d’abord que $$\begin{align*} \mathbb{E}[X_1]&=(-1)\times \frac{1}{2}+1\times \frac{1}{2}=0,\\ \mathop{\mathrm{Var}}(X_1)&=\mathbb{E}[X_1^2]=(-1)^2\times \frac{1}{2}+1^2\times \frac{1}{2}=1, \end{align*}$$ les incréments sont donc centrés et réduits. Par linéarité de l’espérance, on obtient $$\mathbb{E}[S_n]=\mathbb{E}[S_0+\sum_{k=1}^n X_k]=S_0+\sum_{k=1}^n \mathbb{E}[X_k]=S_0,$$ puisque $S_0$ est déterministe. Enfin, en utilisant l’indépendance des $X_k$, on obtient $$\mathop{\mathrm{Var}}(S_n)=\mathop{\mathrm{Var}}(S_0+\sum_{k=1}^n X_k)=\sum_{k=1}^n \mathop{\mathrm{Var}}(X_k)=n,$$ d’où le résultat.

Ainsi, en moyenne la marche reste constante, mais sa variance devient de plus en plus grande au cours du temps.

Représentation graphique

Les marches aléatoires, comme tous les processus à valeurs discrètes, ont une représentation graphique naturelle. On représente graphiquement un tirage de la marche $(S_n)_{n\in\mathbb{N}}$ sur l’intervalle de temps $\llbracket 0,N \rrbracket$ par une ligne brisée joignant les points $(0,S_0)$, $(1,S_1)$, ,$(N,S_N)$. On a donc en abscisse le temps, et en ordonnée la valeur de la marche, cf. Figure 1.

La marche aléatoire est un processus à temps discret, donc rigoureusement sa représentation graphique devrait être constituée des points $(n,S_n)$ non reliés. Par exemple, $S_{1/2}$ n’est pas défini. Cependant, on relie les points pour une meilleure lecture des graphiques.

On s’intéresse maintenant aux représentations graphiques qui peuvent correspondre à des tirages de la marche aléatoire.

Définition 2 Soit $n>m$ deux entiers naturels et $(a,b)\in\mathbb{Z}^2$ deux entiers relatifs. On appelle chemin de $(m,a)$ à $(n,b)$ la représentation graphique d’un tirage de la marche aléatoire telle que $S_m=a$ et $S_n=b$.

Figure 2: Voici deux chemins de $(1,1)$ à $(5,3)$.

On peut maintenant se poser la question de savoir s’il existe toujours un chemin qui relie deux points quelconques, et s’il en existe, combien on peut construire de chemins différents reliant ces deux points. On peut facilement montrer que certains chemins sont impossibles en regardant la parité de la marche aléatoire et son amplitude maximale.

Proposition 2 (Parité) Pour tout $n\in\mathbb{N}$, $S_{2n}$ a la même parité que $S_0$ et $S_{2n+1}$ a la parité opposée à celle de $S_0$.

Preuve. Pour tout $n$, $X_{n+1}$ prend les valeurs $-1$ ou $1$ donc est impair. Comme $S_{n+1}=S_n+X_{n+1}$, la marche change de parité à chaque pas de temps.

On en déduit immédiatement que les chemins doivent respecter cette alternance de parité.

Corollaire 1 Si $n-m$ et $b-a$ n’ont pas la même parité, alors il n’existe pas de chemin de $(m,a)$ à $(n,b)$.

Preuve. Supposons sans perte de généralité que $n-m$ est pair, et qu’il existe un chemin de $(m,a)$ à $(n,b)$. Alors $S_m=a$ et $S_n=b$ ont nécessairement la même parité, donc $S_n-S_m=b-a$ est pair.

Exemple 1 Il n’existe pas de chemin de $(0,0)$ à $(2,1)$.

Proposition 3 (Amplitude) Pour tout $n\in\mathbb{N}$, on a $S_0-n\leq S_n\leq S_0+n$.

Preuve. Pour tout $n$, $X_{n}$ prend les valeurs $-1$ ou $1$ donc en particulier $$-1\leq X_n\leq 1.$$ Comme $S_{n}=S_0+\sum_{k=1}^n X_k$, en sommant les inégalités on obtient bien $$S_0-n\leq S_n\leq S_0+n,$$ d’où le résultat.

Corollaire 2 Si $n-m<|b-a|$, alors il n’existe pas de chemin de $(m,a)$ à $(n,b)$.

Preuve. Supposons qu’il existe un chemin de $(m,a)$ à $(n,b)$. Alors $S_m=a$ et $S_n=b$. En particulier, $S_n=S_m+\sum_{k=m+1}^nX_k$, d’où $$\begin{align*} &S_m-(n-m)\leq S_n\leq S_m+(n-m)\\ \Rightarrow & \; a-(n-m)\leq b\leq a+(n-m)\\ \Rightarrow & \; -(n-m)\leq b-a\leq n-m. \end{align*}$$ On a donc nécessairement $|b-a|\leq n-m$.

Exemple 2 Il n’existe pas de chemin de $(0,0)$ à $(2,4)$.

viewof inputs2 = Inputs.form([
  Inputs.range([2, 100], {label: tex`n`, step: 2}),
  Inputs.button("Re-Tirage")
])

n_samples2 = inputs2[0];
seed2 = 44 + inputs2[1];

{
var npoints2=n_samples2
const rng = seedrandom(seed2)
var samples2 = new Array(npoints2)
// create a vector of size 100 whose first half is 1 and second half is -1
for (var i = 0; i < npoints2 ; i++) {
  samples2[i] = i >= npoints2/2  ? 1 : -1;
}

// https://www.codemzy.com/blog/shuffle-array-javascript
function shuffleArray(array) {
  let length = array.length;
  let shuffle = array.slice(); // copy of array
  // loop over the array
  for (let i = length - 1; i > 0; i -= 1) {
    let random = Math.floor(rng.double() * (i + 1)); // random card position
    let current = shuffle[i]; // current card
    // swap the random card and the current card
    shuffle[i] = shuffle[random]; // move the random card to the current position
    shuffle[random] = current; // put the current card in the random position
  }
  return shuffle; // return shuffled array
};


samples2=shuffleArray(samples2);

var x2 = new Array(npoints2), walk2 = new Array(npoints2), zeros2 = new Array(npoints2), z = new Array(npoints2), i, j;


// create a cumsum function:
function cumsum(array) {
  var result = [];
  array.reduce(function(a,b,i) { return result[i] = a+b; },0);
  return result;
}

var walkint = cumsum(samples2);
walk2 = new Array(npoints2+1),
walk2[0] = 0
for(i = 0; i < npoints2; i++) {
    walk2[i+1] = walkint[i];
    }

//  Densité:
for(var i = 0; i < npoints2+1; i++) {
    x2[i] = i ;
    zeros2[i] = 0;
    }

{
    // points lower
var trace1 = {
        x: x2.slice(1, n_samples2+1),
        y: zeros2.slice(1, n_samples2+1),
        z: samples2.slice(0, n_samples2),
        // mode: 'markers',
        type: 'heatmap',
            xaxis: 'x2',

        // marker: {
        //     color: samples2.slice(0, n_samples2).map((x) => x > 0 ? 'blue' : 'red'),
        //     size: 5,
        // },
        showscale: false,
        colorscale: [[0, "rgb(66, 139, 202)"], [1, "rgb(255,0,0)"]],

  }



var trace22 = {
        x: x2.slice(0, n_samples2+1),
        y: walk2.slice(0, n_samples2+1),
        type: "scatter",
        mode: "lines",
        name: 'Marche aléatoire',
        line: {color: 'black'},
        yaxis: 'y2',
        xaxis: 'x2',
        }



var data = [
  trace1,
  trace22,
  ];


var layout = {
    width: 600,
  xaxis: {range: [0, n_samples2+1],
          showticklabels: false,
          autorange: false},
    yaxis: {domain: [0, 0.08],
            showticklabels: false,
      ticks:"",
            range: [-0.5, 0.5],
            autorange: false},
    xaxis2: {matches: 'x',
              range: [0, n_samples2+1],
          autorange: true},
    yaxis2: {domain: [0.29, 0.99],
              range: [-14, 14]},

  showlegend: false,

};

    var config = {responsive: true}
    const div = DOM.element('div');
    Plotly.react(div, data, layout, config);
    return div;
    }
}

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

RuntimeError: tex could not be resolved

OJS Runtime Error

tex could not be resolved

Figure 3: Marche aléatoire simple symétrique passant en $(0,0)$ et en $(100,0)$.

Une fois les conditions de parité et d’amplitude satisfaites, il existe toujours des chemins reliant deux points, et on peut les dénombrer explicitement.

Proposition 4 (Nombre de chemins) Si $|b-a|\leq n-m$ et $n-m$ et $b-a$ ont la même parité, alors le nombre de chemins de $(m,a)$ à $(n,b)$ est le nombre de combinaisons $\displaystyle \binom{n-m}{\frac{n-m}{2}+\frac{b-a}{2}}$.

Preuve. Un chemin de $(m,a)$ à $(n,b)$ correspond à $n-m$ pas de la marche aléatoire en partant de $a$ et en arrivant en $b$. Supposons sans perte de généralité que $b>a$. Alors on peut décomposer les pas de la marche entre $x$ pas vers le haut (tirages de $+1$) et $y$ pas vers le bas (tirages de $-1$). On doit avoir un nombre total de pas de $x+y=n-m$, et une différence des ordonnées de $x-y=b-a$, ce qui donne le système

$$\begin{align*} \left\{\begin{array}{rcl} x+y&=&n-m\\ x-y&=&b-a \end{array} \right. \Leftrightarrow \left\{\begin{array}{rcl} x&=&\frac{n-m}{2}+\frac{b-a}{2}\\ y&=&\frac{n-m}{2}-\frac{b-a}{2} \end{array} \right. \enspace. \end{align*}$$

Pour dénombrer le nombre total de chemins de longueur $x+y$ avec $x$ montées et $y$ descentes, il suffit de choisir les emplacements de $x$ montées parmi les $x+y$ pas. On obtient donc $\binom{x+y}{x}=\binom{n-m}{\frac{n-m}{2}+\frac{b-a}{2}}$ chemins.

Remarquons que pour dénombrer le nombre de chemins d’un point à un autre, nous n’avons pas utilisé le fait que $\mathbb P(X=1)=\mathbb P(X=-1)$, mais uniquement le fait que $X$ ne peut prendre que les valeurs $-1$ et $1$. Le résultat ci-dessus est donc également valable pour les marches asymétriques où $p=\mathbb P(X=1)=1-\mathbb P(X=-1)\neq \frac{1}{2}$.

Principe de réflexion

On souhaite maintenant dénombrer les chemins qui ont une propriété particulière supplémentaire, comme passer par un point fixé. Pour cela, on utilise les propriétés de symétrie de la marche.

Proposition 5 (Principe de réflexion) Soit $a$ et $b$ deux entiers naturels non nuls et $n,m$ deux entiers naturels tels que $n>m$, $|b-a|\leq n-m$ et $b-a$ et $n-m$ ont la même parité. Alors le nombre de chemins de $(m,a)$ à $(n,b)$ passant par $0$ (i.e. touchant l’axe des abscisses) est égal au nombre de chemins de $(m,a)$ à $(n,-b)$.

Figure 4: Réflexion: un chemin de $(0,2)$ à $(11,1)$ passant par 0 (trait bleu) et son image (tirets rouges) par la symétrie de premier passage en 0.

Preuve. Le principe est de construire une bijection entre les deux ensembles de chemins pour prouver qu’ils ont le même cardinal. Pour cela, on exploite la symétrie de la marche, comme illustré figure Figure 4.

Considérons un chemin $(S_m,\ldots,S_n)$ de $(m,a)$ à $(n,b)$ passant par $0$ pour la première fois en $p$. On a alors $m<p<n$. On construit un chemin $(\widetilde{S}_m,\ldots,\widetilde{S}_n)$ de $(m,a)$ à $(n,-b)$ en gardant la première partie du chemin initial de $(m,a)$ à $(p,0)$, puis en prenant ensuite le symétrique du chemin initial par rapport à l’axe des abscisses de $(p,0)$ à $(n,-b)$ : $$\begin{align*} \widetilde{S}_k=\left\{ \begin{array}{lcl} S_k &\text{ si }& m\leq k\leq p,\\ -S_k&\text{ si }& p\leq k\leq n. \end{array} \right. \end{align*}$$ Cette application définit une bijection entre les deux ensembles de chemins. En effet, si on prend maintenant un chemin $(\widetilde{S}_m,\ldots,\widetilde{S}_n)$ de $(m,a)$ à $(n,-b)$, comme il fait des pas de $1$, que $a>0$ et $-b<0$, ce chemin passe nécessairement par $0$. Soit $p$ le premier instant où le chemin est en $0$. On construit alors un chemin $(S_m,\ldots,S_n)$ de $(m,a)$ à $(n,b)$ passant par $0$ en posant $$\begin{align*} S_k=\left\{ \begin{array}{lcl} \widetilde{S}_k &\text{ si }& m\leq k\leq p,\\ -\widetilde{S}_k&\text{ si }& p\leq k\leq n. \end{array} \right. \end{align*}$$ Il y a donc le même nombre de chemins des deux types.

A nouveau, nous n’avons pas utilisé le fait que $\mathbb P(X=1)=\mathbb P(X=-1)$, mais uniquement le fait que $X$ ne peut prendre que les valeurs $-1$ et $1$ qui sont symétriques l’une de l’autre. Le résultat ci-dessus est donc également valable pour les marches asymétriques où $p=\mathbb P(X=1)=1-\mathbb P(X=-1)\neq \frac{1}{2}$. Une première application de cette propriété est le résultat suivant connu sous le nom de théorème du scrutin.

Théorème 1 (du scrutin) Au cours d’une élection opposant deux candidates $A$ et $B$, la candidate $A$ (resp. $B$) a obtenu $a$ (resp. $b$) voix, avec $a>b$. Alors la probabilité que $A$ ait été majoritaire (au sens large) tout au long du dépouillement est $$p=1-\frac{b}{a+1}.$$

Preuve. Tous les dépouillement étant équiprobables, $p$ s’obtient comme le rapport du nombre de dépouillements avec $A$ en tête tout le long par le nombre total de dépouillements. On peut modéliser un dépouillement par une marche aléatoire $(S_n)$ (pas nécessairement symétrique) où $S_n$ est le nombre de voix d’avance de $A$ sur $B$ après le dépouillement du $n$-ème bulletin.

Il y a en tout $a+b$ bulletins et à la fin $a-b$ voix d’avance de $A$ sur $B$, donc le nombre total de dépouillements est le nombre de chemins de $(0,0)$ à $(a+b,a-b)$ et vaut $\binom{a+b}{a}$.

Le nombre de dépouillements avec $A$ en tête tout le long correspond

• au nombre de chemins de $(0,0)$ à $(a+b,a-b)$ ne prenant aucune valeur strictement négative, autrement dit le nombre de chemins de $(0,0)$ à $(a+b,a-b)$ ne touchant pas $-1$;
• au nombre de chemins de $(0,1)$ à $(a+b,a-b+1)$ ne touchant pas $0$, en décalant d’un cran les ordonnées;
• au nombre total de chemins de $(0,1)$ à $(a+b,a-b+1)$ moins le nombre de chemins de $(0,1)$ à $(a+b,a-b+1)$ touchant $0$;
• au nombre total de chemins de $(0,1)$ à $(a+b,a-b+1)$ moins le nombre de chemins de $(0,1)$ à $(a+b,-(a-b+1))$ par le principe de réflexion.

Il vaut donc $\binom{a+b}{a}-\binom{a+b}{b-1}$. Ainsi

$$\begin{align*} p &=\frac{\binom{a+b}{a}-\binom{a+b}{b-1}}{\binom{a+b}{a}}=1-\frac{\binom{a+b}{b-1}}{\binom{a+b}{a}} \\ &=1-\frac{(a+b)!a!b!}{(b-1)!(a+1)!(a+b)!}=1-\frac{b}{a+1}, \end{align*}$$

d’où le résultat.

Comportement asymptotique

On s’intéresse maintenant au comportement de la marche sans limite de temps. Parmi les questions d’intérêt, on peut se demander si elle revient à son point de départ $x$, combien de fois et en combien de temps.

Comme les $(X_n)_{n\geq 1}$ sont indépendantes et de même loi intégrable, on peut appliquer la loi des grands nombres pour obtenir que $$\frac{S_n}{n}\xrightarrow[n\to\infty]{ps}\mathbb{E}[X_1]=0,$$ ce qui ne donne aucune information sur le comportement en temps long de $S_n$.

Propriété de Markov et stationnarité

Les deux propriétés suivantes sont des propriétés du processus et non plus seulement des trajectoires. Elles énoncent une certaine forme d’invariance de la marche au cours du temps. La première est une propriété d’absence de mémoire : la position future de la marche ne dépend que de sa position actuelle et pas de la trajectoire qui l’a amenée à cette position.

Proposition 6 (Markov) Pour tout $n\in\mathbb{N}$ et pour tous $(a_0,a_1,\ldots,a_{n+1})\in\mathbb{Z}^{n+2}$, on a

$$\begin{align*} \mathbb{P}(S_{n+1}=a_{n+1}& | S_n=a_n, S_{n-1}=a_{n-1},\ldots,S_1=a_1,S_0=a_0)\\ =\mathbb{P}(S_{n+1}=a_{n+1}& | S_n=a_n). \end{align*}$$

Preuve. Par définition des probabilités conditionnelles, on a

$$\begin{align*} \mathbb{P}(S_{n+1}=a_{n+1} &| S_n=a_n, S_{n-1}=a_{n-1},\ldots,S_1=a_1,S_0=a_0)\\ &=\frac{\mathbb{P}(S_{n+1}=a_{n+1}, S_n=a_n, S_{n-1}=a_{n-1},\ldots,S_1=a_1,S_0=a_0)}{\mathbb{P}(S_n=a_n, S_{n-1}=a_{n-1},\ldots,S_1=a_1,S_0=a_0)}\\ &=\frac{\mathbb{P}(X_{n+1}=a_{n+1}-a_n, S_n=a_n, S_{n-1}=a_{n-1},\ldots,S_1=a_1,S_0=a_0)}{\mathbb{P}(S_n=a_n, S_{n-1}=a_{n-1},\ldots,S_1=a_1,S_0=a_0)}, \end{align*}$$

puisque $S_{n+1}=S_n+X_{n+1}$. Remarquons maintenant que $X_{n+1}$ est indépendante de $X_1,\ldots, X_n$, donc de $S_0,\ldots,S_n$. On obtient alors

$$\begin{align*} \mathbb{P}(S_{n+1}=a_{n+1} &| S_n=a_n, S_{n-1}=a_{n-1},\ldots,S_1=a_1,S_0=a_0)\\ &=\frac{\mathbb{P}(X_{n+1}=a_{n+1}-a_n)\mathbb{P}(S_n=a_n, S_{n-1}=a_{n-1},\ldots,S_1=a_1,S_0=a_0)}{\mathbb{P}(S_n=a_n, S_{n-1}=a_{n-1},\ldots,S_1=a_1,S_0=a_0)}\\ &=\mathbb{P}(X_{n+1}=a_{n+1}-a_n). \end{align*}$$

Par ailleurs, par un raisonnement analogue on a

$$\begin{align*} \mathbb{P}(S_{n+1}=a_{n+1} | S_n=a_n) &=\frac{\mathbb{P}(S_{n+1}=a_{n+1},S_n=a_n)}{\mathbb{P}(S_n=a_n)}\\ &=\frac{\mathbb{P}(X_{n+1}=a_{n+1}-a_n,S_n=a_n)}{\mathbb{P}(S_n=a_n)}\\ &=\frac{\mathbb{P}(X_{n+1}=a_{n+1}-a_n)\mathbb{P}(S_n=a_n)}{\mathbb{P}(S_n=a_n)}\\ &=\mathbb{P}(X_{n+1}=a_{n+1}-a_n), \end{align*}$$

d’où le résultat.

Proposition 7 Pour tout $n > m$ entiers positifs $S_n-S_m$ est indépendant de $(S_0,S_1,\ldots, S_m)$.

Preuve. Comme les $(X_n)$ sont indépendantes, on a directement que $$S_n-S_m=\sum_{k=m+1}^nX_k,$$ qui est indépendant de $(S_0=x,S_1=x+X_1,\ldots, S_m=x+\sum_{k=1}^mX_k)$.

On a un résultat analogue à la propriété de Markov lorsqu’on regarde deux pas de temps plus éloignés.

Corollaire 3 Pour tout $n>m$ entiers positifs et pour tous $(a_0,a_1,\ldots,a_m,a_{n})\in\mathbb{Z}^{m+2}$, on a

$$\begin{align*} \mathbb{P}(S_{n}=a_{n}& | S_m=a_m, S_{m-1}=a_{m-1},\ldots,S_1=a_1,S_0=a_0)\\ =\mathbb{P}(S_{n}=a_{n}& | S_m=a_m). \end{align*}$$

Preuve. Par un raisonnement analogue à la preuve de la propriété de Markov, on obtient

$$\begin{align*} \mathbb{P}(S_{n}=a_{n}&| S_m=a_m, S_{m-1}=a_{m-1},\ldots,S_1=a_1,S_0=a_0)\\ &=\frac{\mathbb{P}(S_{n}=a_{n},S_m=a_m, S_{m-1}=a_{m-1},\ldots,S_1=a_1,S_0=a_0)}{\mathbb{P}(S_m=a_m, S_{m-1}=a_{m-1},\ldots,S_1=a_1,S_0=a_0)}\\ &=\frac{\mathbb{P}(S_{n}-S_m=a_{n}-a_m,S_m=a_m, S_{m-1}=a_{m-1},\ldots,S_1=a_1,S_0=a_0)}{\mathbb{P}(S_m=a_m, S_{m-1}=a_{m-1},\ldots,S_1=a_1,S_0=a_0)}\\ &=\frac{\mathbb{P}(S_{n}-S_m=a_{n}-a_m)\mathbb{P}(S_m=a_m, S_{m-1}=a_{m-1},\ldots,S_1=a_1,S_0=a_0)}{\mathbb{P}(S_m=a_m, S_{m-1}=a_{m-1},\ldots,S_1=a_1,S_0=a_0)}\\ &=\mathbb{P}(S_{n}-S_m=a_{n}-a_m)\\ &=\mathbb{P}(S_n=a_n|S_m=a_m), \end{align*}$$

en utilisant la propriété des accroissement indépendants.

La seconde propriété dite de stationnarité signifie qu’on peut changer l’origine du repère sans influence sur le comportement futur de la marche.

Proposition 8 (Stationnarité) Pour tout $n>m$ entiers positifs et $(a,b)\in\mathbb{Z}^2$, on a $$\mathbb{P}(S_n=b|S_m=a)=\mathbb{P}(S_{n-m}= b-a|S_0= 0).$$

Preuve. En utilisant l’indépendance des accroissements, on obtient

$$\begin{align*} \mathbb{P}(S_n=b|S_m=a) &=\frac{\mathbb{P}(S_n=b,S_m=a)}{\mathbb{P}(S_m=a)}\\ &=\frac{\mathbb{P}(S_n-S_m=b-a,S_m=a)}{\mathbb{P}(S_m=a)}\\ &=\frac{\mathbb{P}(S_n-S_m=b-a)\mathbb{P}(S_m=a)}{\mathbb{P}(S_m=a)}\\ &=\mathbb{P}(S_n-S_m=b-a)\\ &=\mathbb{P}(\sum_{k=m+1}^nX_k=b-a)\\ &=\mathbb{P}(\sum_{k=1}^{n-m}X_k=b-a)\\ &=\mathbb{P}(S_{n-m}=b-a|S_0=0), \end{align*}$$

car les $(X_n)$ sont indépendantes et de même loi.

Premier retour en $0$

On suppose maintenant que la marche part de $0$ : $S_0=0$ et on cherche à savoir si la marche reviendra en $0$ presque sûrement. Commençons par remarquer que si $S_n=0$ alors $n$ est nécessairement pair.

Proposition 9 Pour tout $n\in\mathbb{N}$, on a $$\mathbb{P}(S_{2n}=0)=\frac{1}{4^n}\binom{2n}{n}.$$

Preuve. Cette probabilité correspond au nombre de chemins de $(0,0)$ à $(2n,0)$ divisé par le nombre total de chemins de longueur $2n$, puisque tous les chemins sont équiprobables. On a donc directement $\mathbb{P}(S_{2n}=0)=\frac{\binom{2n}n}{4^n}$.

On s’intéresse maintenant au premier instant de retour en $0$. On le note $T_0$. Il s’agit donc de la variable aléatoire $$T_0=\inf\{n\geq 1; S_n=0\},$$ avec la convention que $\inf\emptyset= +\infty$. C’est donc une variable aléatoire discrète à valeurs dans $\mathbb{N}^*\cup\{+\infty\}$. On peut calculer explicitement la loi de $T_0$.

Proposition 10 Pour tout $n\in\mathbb{N}^*$, on a $$\mathbb{P}(T_0=2n)=\frac{(2n-2)!}{2^{2n-1}n!(n-1)!}.$$

Preuve. L’événement $(T_0= 2n)$ correspond à $(S_2\neq 0, \ldots,S_{2n-2}\neq 0,S_{2n}=0)$ puisqu’alors $2n$ est le premier temps où la marche retourne en $0$. En particulier, entre l’instant $0$ et l’instant $2n$ la marche ne change pas de signe, et garde le signe de $S_1$. Ainsi, on a $$\begin{align*} \mathbb{P}(T_0=2n)&=\mathbb{P}(S_1=1,S_2>0,\ldots,S_{2n-2}>0,S_{2n}=0)\\ &\quad+\mathbb{P}(S_1=-1,S_2<0,\ldots,S_{2n-2}<0,S_{2n}=0). \end{align*}$$ Par symétrie, ces deux probabilités sont égales. De plus, si $S_{2n-2}>0$ et $S_{2n}=0$ alors nécessairement on a $S_{2n-1}=1$. Ainsi il vient $$\begin{align*} {\mathbb{P}(T_0=2n)}\\ &=2\mathbb{P}(S_1=1,S_2>0,\ldots,S_{2n-2}>0,S_{2n-1}=1,S_{2n}=0)\\ &=2\mathbb{P}(S_{2n}=0|S_1=1,S_2>0,\ldots,S_{2n-2}>0,S_{2n-1}=1)\\ &\quad \times\mathbb{P}(S_1=1,S_2>0,\ldots,S_{2n-2}>0,S_{2n-1}=1)\\ &=2\mathbb{P}(S_{2n}=0|S_{2n-1}=1)\mathbb{P}(S_1=1,S_2>0,\ldots,S_{2n-2}>0,S_{2n-1}=1)\\ &=2\mathbb{P}(S_{1}=-1|S_0=0)\mathbb{P}(S_1=1,S_2>0,\ldots,S_{2n-2}>0,S_{2n-1}=1)\\ &=\mathbb{P}(S_1=1,S_2>0,\ldots,S_{2n-2}>0,S_{2n-1}=1), \end{align*}$$ en utilisant la propriété de Markov, la propriété de stationnarité puis le fait que $${\mathbb P}(S_1=-1|S_0=0) = {\mathbb P}(X_1=-1) = \frac{1}{2}.$$ Cette dernière probabilité correspond au nombre de chemins de $(1,1)$ à $(2n-1,1)$ ne touchant pas $0$ divisée par le nombre total de chemins de longueur $2n-1$. En utilisant le principe de réflexion, on obtient $$\begin{align*} \mathbb{P}(T_0=2n) &=\frac{\binom{2n-2}{n-1}-\binom{2n-2}{n}}{2^{2n-1}}\\ &=\frac{1}{2^{2n-1}}\left(\frac{(2n-2)!}{(n-1)!(n-1)!}-\frac{(2n-2)!}{n!(n-2)!}\right)\\ &=\frac{1}{2^{2n-1}}\frac{(2n-2)!}{(n-1)!(n-2)!}\left(\frac{1}{n-1}-\frac{1}{n}\right)\\ &=\frac{(2n-2)!}{2^{2n-1}n!(n-1)!}, \end{align*}$$ d’où le résultat.

Nous pouvons maintenant énoncer le résultat principal de cette partie.

Théorème 2 La marche aléatoire partant de $0$ revient en $0$ en temps fini avec probabilité $1$, $i.e.$ $$\mathbb{P}(T_0 < +\infty)=1.$$

Preuve. On a $\mathbb{P}(T_0<+\infty)=\sum_{n=1}^\infty\mathbb{P}(T_0=2n)$, il s’agit donc d’identifier la somme de cette série. Pour cela, on exprime différemment le probabilité de l’événement $(T_0=2n)$, en repartant de l’expression du nombre de chemins de $(1,1)$ à $(2n-1,1)$ ne touchant pas $0$ divisée par le nombre total de chemins de longueur $2n-1$. Ce nombre de chemins est égal à la différence entre le nombre de chemins de $(1,1)$ à $(2n-1,1)$ et le nombre de chemins de $(1,1)$ à $(2n-1,-1)$ d’après le principe de réflexion. On obtient ainsi :

$$\begin{align*} {\mathbb{P}(T_0=2n)} &=\mathbb{P}(S_1=1, S_{2n-1}=1)\\ & \qquad -\mathbb{P}(S_1=1, S_{2n-1}=-1)\\ &=\mathbb{P}(S_{2n-1}=1|S_1=1)\mathbb{P}(S_1=1)\\ & \qquad -\mathbb{P}(S_{2n-1}=-1|S_1=1)\mathbb{P}(S_1=1)\\ &=\frac{1}{2}\mathbb{P}(S_{2n-2}=0|S_0=0)-\frac{1}{2}\mathbb{P}(S_{2n-2}=-2|S_0=0)\\ &=\frac{1}{2}\mathbb{P}(S_{2n-2}=0)-\frac{1}{2}\mathbb{P}(S_{2n-2}=-2), \end{align*}$$

par la propriété de stationnarité et puisque $S_0=0$. Par ailleurs, on a

$$\begin{align*} {\mathbb{P}(S_{2n}=0)} &=\mathbb{P}(S_{2n}=0, S_{2n-2} =-2)\\ & \qquad +\mathbb{P}(S_{2n}=0, S_{2n-2}=0) +\mathbb{P}(S_{2n}=0, S_{2n-2}=2)\\ &=2\mathbb{P}(S_{2n}=0, S_{2n-2}=-2)+\mathbb{P}(S_{2n}=0, S_{2n-2}=0), \end{align*}$$

par symétrie. Il vient

$$\begin{align*} {\mathbb{P}(S_{2n}=0)} & =2\mathbb{P}(S_{2n}=0|S_{2n-2}=-2)\mathbb{P}(S_{2n-2}=-2)\\ & \qquad+\mathbb{P}(S_{2n}=0|S_{2n-2}=0)\mathbb{P}(S_{2n-2}=0)\\ &=2\mathbb{P}(S_2=2|S_0=0)\mathbb{P}(S_{2n-2}=-2)\\ & \qquad+\mathbb{P}(S_2=0|S_0=0)\mathbb{P}(S_{2n-2}=0)\\ &=2\frac{1}{4}\mathbb{P}(S_{2n-2}=-2)+\frac{1}{2}\mathbb{P}(S_{2n-2}=0)\\ &=\frac{1}{2}\mathbb{P}(S_{2n-2}=-2)+\frac{1}{2}\mathbb{P}(S_{2n-2}=0), \end{align*}$$

où on a utilisé le fait que

$$\begin{align*} \mathbb{P}(S_2=0|S_0=0)& = \mathbb{P}(X_1 + X_2 = 0) \\ &= \mathbb{P}(X_1 = -1, X_2= 1)+ \mathbb{P}(X_1 = 1, X_2= -1)\\ &=\mathbb{P}(X_1 = -1) \mathbb{P}( X_2= 1)+ \mathbb{P}(X_1 = 1)\mathbb{P}( X_2= -1) \\ &=\frac{1}{2}. \end{align*}$$

Donc on a $\mathbb{P}(S_{2n-2}=-2)=2\mathbb{P}(S_{2n}=0)-\mathbb{P}(S_{2n-2}=0)$.

Revenons maintenant à $T_0$. On obtient

$$\begin{align*} \mathbb{P}(T_0=2n) &=\frac{1}{2}\mathbb{P}(S_{2n-2}=0)-\frac{1}{2}\mathbb{P}(S_{2n-2}=-2)\\ &=\frac{1}{2}\mathbb{P}(S_{2n-2}=0)-\mathbb{P}(S_{2n}=0)+\frac{1}{2}\mathbb{P}(S_{2n-2}=0)\\ &=\mathbb{P}(S_{2n-2}=0)-\mathbb{P}(S_{2n}=0). \end{align*}$$

Ainsi, la probabilité de l’événement $(T_0= +\infty)$ peut s’écrire à l’aide d’une somme télescopique :

$$\begin{align*} \mathbb{P}(T_0=+\infty) &=1-\sum_{n=1}^\infty\mathbb{P}(T_0=2n)\\ &=1-\lim_{N\to\infty}\sum_{n=1}^N\mathbb{P}(T_0=2n)\\ &=1-\lim_{N\to\infty}\sum_{n=1}^N\left(\mathbb{P}(S_{2n-2}=0)-\mathbb{P}(S_{2n}=0)\right)\\ &=1-\lim_{N\to\infty}\left(\mathbb{P}(S_0=0)-\mathbb{P}(S_{2N}=0)\right)\\ &=\lim_{N\to\infty}\mathbb{P}(S_{2N}=0)\\ &=\lim_{N\to\infty}\frac{1}{4^N}\binom{2N}{N}. \end{align*}$$

En utilisant la formule de Stirling¹, on obtient l’équivalence

¹ $n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$ quand $n\to +\infty$

$$\begin{align*} \frac{1}{4^N}\binom{2N}{N} &= \frac{1}{4^N}\frac{(2N)!}{N!N!} \sim \frac{1}{4^N}\frac{(2N)^{2N}\sqrt{4\pi N}e^{-2N}}{(N^{N}\sqrt{2\pi N}e^{-N})^2} = \frac{1}{\sqrt{\pi N}}, \end{align*}$$

donc on a bien $\mathbb{P}(T_0=+\infty)=0$.

Premier passage en $a\neq 0$

On peut obtenir par une méthode similaire la loi du temps d’atteinte de n’importe quel autre point. Soit $a\in\mathbb{Z}^*$. Le temps d’atteinte de $a$ est la variable aléatoire $$T_a=\inf\{n\geq 1; S_n=a\}.$$

Théorème 3 La marche aléatoire partant de $0$ atteint tout état $a\in\mathbb{Z}$ en temps fini avec probabilité $1$. Plus précisément, si $a\neq 0$, on a $\mathbb{P}(T_a=n)=0$ si $n$ et $a$ n’ont pas la même parité ou si $|a|>n$, et sinon $$\mathbb{P}(T_a=n)=\frac{|a|}{n2^n}\binom{n}{\frac{n+a}{2}}.$$

Preuve. On suit les mêmes étapes que ce qu’on a fait pour $T_0$. Les contraintes de parité et de longueur de chemin ont déjà été vues. Si $n$ et $a$ ont la même parité et que $|a|>n$, alors l’événement $(T_a= n)$ correspond à $(S_1\neq a, \ldots,S_{n-1}\neq a,S_{n}=a)$ puisqu’alors $n$ est le premier temps où la marche atteint $a$. Supposons sans perte de généralité que $a>0$. Donc la probabilité $\mathbb{P}(T_a= n)$ est égale au nombre de chemins de $(0,0)$ à $(n,a)$ ne touchant pas $a$ avant $n$ divisée par le nombre total de chemins de longueur $n$. 0r, ce nombre de chemin est égal

• au nombre de chemins de $(0,0)$ à $(n-1,a-1)$ ne touchant pas $a$
• au nombre de chemins de $(0,0)$ à $(n-1,a-1)$ - le nombre de chemins de $(0,0)$ à $(n-1,a-1)$ touchant $a$
• au nombre de chemins de $(0,0)$ à $(n-1,a-1)$ - le nombre de chemins de $(0,-a)$ à $(n-1,-1)$ touchant $0$
• au nombre de chemins de $(0,0)$ à $(n-1,a-1)$ - le nombre de chemins de $(0,-a)$ à $(n-1,1)$
• au nombre de chemins de $(0,0)$ à $(n-1,a-1)$ - le nombre de chemins de $(0,0)$ à $(n-1,a+1)$

Ainsi, on a $$\begin{align*} \mathbb{P}(T_a=n) &=\frac{\binom{n-1}{\frac{n-1}{2}+\frac{a-1}{2}}-\binom{n-1}{\frac{n-1}{2}+\frac{1+a}{2}}}{2^{n}}\\ &=\frac{1}{2^{n}}\left(\frac{(n-1)!}{(\frac{n+a-2}{2})!(\frac{n-a}{2})!}-\frac{(n-1)!}{(\frac{n+a}{2})!(\frac{n-a-2}{2})!}\right)\\ &=\frac{1}{2^n}\frac{(n-1)!}{(\frac{n+a-2}{2})!(\frac{n-a-2}{2})!}\left(\frac{1}{\frac{n-a}{2}}-\frac{1}{\frac{n+a}{2}}\right)\\ &=\frac{a}{2^n}\frac{(n-1)!}{(\frac{n+a}{2})!(\frac{n-a}{2})!}\\ &=\frac{a}{n2^n}\binom{n}{\frac{n+a}{2}} \end{align*}$$ d’où le résultat.

Nous démontrerons dans la partie suivante que $\mathbb{P}(T_a<+\infty)=1$.

En particulier, la marche partant de $0$ va atteindre tout point de $\mathbb{Z}$ avec probabilité $1$, donc elle est presque sûrement non bornée.

La ruine de la joueuse

On s’intéresse maintenant à un problème de ruine. Une joueuse dispose d’un capital initial $x$. Elle joue à pile ou face avec une pièce équilibrée, et gagne $1$ si elle obtient pile, perd $1$ si elle obtient face. La joueuse s’est fixé un objectif de gain $a\geq x$ et un plancher de perte $b\leq x$. Elle joue jusqu’à ce que sa richesse atteigne $a$ ou $b$.

On modélise la fortune de la joueuse par une marche aléatoire $(S_n)_{n\in\mathbb{N}}$, avec $S_0=x$ et $S_n=S_0+\sum_{k=1}^n X_k$, où $X_k$ représente le gain du $k$-ème tirage.

On sait qu’atteindre $a$ ou $b$ partant de $x$ est équivalent à atteindre $a-x$ ou $b-x$ partant de $0$. Le jeu s’arrête donc presque sûrement au bout d’un temps fini.

On note $p_x$ la probabilité de ruine partant d’un capital initial $x$, et $R_x$ l’événement être ruinée en partant de $x$, c’est-à-dire $$p_x=\mathbb{P}(T_b < T_a)= \mathbb{P}(R_x).$$ On peut remarquer directement que $p_a=0$ et $p_b=1$ puisque dans ces deux situations, le jeu ne démarre pas, la ruine est impossible dans le premier cas, et certaine dans le second.

Nous allons obtenir une formule de récurrence sur les $p_x$. Si $b<x<a$, on a par la formule des probabilités totales

$$\begin{align*} p_x&=\mathbb{P}(R_x)\\ &=\mathbb{P}(R_x|S_1=x+1)\mathbb{P}(S_1=x+1)+\mathbb{P}(R_x|S_1=x-1)\mathbb{P}(S_1=x-1)\\ &=\mathbb{P}(R_{x+1})\frac{1}{2}+\mathbb{P}(R_{x-1})\frac{1}{2}, \end{align*}$$

en utilisant la stationnarité. On obtient ainsi que $(p_x)_{a<x< b}$ est une suite récurrente linéaire^[Une suite $(u_n)_{n \in {\mathbb N}}$ est dite récurrente linéaire d’ordre $2$ s’il existe $(a,b)\in\mathbb{R}\times\mathbb{R}^*$ tel que, pour entier $n$, on a

$$u_{n+2} = a u_{n+1} + b u_n .$$ Le polynôme $X^2 - a X + b$ est appelé le polynôme caractéristique de la suite. Si le polynôme caractéristique admet deux racines simples $r_1$ et $r_2$, alors il existe deux réels $\alpha$ et $\beta$ tels que pour tout entier $n$, $$u_n = \alpha r_1^n + \beta r_2^n.$$ Si le polynôme caractéristique admet une racine double $r$, alors il existe deux réels $\alpha$ et $\beta$ tels que pour tout entier $n$, $$u_n = (\alpha + \beta n) r^n.$$] d’ordre $2$, de polynôme caractéristique $X^2-2X+1=(X-1)^2$. Ainsi $p_x=\alpha +\beta x$. On identifie $\alpha$ et $\beta$ avec les conditions extrémales $p_a=0$ et $p_b=1$

$$\begin{align*} \left\{\begin{array}{rcl} p_a=0&=&\alpha+\beta a\\ p_b=1&=&\alpha+\beta b \end{array} \right. \Leftrightarrow \left\{\begin{array}{rcl} \alpha&=&\frac{a}{a-b},\\ \beta&=&-\frac{1}{a-b}. \end{array} \right. \end{align*}$$

Ainsi la probabilité de ruine partant de $x$ vaut $$p_x=\frac{a-x}{a-b}.$$

Un calcul analogue en cherchant la probabilité $q_x$ de faire fortune partant d’une richesse $x$ conduit à $q_x=\frac{x-b}{a-b}=1-p_x$, autrement dit il n’y a pas d’autre issue possible : le jeu va s’arrêter avec probabilité $1$. Si on fait tendre $b$ vers $-\infty$, on trouve que $\mathbb{P}(T_a<\infty |x_0=a)=1$. Donc partant de n’importe quel point, la marche atteindra n’importe quel autre point avec probabilité $1$.

On peut montrer avec un raisonnement analogue que la durée du jeu $d_x$ partant de $x$ est solution de l’équation récurrente linéaire avec second membre² $$d_x=\frac{1}{2}(d_{x+1}+d_{x-1})+1,$$ avec $d_a=d_b=0$.

² Une suite $(u_n)_{n \in {\mathbb N}}$ est dite récurrente linéaire d’ordre $2$ avec second membre s’il existe $(a,b) \in {\mathbb R} \times {\mathbb R}^*$ et une fonction $f$ à valeurs dans ${\mathbb R}$ tels que, pour entier $n$, on a $$u_{n+2} = a u_{n+1} + b u_n + f(n).$$ L’équation $\displaystyle u_{n+2} = a u_{n+1} + b u_n$ s’appelle alors l’équation homogène associée. Les solutions de l’équation avec second membre sont la somme de la solution générique de l’équation homogène et d’une solution particulière de l’équation avec second membre.

En effet, il est clair que $d_a=d_b=0$, et si $a<x<b$, alors on a $d_x=\mathbb{E}(T_a\wedge T_b)$. Attention, la variable aléatoire $T_a\wedge T_b$ est à valeurs dans $\mathbb{N}\cup\{+\infty\}$. Si $\mathbb{P}(T_a\wedge T_b=+\infty|S_0=x)>0$, alors $\mathbb{E}(T_a\wedge T_b)=+\infty$. Par ailleurs, partant de $x+1$, on a

$$\begin{align*} \mathbb{P}(T_a\wedge T_b=+\infty &|S_0=x+1)\\ & \geq \mathbb{P}(T_a\wedge T_b=+\infty, S_1=x|S_0=x+1)\\ &= \mathbb{P}(T_a\wedge T_b=+\infty|S_1=x,S_0=x+1)\mathbb{P}(S_1=x|S_0=x+1)\\ &=\frac{1}{2}\mathbb{P}(T_a\wedge T_b=+\infty|S_0=x) \enspace, \end{align*}$$

par les propriétés de Markov et de stationnarité. Donc $\mathbb{P}(T_a\wedge T_b=+\infty|S_0=x+1)>0$. Ainsi, les membres de gauche et de droite de l’équation $d_x=\frac{1}{2}(d_{x+1}+d_{x-1})+1$ valent tous les deux $+\infty$, et l’égalité est vraie. On montrerait de même que $\mathbb{P}(T_a\wedge T_b=+\infty|S_0=x)>0$ implique $\mathbb{P}(T_a\wedge T_b=+\infty|S_0=x-1)>0$, et par contraposée et décalage d’indices que $\mathbb{P}(T_a\wedge T_b=+\infty|S_0=x)=0$ implique $\mathbb{P}(T_a\wedge T_b=+\infty|S_0=x+1)=\mathbb{P}(T_a\wedge T_b=+\infty|S_0=x-1)=0$. Plaçons nous dans ce dernier cas. On a donc

$$\begin{align*} d_x&=\mathbb{E}(T_a\wedge T_b)\\ &=\sum_{k=1}^\infty k \mathbb{P}(T_a\wedge T_b=k|S_0=x)\\ &=\sum_{k=1}^\infty k \big(\mathbb{P}(T_a\wedge T_b=k|S_1=x+1)\mathbb{P}(S_1=x+1) \\ &\qquad\qquad +\mathbb{P}(T_a\wedge T_b=k|S_1=x-1)\mathbb{P}(S_1=x-1)\big)\\ &=\frac{1}{2}\sum_{k=1}^\infty k \mathbb{P}(T_a\wedge T_b=k-1|S_0=x+1)+\frac{1}{2}\sum_{k=1}^\infty k\mathbb{P}(T_a\wedge T_b=k-1|S_0=x-1)\\ &=\frac{1}{2}\sum_{j=0}^\infty (j+1) \mathbb{P}(T_a\wedge T_b=j|S_0=x+1)+\frac{1}{2}\sum_{j=0}^\infty (j+1)\mathbb{P}(T_a\wedge T_b=j|S_0=x-1)\\ &=\frac{1}{2}\sum_{j=0}^\infty j \mathbb{P}(T_a\wedge T_b=j|S_0=x+1)+\frac{1}{2}\sum_{j=0}^\infty j\mathbb{P}(T_a\wedge T_b=j|S_0=x-1)+1\\ &=1+\frac{1}{2}\mathbb{E}(T_a\wedge T_b|S_0=x+1)+\frac{1}{2}\mathbb{E}(T_a\wedge T_b|S_0=x-1)\\ &=1+\frac{1}{2}(d_{x+1}+d_{x-1}). \end{align*}$$

Cherchons une solution particulière sous la forme $cn^2$ (puisque les constantes et les multiples de $n$ sont solutions de l’équation homogène) :

$$\begin{align*} cn^2=\frac{1}{2}(c(n+1)^2+c(n-1)^2)+1 &\Leftrightarrow cn^2=\frac{1}{2}(cn^2+c+2cn+cn^2+c-2cn)+1\\ &\Leftrightarrow cn^2=cn^2+c+1\\ &\Leftrightarrow c=-1. \end{align*}$$

Ansi, $d$ est la somme d’une solution homogène et d’une solution particulière, donc $$d_x=\alpha +\beta x-x^2.$$ En utilisant $d_a=d_b=0$, on trouve $\alpha$ et $\beta$

$$\begin{align*} \left\{\begin{array}{rcl} d_a=0&=&\alpha+\beta a-a^2\\ d_b=0&=&\alpha+\beta b-b^2 \end{array} \right. \Leftrightarrow \left\{\begin{array}{rcl} \alpha&=-ab,\\ \beta&=a+b. \end{array} \right. \end{align*}$$

Finalement, on obtient que $$d_x=-ab+x(a+b)-x^2.$$

En particulier, si $x=0$ et $b$ tend vers $-\infty$, on obtient que $\mathbb{E}[T_a]=+\infty$. On sait que la marche partant de $0$ atteindra $a$ presque sûrement en temps fini, cependant ce temps est en moyenne infini.

De la marche aléatoire vers le mouvement brownien

On s’intéresse maintenant à une autre forme de comportement asymptotique de la marche aléatoire. Nous allons la renormaliser pour la contraindre à rester dans l’intervalle de temps $[0,1]$. Pour cela, pour tout $N\in\mathbb{N}^*$, on pose $$B^N_t =\frac{1}{\sqrt{N}} S_{\lfloor Nt \rfloor} = \frac{1}{\sqrt{N}} \sum_{k=1}^{\lfloor Nt \rfloor} X_k.$$

Alors la suite $(B^N_t)$ converge en loi lorsque $N$ tend vers l’infini, et c’est également le cas lorsqu’on prend plusieurs temps $t_i$.

Proposition 11 Pour tous $t_0=0<t_1 <\dots< t_p$, le vecteur $(B^N_{t_1},\dots,B^N_{t_p})$ converge en loi vers un vecteur $(B_{t_1},\dots,B_{t_p})$ tel que pour tout $i \in\{1,\dots,p\}$, $B_{t_{i}}-B_{t_{i-1}}$ est indépendant de $B_{t_{i-1}}$ et suit une loi normale $\mathcal{N}(0, t_i - t_{i-1} )$

Preuve. On a $$B^N_{t_i} - B^N_{t_{i-1}} =\frac{1}{\sqrt{N}} S_{\lfloor Nt \rfloor} = \frac{1}{\sqrt{N}} \sum_{k=\lfloor N t_{i-1} \rfloor + 1}^{\lfloor N t_i \rfloor} X_k$$ donc les accroissements du vecteur $(B^N_{t_1},\dots,B^N_{t_p})$ sont indépendant. Il suffit maintenant de montrer qu’ils convergent vers la loi normale. On a $$B^N_{t_i} - B^N_{t_{i-1}} = \sqrt{\frac{\lfloor N t_i \rfloor - \lfloor N t_{i-1} \rfloor }{N}} \frac{1}{\sqrt{\lfloor N t_i \rfloor - \lfloor N t_{i-1} \rfloor }} \sum_{k=\lfloor N t_{i-1} \rfloor + 1}^{\lfloor N t_i \rfloor} X_k \to \sqrt{t_i - t_{i-1}} \mathcal{N}(0,1),$$ par le théorème central limite appliqué à la suite $(X_k)$.

Ce résultat permet de poser la définition suivante.

Définition 3 (Mouvement Brownien) On appelle mouvement Brownien standard, tout processus $(B_t)_{t\geq 0}$ satisfaisant les trois points suivants

1. $B_0=0$,
2. $\forall t\geq s$, $B_{t} - B_s$ indepandant de $(B_r)_{r \leq s}$,
3. $\forall t\geq s$, $B_{t} - B_s \sim \mathcal{N}(0, t-s)$.

Le théorème précédent ne donne pas l’existence d’un tel processus, mais si un tel processus existe, il donne la convergence des lois marginales fini-dimensionnelles de la marche aléatoire renormalisée vers les lois marginales fini-dimensionnelles du mouvement Brownien. On admettra qu’il existe bien un mouvement Brownien. On peut montrer que la marche aléatoire converge pour la norme infinie vers le mouvement Brownien dans l’espace des variables aléatoires à valeurs dans les fonctions continues de $[0,1]$ dans $\mathbb{R}$. Ce résultat est connu sous le nom de théorème de Donsker. Pour simuler un mouvement Brownien, on simule en fait une marche aléatoire et on la renormalise comme ci-dessus avec $N$ assez grand.