 \section{TD Probabilit\'es : Système de transmission Aloha}

Tout ce td est tir\'e de $\cite{Br}$.

\dexer{Exercice 2.7.2 de $\cite{Br}$ non corrig\'e}\\
Soit $(X_n)_n$ une chaîne de Markov homogène canonique sur $E$, dénombrable. Soit $F$ un sous-ensemble fini de l'espace des états $E$. Soit $\tau_{1}=\inf\{n\geq 1 | X_{n}\in F\}, \tau_{2}=\inf\{n\geq \tau_{1}+1 | X_{n}\in F\}, \ldots$ le temps successifs de retour dans $F$. On suppose que pour tout $j\in F$, $\Pro_{j}(\tau_{1}<+\infty)=1$. Alors\\
1. Pour tout $n$, $\tau_{n}$ est fini presque sûrement.\\
2. Le processus $(Y_n)_n =(X_{\tau_{n}})_n$ est une chaîne de Markov homogène sur $F$.\\
\fexer

\dsolution
\newline
On travaille avec la cha\^ine canonique et on remarque que:
$$\tau_{n}=\tau_{n-1}+\tau_{1}\circ\theta_{\tau_{n-1}}\; \; \mbox{si $\tau_{n-1}<+\infty$ \; et $+\infty$ sinon}$$
La propri\'et\'e forte de Markov permet alors d'\'ecrire, pour une fonction $\Phi$ born\'ee et pour $x \in F$:
$$\E_{x}\left[1_{\{\tau_{n}<+\infty\}}\Phi(X_{\tau_{n}})|{\cal F}_{\tau_{n-1}}\right]=1_{\{\tau_{n-1}<+\infty\}}\E_{X_{\tau_{n-1}}}(\Phi(X_{\tau_{1}}))$$
Appliquant ceci \`a $\Phi=1$, on a $\Pro_{x}(\tau_{n}<+\infty)=\Pro_{x}(\tau_{n-1}<+\infty)=\ldots=\Pro_{x}(\tau_{1}<+\infty)=1$ ce qui \'etablit la premi\`ere affirmation.\\
Pour la deuxi\`eme, il suffit de remarquer que l'on peut maintenant \^oter les indicatrices et en posant ${\cal G}_{n}={\cal F}_{\tau_{n}}$, on a :
$$\E_{x}(\Phi(Y_{n})|{\cal G}_{n+1})=\E_{Y_{n-1}}(\Phi(Y_{1}))$$
ce qui prouve que $Y$ est bien une ${\cal G}_{n}$ cha\^ine de Markov homog\`ene sur $F$.\\
\fsolution

\subsection{Description du mod\`ele}

On modélise un système de transmission satellitaire de la manière suivante. Des utilisateurs transmettent des messages dont la taille est born\'ee par une certaine constante $K$ à travers un canal à des moments $t_n, n\in {\mathbb N}$ fixés par avance tels que $t_{n+1}-t_{n} \geq K$. Dans la suite, on prendra $t_{n}=n$ et $K=1$. On suppose de plus que dès que deux messages sont émis au même moment, ils s'annulent et l'on doit recommencer (un seul message peut-être émis à la fois). D'autre part, l'utilisateur sait si son message a été transmis ou pas et décide donc le cas échéant de tenter de le renvoyer avec une certaine probabilité $\nu \in (0,1)$, le message passant alors dans un état dit ``semi-bloqué''. Un message émis pour la première fois (c'est-à-dire non semi-bloqué) arrivant alors qu'aucun autre message ``semi-bloqué'' ne tente de réemettre est immédiatement transmis. Sinon, il passe dans l'état de message ``semi-bloqué''. Ces règles montrent en particulier que deux messages émis pour la première fois mais arrivant en même temps deviendront aussitôt des mesages semi-bloqués. Les trois règles fondamentales à retenir sont donc les suivantes :\\
1. Les transmissions et les retransmissions ne peuvent se faire qu'aux instants $1,2,\ldots$.\\
2. Tous les messages semi-bloqués (c'est-à-dire ceux ayant déjà essayé d'être transmis mais sans succès) tentent de retransmettre indépendament des autres avec probabilité $\nu$ \`a chaque instant. On dit que la retransmission se fait selon une loi de Bernoulli.\\
3. Les messages émis pour la première fois, s'ils arrivent alors que le canal est libre (c'est-à-dire pas de messages semi-bloqués en train d'essayer de retransmettre) sont immédiatement transmis.\\

On notera $X_{n}$ le nombre de messsages semi-bloqués à l'instant $n$ et $A_{n}$ est le nombre de messages qui arrivent à l'instant $n$ (ce sont donc des messages qui tentent d'être émis pour la première fois). On suppose que $(A_n)_{n\geq 0}$ est i.i.d. telle que :
$$\Pro[A_n =i]=a_i \;\;, \;\; \lambda=\E(A_n)$$
On supposera de plus que $a_0 +a_1 \in (0,1)$ et $a_0>0$. $\lambda$ est appelée l'intensité du traffic.\\

Ce système de transmission est connu sous le nom de système ALOHA.

\subsection{Instabilité de ALOHA}

\quest 1) Expliquer pourquoi si $X_{n}=k$, alors la probabilité que $i$ parmis eux tentent de réémettre est donnée par:
$$b_{i}(k)=C_{k}^{i}\nu^{i}(1-\nu)^{k-i}$$

\quest 2) La modélisation mathématique de ce système de transmission consiste à voir $(X_n)_n$ comme une chaîne de Markov à valeurs dans ${\mathbb N}$ avec pour matrice de transition:\\
\begin{equation*}
\begin{split}
&p_{i,j}=b_{1}(i)a_{0} \; \mbox{ si $j=i-1$,}\\
&p_{i,j}=[1-b_{1}(i)]a_{0}+b_{0}(i)a_{1} \; \mbox{si $j=i$,}\\
&p_{i,j}=[1-b_{0}(i)]a_{1} \; \mbox{si $j=i+1$,}\\
&p_{i,j}=a_{j-i} \; \mbox{si $j \geq i+2$.}
\end{split}
\end{equation*}

\subquest a) Expliquer pourquoi la probabilité de transition est celle donnée ci-dessus.

\subquest b) Montrer que cette chaîne est irréductible.

\quest 3) Le but de la question est de prouver que le système ALOHA est instable dans le sens suivant : ``la chaîne n'est pas récurrente positive''.

\subquest a) Expliquer pourquoi ce critère est mathématiquement acceptable. Quels autres critères pourrait on demander ?

\subquest b) Montrer que l'instabilité est la négation de l'existence d'une distribution stationnaire $\pi$.

\quest 4) Montrer que si une distribution stationnaire pour la chaîne existait alors elle devrait satisfaire:
\begin{eqnarray*}
\pi (i)
&=&\pi (i)\{[1-b_1(i)]a_o + b_{0}(i)a_1\}+\pi(i-1)[1-b_{0}(i-1)]a_1\\
&+&\pi(i+1)b_{1}(i+1)a_0 + \sum_{l=2}^{\infty}\pi(i-l)a_l
\end{eqnarray*}
avec $\pi(j)=0$ si $j<0$.

\quest 5) On pose $P_{N}=\sum_{i=0}^{N}\pi(i)$.

\subquest a)  Montrer que
$$P_{N}(1-a_{0})=\pi(N)b_{0}(N)a_1 +\pi(N+1)b_{1}(N+1)a_0 + \sum_{l=1}^{N}a_{l}P_{N-l}$$

\subquest b) Montrer que
$$\sum_{l=1}^{N}a_{l}P_{N-l}\leq P_{N-1}(1-a_0)$$

\subquest c) En déduire
$$\cfrac{\pi (N+1)}{\pi (N)}\geq \cfrac{(1-a_0)-(1-\nu)^{N}a_1}{(N+1)\nu(1-\nu)^{N}a_{0}}$$

\quest 6) Conclure.

\subsection{Quelques outils théoriques : fonctions de Liapounov}

Nous allons tenter de résoudre ce problème d'instabilité. Commençons par donner un critère de récurrence positive plus maniable que l'existence d'une probabilité stationnaire.

\begin{lemf}
Soit $(X_n)_n$ une chaîne de Markov irréductible homogène par rapport à sa filtration naturelle $({\cal F}_{n})_n$. Soit $F$ un sous-ensemble fini de l'espace des états $E$. Soit $\tau=\inf\{n\geq 1 | X_{n}\in F\}$ le premier temps de retour dans $F$. Si pour tout $j\in F$, $\E_{j}[\tau]<+\infty$ alors la chaîne est récurrente positive.
\end{lemf}

\quest 1) On définit comme dans l'exercice les temps successifs de retour en $F$ de $X$, $\tau_n$, et la chaîne de Markov $Y_n=X_{\tau_n}$. Montrer que $Y_n$ est irréductible.

\quest 2) En déduire que $Y$ est positive récurrente.

\quest 3) On pose $T_i$ le premier temps de retour en $i\in F$ de la chaîne $X$ et $\tilde{T}_{i}$ celui de la chaîne $Y$. La question 2) permet d'écrire $\E_i({\tilde{T}}_i)<+\infty$. On pose alors $S_0=\tau_1$ et $S_k=\tau_{k+1}-\tau_{k}$ pour $k\geq 1$. Montrer que
$$T_i=\sum_{k=0}^{\infty}S_{k}1_{\{k<{\tilde T}_i\}}$$

\quest 4) En déduire $\E_{i}[T_i]=\sum_{k=0}^{\infty}\E_{i}[S_{k}1_{\{k<{\tilde T}_i\}}]$.

\quest 5)

\subquest a) Montrer que $\{k<{\tilde T}_i\} \in {\cal F}_{\tau_k}$.

\subquest b) En utilisant la propriété forte de Markov, montrer que pour tout $l\in F$, on a
$$\E_{i}[S_{k}1_{\{k<{\tilde T}_i\}}1_{\{X_{\tau_{k}}=l\}}]=\E_{i}[S_{k}|X_{\tau_{k}}=l]\Pro_{i}(k<{\tilde T}_i, X_{\tau_{k}}=l)$$

\quest 6)

\subquest a) Montrer que $\E_{i}[S_{k}|X_{\tau_{k}}=l]=\E_{l}[\tau]$.

\subquest b) En déduire
$$\E_{i}(T_{i})\leq \left(\sup_{l\in F}\E_{l}(\tau)\right)\sum_{k=0}^{\infty}\Pro_{i}({\tilde T}_{i}>k)=\left(\sup_{l\in F}\E_{l}(\tau)\right)\E_{i}({\tilde T}_{i})<+\infty$$
et conclure.

\begin{thf}\textbf{Théorème de Foster}\\
Soit $P$ une matrice de transition irréductible sur un espace d'état dénombrable $E$ associée à une chaîne de Markov $X$. On suppose qu'il existe une fonction $h: E \rightarrow {\mathbb R}$ telle que $\inf_{i}h(i)>-\infty$ et v\'erifiant :
$$\sum_{k\in E}p_{ik}h(k)=\E_{i}(h(X_{1}))<+\infty \; \; \mbox{pour tout $i\in F$, }$$
$$\sum_{k\in E}p_{ik}h(k)=\E_{i}(h(X_{1}))\leq h(i)-\epsilon \; \; \mbox{pour tout $i\notin F$, }$$
pour un $\epsilon >0$ et un ensemble fini $F$.
\end{thf}

Prouvons ce théorème.\\

\quest 1) Montrer que l'on peut se ramener au cas où $h\geq 0$.

\quest 2) On appelle $\tau=\inf\{n\geq 1 | X_{n}\in F\}$ le premier temps de retour dans $F$ et $\{{\cal F}_n\}_{n}$ la filtration naturelle associée à $X$. On définit $Y_n =h(X_n) 1_{\{n<\tau\}}$.

\subquest a) Montrer que l'on a
$$\E_{i}(Y_{n+1}|{\cal F}_{n})=\E_{i}[Y_{n+1}1_{\{n<\tau\}}|{\cal F}_{n}]+\E_{i}[Y_{n+1}1_{\{n\geq\tau\}}|{\cal F}_{n}]$$
\subquest b) Puis
$$\E_{i}(Y_{n+1}|{\cal F}_{n})=\E_{i}[h(X_{n+1})1_{\{n<\tau\}}|{\cal F}_{n}]=1_{\{n<\tau\}}\E_{i}[h(X_{n+1})|{\cal F}_{n}]$$
\subquest c) Et enfin
$$\E_{i}(Y_{n+1}|{\cal F}_{n})\leq 1_{\{n<\tau\}}h(X_n)-\epsilon 1_{\{n<\tau\}}$$

\quest 3)

\subquest a) Montrer que $\sum_{k=0}^{\infty}\Pro_{i}(\tau>k)=\E_{i}(\tau)$.

\subquest b) Déduire de la question 2c) l'inégalité suivante
$$0\leq \E_{i}(Y_{n+1})\leq \E_{i}(Y_{n})-\epsilon\Pro(\tau >n)$$

\quest 4) En remarquant que $Y$ est positive, montrer
$$\E_{i}(\tau)\leq \epsilon^{-1} h(i)<+\infty \; \; \mbox{pour $i\notin F$}$$

\quest 5) Si $j\in F$, montrer en utilisant la propriété forte de Markov que $$\E_{j}[\tau]= 1+\sum_{i\notin F}p_{ji}\E_{i}[\tau]$$

\quest 6) Déduire de 4) et 5) que si $j\in F$, alors $\E_{j}(\tau)<+\infty$. 

\quest 7) Utiliser le lemme pr\'ec\'edent et conclure.

\quest Ceci termine la preuve du théorème.

\begin{corf}\textbf{Lemme de Pake}\\
Soit $(X_n)_n$ une chaîne de Markov irréductible sur $\mathbb N$ telle que pour tout $n\geq 0$ et tout $i \in E$,
$$\E [X_{n+1}|X_{n=i}]<+\infty$$
et
$$\limsup_{i\rightarrow \infty}\E [X_{n+1}-X_{n}|X_{n}=i]<0$$
Alors $(X_n)_n$ est récurrente positive.\\
\end{corf}

Appliquer le théorème de Foster avec $2\epsilon=-\limsup_{i\rightarrow \infty}\E [X_{n+1}-X_{n}|X_{n}=i]$,$h(i)=i$ et $F=\{i;i\leq i_{o}\}$ où $i_0$ est un entier suffisament large.

\begin{remf}
La fonction $h$ dans le théorème de Foster est appelée une fonction de Lyapounov car elle joue le même rôle que celui joué par les fonctions de Lyapounov ``classiques'' dans la théorie de la stabilité pour les équations différentielles. $h$ a en effet tendance à décroître le long des trajectoires du processus, du moins en dehors d'un certain ensemble d'états ($F$). Puisque $h$ est positive (cf. la démonstration), cette fonction ne va pas pouvoir éternellement décroître et va donc un jour ou l'autre rentrer dans $F$. (p. 169)
\end{remf}

\subsection{Stabilisation du protocole Aloha}

On a vu dans la première section que le protocole ALOHA était, avec une retransmission de probabilité $\nu$, instable. Nous allons voir comment, en autorisant la probabilité de retransmission $\nu(\cdot)$ à dépendre du nombre de messages semi-bloqués et à condition que l'intensité du traffic soit suffisament faible, on peut rendre le protocole stable si $a_{0}>a_{1}$, hypothèse que nous faisons dans la suite. La description est donc toujours la même que dans la première section mais maintenant, $\nu$ n'est plus une constante mais une fonction du nombre de messages semi-bloqués. Si $X_n=k$ est le nombre de messages semi-bloqués, on note toujours $b_i(k)$ la probabilité que $i$ parmi eux soient réémis.\\

\begin{remf}
Dans le cas où l'on ne suppose pas $a_{0}>a_{1}$, on peut montrer que le protocole reste instable même si l'on autorise une probabilité de retransmission non constante.
\end{remf}

\quest 1) Montrer que :
$$\E\left[X_{n+1}-X_{n}|X_{n}=i\right]=\lambda-b_{1}(i)a_{0}-b_{0}(i)a_{1}$$

\quest 2) En utilisant le lemme de Pake, montrer qu'il suffit de trouver une fonction $\nu$ telle que :
$$\lambda \leq \lim_{i\rightarrow \infty}(b_{1}(i)a_0 +b_{0}(i)a_1)-\epsilon $$
o\`u $\epsilon >0$.

\quest 3) Montrer que cette condition est équivalente à :
$$\lambda \leq g_{i}(\nu(i))-\epsilon$$
où $g_{k}(\nu)=(1-\nu)^k a_1 + k\nu (1-\nu)^{k-1}a_0$.

\quest 4) En déduire qu'une condition de stabilité est :
$$\lambda < a_{0}\exp \left\{\cfrac{a_1}{a_0}-1\right\}$$

\quest 5) Critiquer ce protocole.

\quest La principale critique que l'on puisse faire à ce protocole est que pour le rendre stable, notre stratégie suppose que chaque utilisateur connaisse le nombre de messages semi-bloqués. Ce n'est pratiquement pas faisable. Ce qui est réaliste, c'est de concevoir une probabilité de retransmission qui se ferait en fonction de l'information suivante : ``y a-t-il collision, transmission d'un message ou pas ?''. On peut montrer que ces stratégies sont effectivement stables.

\begin{remf}
Pour un autre protocole, voir $\cite{Br}$  pp.174-178. Un autre exemple int\'eressant traité par $\cite{Br}$ est une marche aléatoire 2-dimensionnelle avec des barrières réléchissantes sur l'axe des ordonnées et des abscisses. Le processus reste donc toujours dans le quadrant positif.\\
Le crit\`ere de Foster est aussi donn\'e p. 135, probl\`eme corrig\'e 4.8 dans $\cite{BMP}$ (en particulier, l'exercice du d\'ebut y est d\'emontr\'e). Une application y est donn\'ee pour un mod\`ele (simple) de file d'attente.
\end{remf}
