Ce document présente un travail pratique sur les chaînes de Markov, incluant des instructions pour simuler des chaînes à l'aide de Python et des matrices de transition. Il aborde des concepts tels que la convergence des états, le calcul des probabilités de transition, et les théorèmes ergodiques. Des exercices pratiques sont également fournis pour appliquer ces concepts à des matrices spécifiques et à des simulations.
0 évaluation0% ont trouvé ce document utile (0 vote)
1 vues7 pages
Ce document présente un travail pratique sur les chaînes de Markov, incluant des instructions pour simuler des chaînes à l'aide de Python et des matrices de transition. Il aborde des concepts tels que la convergence des états, le calcul des probabilités de transition, et les théorèmes ergodiques. Des exercices pratiques sont également fournis pour appliquer ces concepts à des matrices spécifiques et à des simulations.
Ce document présente un travail pratique sur les chaînes de Markov, incluant des instructions pour simuler des chaînes à l'aide de Python et des matrices de transition. Il aborde des concepts tels que la convergence des états, le calcul des probabilités de transition, et les théorèmes ergodiques. Des exercices pratiques sont également fournis pour appliquer ces concepts à des matrices spécifiques et à des simulations.
Ce document présente un travail pratique sur les chaînes de Markov, incluant des instructions pour simuler des chaînes à l'aide de Python et des matrices de transition. Il aborde des concepts tels que la convergence des états, le calcul des probabilités de transition, et les théorèmes ergodiques. Des exercices pratiques sont également fournis pour appliquer ces concepts à des matrices spécifiques et à des simulations.
Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
Télécharger au format pdf ou txt
Vous êtes sur la page 1/ 7
tpmarkov
July 9, 2020
1 Introduction aux Processus Stochastiques (PRSTO)
P. Carmona Pour avancer dans le notebook et exécuter les cellules il faut taper Shift+Enter ou utiliser la barre d’outils ci-dessus et choisir Cell, Run Cell and select Below
1.1 Consignes Vous répondrez aux questions en modifiant ce notebook. En insérant des cellules de type Mark- down pour le texte et des cellules de type code pour le code. Ensuite vous sauvez ce notebook sous le nom Prenom_Nom_tpmarkov.ipynb et vous le déposez sur Moodle
1.2 Simulation d’une chaîne de Markov
Le langage Python dispose d’une fonction pour simuler suivant une loi discrète rnd.choice On dispose d’une matrice de transition, par exemple celle modélisant le climat à Los Angeles.
[1]: import numpy as np
import matplotlib.pyplot as plt import numpy.random as rnd %matplotlib inline
Ecrire une fonction genmarkov(x,n,p) qui simule une chaîne de markov de matrice de transition p issue de x et qui renvoie la valeur Xn−1 (ω ). On écrira également la fonction vgenmarkov qui elle renvoie le vecteur des valeurs ( X0 (ω ), ..., Xn−1 (ω )). Pour le climat à Los Angeles, vérifiez que la proportion de temps passé dans chaque état converge vers un nombre qui ne dépend que de cet état et pas du point de départ.
[3]: n=5000 z=vgenmarkov(1,n,pla) (z==0) #donne un vecteur de booleen (z==0).sum() #donne le nombre de fois ou l'on est passe dans l'etat 0 (z==0).mean() #donne la moyenne empirique (z==0).cumsum() #donne le vecteur des sommes cumulees y=(z==0).cumsum()/np.arange(1,len(z)+1) #donne le vecteur des moyennes de 0
<ipython-input-3-da6a850e0e43> in <module>() 1 n=5000 ----> 2 z=vgenmarkov(1,n,pla) 3 (z==0) #donne un vecteur de booleen 4 (z==0).sum() #donne le nombre de fois ou l'on est passe dans l'etat 0 5 (z==0).mean() #donne la moyenne empirique
Utiliser la loi forte des grands nombres pour calculer, pour les matrices p3, p4 des valeurs ap- (n) (n) (n) prochées de p2,3 , p3,3 , p1,4 pour les valeurs de n suivantes n = 2, 5, 10, 20. Par exemple, vous faites N=1000 (ou N=10000, ou N=50000) simulations de la chaîne de Markov issue de 2, puis vous comptez la proportion de fois où vous observez la valeur 3 Vérifier vos simulations en utilisant le calcul matriciel. Sous Python, le produit matriciel des matrices p et q s’écrit np.dot(p,q) ce qui est très différent de p ∗ q. Ecrivez une fonction puis(p,n) qui renvoie la matrice pn . (Vous pouvez utiliser un algorithme de calcul rapide de puissance si vous savez le coder).
1.4 Calcul de probabilités et de temps d’absorption
Premièrement, en utilisant la structure de classes, décrire les 3 comportements asymptotiques possibles pour la chaîne de Markov de matrice de transition
En utilisant la loi forte des grands nombres, calculer une valeur approchée de la probabilité que la chaîne de Markov, issue de 4, réussisse à atteindre l’état 2. Essayons maintenant de répondre à la même question en utilisant le calcul matriciel. Ecrire la matrice de la chaîne absorbee P̃ sous la forme canonique
Q R P̃ = 0 I
Puis utiliser la fonction np.linalg.inv pour calculer N = ( I − Q)−1 et enfin retrouver le calcul précédent de la probabilité d’absorption en 2 lorsque l’on part de 4.
4 1.5 Détermination de probabilités invariantes On peut chercher les valeurs et vecteurs propres de la matrice pla
N’oublions pas que le vecteur 1 dont toutes les coordonnées sont des 1 est un vecteur propre avec la valeur propre 1. Ici nous cherchons une probabilité invariante, i.e. un vecteur propre à gauche. Il faut donc déterminer le spectre de la transposée
[215]: v,w=np.linalg.eig(pla.T)
[216]: v
[216]: array([ 0.4, 1. ])
[217]: w
[217]: array([[-0.70710678, -0.19611614],
[ 0.70710678, -0.98058068]])
Il faut faire attention lorsque l’on compare des valeurs numériques
[218]: np.sqrt(2)*np.sqrt(2) == 2.0
[218]: False
Pour comparer, à la précision de la machine utilisée,
[219]: np.isclose(np.sqrt(2)*np.sqrt(2), 2.0)
[219]: True
Ecrire une fonction probinv(p) qui prenne en paramètre une matrice stochastique p et qui retourne une probabilité invariante pour p. N’oubliez pas de normaliser le vecteur propre pour obtenir une probabilité. Tester cette fonction avec pla et la matrices de transition pt et celle de l’exercice 4.10.
1.6 Le théorème ergodique
Rappelez les conditions d’application de ce théorème. Indiquez pour chacun des exercices 4.7, 4.12 si vous avez le droit de l’appliquer et faites le, éventuellement, pour répondre aux questions de ces exercices. Vous devez déterminer la/les probabilités invariantes, la fonction f dont vous prenez la moyenne temporelle (c’est un vecteur de la bonne dimension) et calculer la moyenne < f , π >.
Relire attentivement l’énoncé de ce théorème. Indiquer, pour la matrice pla et celle de l’exercice 4.17, vers quelle matrice P∞ doit converger Pn quand n → ∞. Vérifier, dans ces deux cas, que la décroissance d’une distance entre Pn et P∞ est en ρn avec ρ ∈ ]0, 1[. Comparer la valeur de ρ trouvée expérimentalement et la valeur théorique donnée par le théorème de Perron Frobenius. [221]: def distance(p,q): r=(p-q)**2 return(np.sqrt(r.sum())) distance(p7,p7)
[221]: 0.0
1.8 Page Rank
Considérons 6 pages web dont les liens sont donnés par le graphe suivant. Simuler un marcheur qui choisit une page uniformément parmi les liens possibles. Que se passe-t-il ? Pouviez vous le prévoir ? On rajoute du damping α ∈ (0, 1) ie de l’exploration 1 − α : a chaque étape le marcheur en x choisit un des d x liens possibles avec la probabilité dαx et choisit une page au hasard dans tout le web avec la probabilité 1 − α. Pourquoi y a-t-il une unique mesure invariante ? Trouver la mesure invariante pour α = 0.5 et α = 0.85. En déduire la page la plus importante dans les deux cas. Commentez. Commandes Python : np.full
