OEF Chaînes de Markov --- Introduction ---

Ce module regroupe pour l'instant 21 exercices sur les chaînes de Markov à espace d'états fini ou dénombrable. La plupart des exercices portent sur les chaînes de Markov à espace d'états fini.

Les états accessibles

On considère une chaîne de Markov homogène dont les états sont numérotés de 1 à et dont la matrice de transition est :

Cocher tous les états accessibles à partir de l'état (s'il n'y en a pas, cocher "aucun des états").

Automate

Une source émet une suite de chiffres choisis parmi les entiers de 0 à , indépendamment les uns des autres suivant la loi de probabilité suivante :

On dispose d'un automate qui reconnait le motif = suivant :

Initialement, cet automate est dans l'état 0. Après avoir lu un chiffre émis par la source, l'automate est dans l'état si les deux conditions suivantes sont réalisées :

les derniers chiffres que la source a envoyés forment le motif
les derniers chiffres qu'a envoyés la source ne forment pas le motif .

Dans les autres cas, l'automate est dans l'état 0.

1- Compléter le tableau suivant en donnant l'état de l'automate après la lecture d'un chiffre en fonction de l'état de l'automate avant cette lecture.

avant la lecture \ chiffre lu
état

1- Bonne réponse ! L'état de l'automate après la lecture du -ième chiffre peut s'écrire où est la fonction décrite par le tableau ci-dessous.

état \ chiffre lu

Cela permet de montrer que les états successifs de l'automate ,..., ,... constituent une chaîne de Markov.

2 - Donner sa matrice de transition.

NB :

Suite binaire

Une source émet une suite de bits 0 et 1. On suppose que la loi du premier bit émis est donnée par le tableau suivant :

s

On suppose que les chiffres sucessivement émis constituent une chaîne de Markov homogène dont la matrice de transition est :

Loi à un instant donné

On considère une chaîne de Markov , homogène d'espace d'états et de matrice de transition :

1- Déterminer la loi conditionnelle de sachant que .


P( = \| = )

Bonne réponse ! on a bien


P( = \| = )

2- La loi de est donnée dans le tableau suivant :

	s
P( = )

Déterminer la loi de


P( = )

Etats récurrents

On considère une chaîne de Markov homogène dont les états sont numérotés de 1 à . Sa matrice de transition est :

NB: le caractère * désigne un coefficient non nul

Cocher tous les états récurrents (s'il n'y en a pas, cocher "aucun des états").

Communication entre les états

On considère une chaîne de Markov homogène dont les états sont numérotés de 1 à et dont la matrice de transition est :

Cocher tous les états qui communiquent avec l'état (s'il n'y en a pas, cocher "aucun des états").

Diffusion

On modélise le mouvement de molécules entre deux compartiments A et B de la façon suivante : on discrétise le temps en intervalles de même durée notée . On suppose que pendant un intervalle de temps ,

Pour , on note le nombre de particules dans le compartiment A à l'instant . On peut montrer que la suite est une chaîne de Markov homogène. Donner sa matrice de transition.

NB :

File d'attente

On dispose d'un réseau constitué et d'un buffer qui peut contenir au maximum fichiers. On discrétise le temps en intervalles de même durée appelés slots. On suppose qu'au cours d'un slot, chaque serveur peut traiter un fichier qui est dans le buffer au début de ce slot. On modélise le nombre de fichiers qui arrivent dans le buffer du réseau au cours de chaque slot par des variables aléatoires indépendantes , ,... dont la loi est décrite par le tableau ci-dessous :

A la fin d'un slot, le buffer contient les fichiers qui n'ont pas pu être traités par les serveurs au cours du slot, auxquels s'ajoutent les fichiers qui sont arrivés pendant le slot. Les fichiers qui ne peuvent pas être stockés dans le buffer sont perdus.
On note le nombre du fichier au début du premier slot et pour , on note le nombre de fichiers en attente de traitement à la fin du n-ième slot. On peut montrer que la suite est une chaîne de Markov homogène. Donner sa matrice de transition.

NB :

Irréductibilité

On considère une chaîne de Markov homogène dont les états sont numérotés de 1 à et dont la matrice de transition est :

La chaîne est-elle irréductible ?

Calcul de la loi invariante

On considère une chaîne de Markov homogène dont les états sont numérotés de 1 à et dont la matrice de transition est :

Donner les coefficients d'une loi probabilité invariante pour cette chaîne.

NB :

Loi réversible

On considère une chaîne de Markov homogène dont les états sont numérotés de 1 à et dont la matrice de transition est :

1- Cette chaîne de Markov admet-elle une loi de probabilité réversible ?

2- Donner les coefficients d'une loi de probabilité invariante pour cette chaîne.

NB :

Marche aléatoire sur un graphe

On considère le graphe représenté ci-dessous :

Une fourmi se déplace sur le graphe de la façon suivante : arrivée à un sommet, elle choisit au hasard une arête partant de ce sommet et la parcourt jusqu'à atteindre un autre sommet.

Donner la matrice de transition de la chaîne de Markov décrivant la suite des sommets visités par la fourmi.

NB : pour écrire la matrice, énumérer successivement les coefficients de chaque ligne en les séparant par des virgules et passer à la ligne pour écrire les coefficients de la ligne suivante.

Jeu de l'oie I

Un jeu de l'oie simple est constitué de cases numérotées de 1 à disposées comme ci-dessous. La case 1 est la case de départ et la case est la case d'arrivée.

Pour faire avancer le pion, on lance un dé à faces numérotées de 1 à et on avance le pion d'un nombre de cases égal au nombre obtenu avec le dé. Le jeu s'arrête lorsque le pion tombe exactement sur la case . Sinon le pion recule.
Par exemple, si le pion se trouve sur la case et si le dé tombe sur 3, le pion va à la case . Si au coup suivant, le dé tombe sur 1, le pion retourne sur la case .

Les positions successives du pion définissent une chaîne de Markov sur les entiers de 1 à . On supposera que lorsque le jeu s'arrête, les positions suivantes du pion sont toujours .

1- Donner la matrice de transition de cette chaîne de Markov.

NB :

Bonne réponse : la matrice de transition de cette chaîne de Markov est bien :

2- Dans le véritable jeu de l'oie, toutes les cases ne sont pas identiques. On modifie le plateau du jeu en supposant que la case est une case "oubliette", ce qui signifie que si le pion tombe sur cette case, il y reste indéfiniment.

Déterminer la matrice de transition de la chaîne de Markov qui décrit les positions successsives du pion sur ce nouveau plateau.

Jeu de l'oie II

Un jeu de l'oie simple est constitué de cases numérotées de 1 à disposées comme ci-dessous. La case 1 est la case de départ et la case est la case d'arrivée.

Pour faire avancer le pion, on lance un dé à faces numérotées de 1 à et on avance le pion d'un nombre de cases égal au nombre obtenu avec le dé. Le jeu s'arrête lorsque le pion tombe exactement sur la case . Sinon le pion refait un tour.
Par exemple, si le pion se trouve sur la case et si le dé tombe sur 2, le pion va à la case 1.

Les positions successives du pion définissent une chaîne de Markov sur les entiers de 1 à . On supposera que lorsque le jeu s'arrête, les positions suivantes du pion sont toujours .

1- Donner la matrice de transition de cette chaîne de Markov.

NB :

Bonne réponse : la matrice de transition de cette chaîne de Markov est bien :

Déterminer la matrice de transition de la chaîne de Markov qui décrit les positions successsives du pion sur ce nouveau plateau.

Probabilité d'absorption

On considère une chaîne de Markov homogène sur les entiers de 1 à , dont la matrice de transition est :

Calculer la probabilité que la chaîne de Markov partie de l'état réussisse à atteindre l'état .

Comportement asymptotique

Soit une chaîne de Markov homogène sur , de matrice de transition et .
de la chaîne.

Que peut-on dire du comportement de la suite lorsque tend vers dans la situation suivante ?

Votre réponse :

Liens entre deux états

Soient et deux états différents d'une chaîne de Markov homogène sur .

Que peut-on dire de l'état dans la situation suivante ?

Votre réponse :

Nombre de lois invariantes

On considère la chaîne de Markov homogène de matrice de transition :

Combien a-t-elle de mesures de probabilité invariantes ?

Caractérisation d'un état

Soit une chaîne de Markov homogène sur partant de l'état .

L'affirmation suivante est-elle toujours vraie ?

Si , alors

Séquence markovienne 1

Une source émet une suite de chiffres choisis parmi les entiers de 1 à . On suppose que les chiffres sucessivement émis constituent une chaîne de Markov homogène dont la matrice de transition est :

1- Sachant que le -ième chiffre émis est , quelle est la probabilité que les chiffres suivants soient dans l'ordre ?

2- Sachant que le -ième chiffre émis est , quelle est la probabilité que le -ième chiffre émis soit ?

3- Sachant que le -ième chiffre émis est et que le -ième chiffre émis est , quelle est la probabilité que le -ième chiffre émis soit ?

Séquence markovienne 2

Sachant que la suite de chiffres émise par la source commence par , combien de chiffres la suite aura-t-elle, en moyenne , à la apparition de ?

The most recent version

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur de web.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.

Description: exercices d'introduction aux chaînes de Markov. interactive exercises, online calculators and plotters, mathematical recreation and games

Keywords: interactive mathematics, interactive math, server side interactivity, , probabilités, proba, chaînes, chaîne, Markov, graphe, matrice de transition, loi, récurrent, transitoire, absorbant