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

Ce module regroupe pour l'instant 33 exercices sur les chaînes de Markov homogènes à espace d'états fini ou dénombrable.

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").

NB : , sélectionnez la liste suivante :

Automate

Une source émet une suite de , indépendamment les uns des autres selon la loi de probabilité suivante :

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

Description du fonctionnement de cet automate : il peut se trouver dans les états 0, ; son état peut varier à chaque fois qu'il lit un nouveau chiffre émis par la source.
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 :

Q=
  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( = )

NB : , sélectionnez la liste suivante :

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 :

N.B. Le caractère * désigne un coefficient non nul.

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


N.B. Si vous voulez faire un copier-coller des coefficients de la matrice de transition, sélectionnez la ligne suivante :

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").

NB : , sélectionnez la liste suivante :

Définition de la période d'un état

Soit une chaîne de Markov homogène dont les états sont numérotés de 1 à . On note sa matrice de transition.

Donner l'information la plus précise que l'on peut déduire de l'hypothèse suivante :

.

La période du -ième état

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 :

La période d'un état sur un exemple

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

N.B. : le caractère * désigne un coefficient non nul.

Donnez la période du premier -ième état :

N.B. : Si vous voulez faire un copier-coller des coefficients de la matrice de transition, sélectionnez la ligne suivante :

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.

N.B.

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 ?

NB : , sélectionnez la liste suivante :

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 :
NB : , sélectionnez la liste suivante :

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.
    Entrez votre réponse :

    NB :
    NB : , sélectionnez la liste suivante :

Loi réversible 2

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.
    Entrez votre réponse :

    NB :
    NB : , sélectionnez la liste suivante :


    La seule loi invariante par est décrite par le vecteur .
  3. On suppose que la loi de est décrite par le vecteur . Déterminer la probabilité que soit dans l'état si on a observé que est dans l'état .
    Entrez votre réponse :

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.

Marche aléatoire sur un graphe 2

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.
  1. Donner la matrice de transition notée 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.
  2. Cette chaîne admet une unique loi invariante, laquelle ?
  3. Quelle est la période de cette chaîne ?
  4. La fourmi passe par le sommet avec une fréquence qui converge vers avec probabilité 1 si on fait tendre le nombre de déplacements de la fourmi vers .
  5. La fourmi parcourt l'arête qui séparent les sommets et avec une fréquence qui converge vers avec probabilité 1 si on fait tendre le nombre de déplacements de la fourmi vers .

Moyenne temporelle

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 :

=

Lorsque tend vers , la variable aléatoire

converge avec probabilité 1 vers une constante. Quelle est la valeur de cette constante ?

NB , sélectionnez la liste suivante :

Mouvements d'habitants

On modélise l'évolution du lieu d'habitation d'un individu au cours des années par une chaîne de Markov homogène .

  1. Entrer les poids des arêtes du graphe suivant afin d'obtenir le graphe associé à la chaîne de Markov .

       
       
  3. Si ce modèle de mouvement entre les villes A et B s'appliquait depuis longtemps à toutes les personnes des villes A et B indépendamment les unes des autres, le nombre d'habitants de la ville devrait être en moyenne de :

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 :

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.

Probabilité d'absorption

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

Déterminer la probabilité que la chaîne de Markov partie de l'état réussisse à atteindre l'état :

NB : on peut faire un copier-coller des coefficients de la matrice en sélectionnant la liste suivante :

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 ?

et

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 lois 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

Salle d'attente

Un patient qui arrive dans un cabinet médical est dirigé vers une salle d'attente. S'il y a déjà personnes qui attendent, le patient découragé repart immédiatement.
dans ce cabinet. Le médecin vient Les médecins viennent toutes les 20 mn dans la salle d'attente pour voir s'il y a des patients en attente. Si c'est le cas, il prend en consultation l'un des patients, sinon il revient 20 mn plus tard. On supposera qu'une consultation ne dure pas plus de 20 mn. On discrétise le temps en intervalles de temps de durée 20 mn. On modélise le nombre de personnes qui arrivent à ce cabinet médical pendant les intervalles de temps successifs , , ,... par des variables aléatoires indépendantes et de même loi , , ,... La loi de ces v.a. est décrite par le tableau ci-dessous :
On note le nombre de personnes dans la salle d'attente à l'instant et pour , on note le nombre de personnes qui sont dans la salle d'attente lorsque le médecin arrive les médecins arrivent à l'instant dans la salle d'attente. On peut montrer que la suite est une chaîne de Markov homogène.
Donner sa matrice de transition.

NB :

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 ?
NB : , sélectionnez la liste suivante :

Séquence markovienne 2

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 :

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 ?

NB : , sélectionnez la liste suivante :

Suite markovienne stationnaire

Une source émet une suite de chiffres choisis parmi les entiers . On suppose que

NB , sélectionnez la liste suivante :
  1. Déterminez la loi de probabilité invariante par cette matrice.

    Entrez votre réponse :
    ()


  • Déterminez la probabilité que le motif apparaisse en position .

    Entrez votre réponse :


    • Bonne réponse, la probabilité que le motif apparaisse en position est égale à .
  • Le nombre d'occurrences du motif dans une telle suite est une variable aléatoire. Déterminez son espérance.

    Entrez votre réponse :


    • Bonne réponse, le motif apparaîtra en moyenne fois dans une telle suite.
  • Déterminez la probabilité que le motif apparaissent en position et en position .

    Entrez votre réponse :

    • Simulation d'une chaîne de Markov

    On cherche à simuler une réalisation d'une chaîne de Markov homogène dont l'ensemble des états est {} et dont la matrice de transition est

    Supposons que l'on ait déjà simulé une réalisation de et que l'on ait obtenu :

    .

    Compléter l'algorithme suivant pour qu'il simule une réalisation de i <- 1 Tant que u > q(i) i <- i + 1 FinTantQue Retourner e(i)
    N.B. Dans le programme, rand simule le tirage d'un nombre suivant la loi uniforme sur [0,1].

    Suite binaire 2

    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 :

    1. ?
    2. ?
      La probabilité recherchée est
    4. ?
    The most recent version
    Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
    Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

    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.