Module FAT du MPRO, session 2020

Livre de référence

Voici le livre de référence, il va bien au delà du programme du module.

Author = Decreusefond, L. and Moyal, P.,
Publisher = Hermes,
Title = Mod{'e}lisation et Analyse Stochastiques Des Syst{`e}mes de T{'e}l{'e}communications,
Year = 2011

Slides

Velib

Le Vélib (version Decaux à Paris) a ceci d’intéressant que l’on a accès aux données de toutes les stations en temps réel. Le site http://vlsstats.ifsttar.fr illustre ce que l’on peut en faire.

Votre tache (que vous n’avez pas d’autre choix que d’accepter) consiste à

Kelly

Kelly, F. P. and Yudovina, E., Lectures on Stochastic Networks

Annales

Partie théorique

1 vélo

On commence par le cas trivial de 1 vélo en partage sur les 5 stations.

  • Quelle est la taille de l’espace d’état ?

  • Utilisez les équations de trafic pour obtenir les relations entre les \(\alpha_i\) (notations du document sur les colonies).

  • Dans ces conditions (un seul vélo), calculer la probabilité stationnaire que chaque station soit vide.

Tip

Pour résoudre numériquement le système d’équations donnant les \(\alpha_i\) , on suggère de mettre le système sous forme de calcul matriciel \(M\alpha = X\) où \(\alpha\) est le vecteur colonne des \(\alpha_i\). On a alors \(\alpha=M^{-1}X\). Pour éviter \(X = 0\), on pourra remplacer une ligne de \(M\) par des \(1\) et la dernière ligne de \(X\) par 1.

  • Comparez aux résultats obtenus par simulation.

Warning

Tant que votre simulation ne vous permet pas d’obtenir les résultats précis obtenus algébriquement, c’est qu’il y a un problème dans votre code.

100 vélos

On garde la même matrice de routage, les mêmes temps de transit, etc. En revanche, on suppose que l’on a 100 vélos dans le système.

  • Calculer par simulation la probabilité stationnaire pour chaque station d’être vide. On n’oubliera pas de préciser les intervalles de confiance, voir Intervalles de confiance.

  • la théorie des processus de Markov stipule que

    \[\pi(n)=G_N^{-1} \, \prod_{j=1}^J \frac{\alpha_j^{n_j}}{\prod_{r=1}^{n_j} \phi_j(r)}\]

    pour pour tout \(n\) dans l’espace d’états.

    Notons \(V_i\) l’ensemble des états où la station \(i\) est vide. Pour 100 vélos et 5 stations, quelle serait la complexité du calcul de \(\pi(V_1)\) en termes de nombres d’opérations ?

Tip

On cherchera juste une estimation logarithmique (log en base 10) de ce nombre pour avoir une idée du nombre de chiffres.

Intervalles de confiance

La méthode Monte-Carlo permet de calculer des quantités de la forme \(\theta=E[X]\) où \(X\) est une variable aléatoire réelle ou vectorielle. Elle repose sur la génération de nombreux tirages de copies indépendantes de \(X\) et la loi forte des grands nombres :

\[\label{eq:1} \theta=\lim_{n\to \infty}\frac{1}{n} (X_1+\ldots + X_n):=\lim_{n\to \infty} \hat{\theta_n}.\]

La précision du résultat se mesure par la probabilité de se tromper. On appelle intervalle de confiance à \(\alpha\%\), l’intervalle de la forme \([\hat{\theta}_n-\epsilon,\hat{\theta}_n+\epsilon],\) dans lequel on est sûr à \(\alpha\%\) que se trouve le bon résultat, c’est-à-dire que l’on veut garantir

\[P(|\theta-\hat{\theta}_n|>\epsilon)< 1-\alpha.\]

Le théorème limite centrale indique que

\[\frac{\sqrt{n}}{\sigma}(\theta-\hat{\theta}_n) \text{ converge en loi vers une v.a. gaussienne centrée réduite },\]

avec \(\sigma^2=var(X).\) On en déduit que

\[P(\theta\in [\hat{\theta}_n-\frac{\beta \sigma}{\sqrt{n}},\hat{\theta}_n+\frac{\beta \sigma}{\sqrt{n}}]) \simeq \alpha\]

où \(\beta\) est tel que

\[2(2 \pi)^{-1/2}\int_\beta^{\infty} e^{-u^2/2} du = 1-\alpha.\]

On en déduit que l’intervalle de confiance à \(\alpha\%\) est donné par

\[[\hat{\theta}_n-\frac{\beta \sigma}{\sqrt{n}},\hat{\theta}_n+\frac{\beta \sigma}{\sqrt{n}}])\]

Lorsque l’on ne connaît pas \(\sigma,\) on le remplace par la variance empirique des observations, notée \(\sigma_n\) et donnée par :

\[\sigma_n^2 =\frac{1}{n-1}\sum_{j=1}^n (X_j-\hat{\theta}_n)^2.\]

Pour \(\alpha=0,95,\) on a \(\beta=1,96.\)