Les états accessibles

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

Cocher tous les états accessibles à partir de l'état $val11 (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 à $val7, indépendamment les uns des autres suivant la loi de probabilité suivante :
$val23

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

$val15

Initialement, cet automate est dans l'état 0. Après avoir lu un chiffre émis par la source, l'automate est dans l'état $val25 si les deux conditions suivantes sont réalisées : 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 $m_s1
état $m_s2
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 $m_s1
$m_s2 $(val17[$m_s3])

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

2 - Donner sa matrice de transition.

NB : $val29


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 :
$m_s
$(val10[1;$m_ss])

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

$val22 ?


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 .
$m_ii
P( = | = $val12)

Bonne réponse ! on a bien
$m_ii
P( = | = $val12) $(val17[1;$m_j])

2- La loi de est donnée dans le tableau suivant :
$m_s
P( = ) $(val10[1;$m_ss])

Déterminer la loi de
$m_s2
P( = )


Etats récurrents

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

$val17

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 à $val6 et dont la matrice de transition est :

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


Diffusion

On modélise le mouvement de $val6 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 , $val9

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 : $val10


File d'attente

On dispose d'un réseau constitué $val17$val16 et d'un buffer qui peut contenir au maximum $val7 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 :

$val11

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 : $val18


Irréductibilité

On considère une chaîne de Markov homogène dont les états sont numérotés de 1 à $val6 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 à $val6 et dont la matrice de transition est :

=

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

NB : $val17

Loi réversible

On considère une chaîne de Markov homogène dont les états sont numérotés de 1 à $val6 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 : $val19

Marche aléatoire sur un graphe

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

$val10

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 $val7 cases numérotées de 1 à $val7 disposées comme ci-dessous. La case 1 est la case de départ et la case $val7 est la case d'arrivée.

$val16

Pour faire avancer le pion, on lance un dé à $val6 faces numérotées de 1 à $val6 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 $val7. Sinon le pion recule.
Par exemple, si le pion se trouve sur la case $val13 et si le dé tombe sur 3, le pion va à la case $val14. Si au coup suivant, le dé tombe sur 1, le pion retourne sur la case $val13.

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

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

NB : $val19

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 $val10 est une case "oubliette", ce qui signifie que si le pion tombe sur cette case, il y reste indéfiniment.

$val18

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 $val7 cases numérotées de 1 à $val7 disposées comme ci-dessous. La case 1 est la case de départ et la case $val7 est la case d'arrivée.

$val14

Pour faire avancer le pion, on lance un dé à $val6 faces numérotées de 1 à $val6 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 $val7. Sinon le pion refait un tour.
Par exemple, si le pion se trouve sur la case $val17 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 à $val7. On supposera que lorsque le jeu s'arrête, les positions suivantes du pion sont toujours $val7.

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

NB : $val18

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 $val10 est une case "oubliette", ce qui signifie que si le pion tombe sur cette case, il y reste indéfiniment.

$val16

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 à $val9, dont la matrice de transition est :

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


Comportement asymptotique

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

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

$val42

Votre réponse :


Liens entre deux états

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

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

$val18 et $val19

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 $val7 partant de l'état $val9.

L'affirmation suivante est-elle toujours vraie ?

Si $val18, alors $val19


Séquence markovienne 1

Une source émet une suite de chiffres choisis parmi les entiers de 1 à $val6. 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 $val10-ième chiffre émis est $val11, quelle est la probabilité que les $val14 chiffres suivants soient dans l'ordre $val19 ?

2- Sachant que le $val10-ième chiffre émis est $val11, quelle est la probabilité que le $val16-ième chiffre émis soit $val13 ?

3- Sachant que le $val10-ième chiffre émis est $val11 et que le $val16-ième chiffre émis est $val13, quelle est la probabilité que le $val18-ième chiffre émis soit $val12 ?


Séquence markovienne 2

Une source émet une suite de chiffres choisis parmi les entiers de 1 à $val7. 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 $val8, combien de chiffres la suite aura-t-elle, en moyenne , à la $val13 apparition de $val9 ?