Quelles sont les chaînes de Markov?

9

Je lis actuellement des articles sur le regroupement de chaînes de Markov et je ne vois pas la différence entre une chaîne de Markov et un graphique pondéré simple.

Par exemple, dans l'article Optimisation de l'espace d'état dans les chaînes de Markov, ils fournissent la définition suivante d'une CTMC (chaîne de Markov à temps continu):

Nous considérons un CTMC fini avec un espace d'états par une matrice de taux de transition .S = { x 1 , x 2 , , x n } Q : S × SR +(S,Q)S={X1,X2,,Xn}Q:S×SR+

Ils ne mentionnent pas du tout la propriété Markov, et, en fait, si le poids sur les bords représente une probabilité, je crois que la propriété Markov tient trivialement car la probabilité ne dépend que de l'état actuel de la chaîne et non du chemin qui mène à elle.

Dans un autre article sur les propriétés relationnelles de la lumpabilité, les chaînes de Markov sont définies de la même manière:

Une chaîne de Markov M sera représentée comme un triplet (S,P,π)S est l'ensemble fini d'états de M , P la matrice de probabilité de transition indiquant la probabilité de passer d'un état à un autre, et π est le distribution de probabilité initiale représentant la probabilité que le système démarre dans un certain état.

Encore une fois, aucune mention du passé ou du futur ou de l'indépendance.

Il y a un troisième papier Simple O (m logn) Time Markov Chain Lumping où non seulement ils ne déclarent jamais que les poids sur les bords sont des probabilités, mais ils disent même:

Dans de nombreuses applications, les valeurs sont non négatives. Nous ne faisons pas cette hypothèse, cependant, car il existe également des applications où est délibérément choisi comme , ce qui le rend généralement négatif.W ( s , s ) - W ( s , S { s } )W(s,s)W(s,s)-W(s,S{s})

De plus, il est indiqué que le regroupement devrait être un moyen de réduire le nombre d'états tout en maintenant la propriété Markov (en agrégeant l'état "équivalent" dans un état plus grand). Pourtant, pour moi, il semble que ce soit simplement la somme des probabilités et cela ne devrait même pas garantir que les probabilités résultantes des transitions vers / depuis les états agrégés sont dans la plage . Qu'est-ce que le grumelage conserve alors?[0,1]

Donc, je vois deux possibilités:

  • Je n'ai pas compris ce qu'est une chaîne de Markov, ou
  • L'utilisation du terme chaîne de Markov dans ces articles est fausse

Quelqu'un pourrait-il clarifier la situation?

Il semble vraiment que différentes communautés utilisent ce terme et qu'elles signifient des choses très différentes. D'après ces 3 articles que je considère, il semble que la propriété Markov soit triviale ou inutile, tout en regardant un autre type de documents, elle semble fondamentale.

Bakuriu
la source
Il existe des tonnes de manuels et de ressources sur Internet qui expliquent (a) ce qu'est une chaîne de Markov et (b) quelle est la définition mathématique précise. Nous nous attendons à ce que vous fassiez une quantité importante de recherche et d'auto-étude avant de demander. Alors, avez-vous consulté l'une de ces ressources? Qu'avez-vous trouvé là-bas? PS Je suppose que les articles de la littérature supposeraient que vous connaissez la définition d'une chaîne de Markov, et ces phrases ne seraient pas nécessairement conçues comme une définition formelle précise d'une chaîne de Markov, mais plutôt simplement pour établir la notation qu'ils utilisent lors de la conversation environ un.
DW
Passé ou futur ou indépendance sont des propriétés qui suivent, iirc. Il devrait cependant y avoir quelques restrictions sur le poids; peut-être que certaines choses peuvent rester implicites, par exemple en affectant un poids sortant manquant à un bord qui mène à un état de puits (cf. différentes définitions DFA).
Raphael
4
@DW Oui, je l'ai fait. Ce que j'ai trouvé, c'est que la notion de chaîne de Markov dans les manuels semble n'avoir rien à voir avec son concept tel qu'il est utilisé dans de tels articles. C'est exactement pourquoi je pose cette question.
Bakuriu
4
Encore une fois, il y a une troisième possibilité. Je pense que l'erreur que vous faites est d'interpréter la déclaration contenue dans ces articles comme une définition d'une chaîne de Markov. Je suppose que ce n'est probablement pas l'intention de ces déclarations. Je suppose que les auteurs supposent que vous connaissez déjà la définition d'une chaîne de Markov et que vous essayez simplement d'établir une notation (il existe plusieurs types de notation que vous pouvez utiliser pour le même concept). Alors, jetez un autre regard de ce point de vue et voyez si vous trouvez quelque chose qui le contredit dans les journaux (si vous en trouvez, ajoutez-le à la question).
DW
4
@DW Il semble que l'OP ait fait des recherches décentes et structuré sa question de manière acceptable. Oui, nous pouvons utiliser Google pour apprendre. Mais avez-vous remarqué à quel point les sites SE sont bien classés dans Google? C'est parce que nous condensons les informations en questions (généralement) uniques et bien définies. Les efforts de collaboration de notre communauté créent un contenu très riche et précieux qui est, plusieurs fois, plus utile que les pages et les pages d'informations disponibles, ce qui se traduit par un apprentissage plus efficace.
BAR

Réponses:

10

Une chaîne de Markov à temps continu peut être représentée sous forme de graphique dirigé avec des poids de bord non négatifs constants. Une représentation équivalente des poids de bord constants d'un graphe orienté à nœuds est une matriceLa propriété Markov (que les futurs états dépendent uniquement de l'état actuel) est implicite dans les poids de bord constants (ou entrées constantes dans la matrice). Implicite signifie implicite par . Les mathématiciens l'utilisent comme un euphémisme signifiant «vous devez le prouver vous-même».N × NNN×N

Mais le premier article définit une notation cohérente avec une chaîne de Markov à temps continu, parfois appelée processus de Markov , tandis que le second papier définit une notation cohérente avec une chaîne de Markov à temps discret . Ils disent

P est la matrice de probabilité de transition indiquant la probabilité de passer d'un état à un autre, et est la distribution de probabilité initiale représentant la probabilité que le système démarre dans un certain état. [non souligné dans l'original]π

Ils supposent que la matrice est constante dans le temps (impliquant ainsi la propriété Markov). Implicite dans le terme probabilité est le fait que chaque constante est dans la plage , que les entrées dans chaque colonne de somme à , et que la somme des entrées dans somme à .[0,1]P1π1

Je ne peux pas lire le troisième papier, il est payant. Si les entrées dans chaque colonne de la matrice doivent totaliser 1, ce sont des probabilités et elles parlent de chaînes de Markov à temps discret. Si les entrées de chaque colonne peuvent correspondre à un nombre arbitraire, les entrées représentent des taux et non des probabilités et elles parlent de chaînes de Markov à temps continu.

Les chaînes de Markov à temps continu ne sont pas les mêmes que les chaînes de Markov à temps discret . Dans une chaîne de Markov à temps continu, les poids de bord ne représentent pas des probabilités, mais plutôt des taux de transition . Les poids des bords doivent être non négatifs, mais peuvent être arbitrairement grands, et les poids des bords extérieurs peuvent correspondre à n'importe quel nombre non négatif. Il n'est pas nécessaire que la somme soit .1

Avec les chaînes de Markov à temps continu et à temps discret, la propriété Markov est impliquée par les poids de bord constants (ou de manière équivalente les entrées constantes dans la matrice de transition).

Logique errante
la source
8

Les chaînes de Markov sont disponibles en deux versions: temps continu et temps discret.

Les chaînes de Markov temporelles continues (CTMC) et les chaînes de Markov temporelles discrètes (DTMC) sont représentées sous forme de graphiques pondérés dirigés.

Pour les DTMC, les transitions prennent toujours une unité de «temps». En conséquence, il n'y a pas de choix pour ce que devrait être votre poids sur un arc - vous mettez la probabilité d'aller à "j" étant donné que vous êtes à "i".

Pour les CTMC, le temps de transition entre deux états quelconques est nécessairement donné par une variable aléatoire exponentielle. C'est la principale différence entre les CTMC et les DTMC: les DTMC ont toujours un temps de transition unitaire. Les CTMC ont un temps de transition aléatoire.

Pour un CTMC, la convention est généralement de mettre des poids sur un arc en fonction du taux de la variable aléatoire exponentielle allant de la source à la destination. C'est-à-dire que la convention est de mettre des taux sur les arcs, pas des probabilités.

Taux négatifs

Bien que tous les CTMC dont je me souvienne soient représentés avec des taux positifs sur les bords, des taux négatifs apparaissent dans l'analyse CTMC.

Supposons que nous nous trouvions à l'état A, qui est connecté à B, C et D comme ci-dessous.

A -> B (le taux en A de B est négatif) A -> C (le taux en A de C est négatif) D -> A (le taux en A de D est positif)

Ce n'est probablement pas tout à fait ce à quoi votre document fait référence; Je soulève pour montrer que les poids négatifs ne sont pas nécessairement ridicules si quelqu'un travaillait avec une convention appropriée.

Propriété Markov

Pour DTMC, vous avez raison. La propriété markov est satisfaite trivialement. Pour les CTMC, la propriété markov est satisfaite car les transitions sont données par des variables aléatoires exponentielles (qui sont "sans mémoire"). Si les transitions n'étaient pas données par des variables aléatoires exponentielles (disons plutôt qu'elles étaient uniformes), alors nous parlerions de «chaînes semi-markoviennes» ou de «processus semi-markoviens».

Riley
la source
Merci pour la clarification sur l'exponentielle sans mémoire. Ca a du sens. J'ai revérifié le troisième article et ils disent explicitement qu'ils ne supposent pas que les poids ne sont pas négatifs, car il y a une définition particulière de (le taux d'un état en lui-même) qui est généralement défini comme être (c'est-à-dire moins la somme des taux de pour tous les autres états), ce qui le rend presque toujours négatif. W(s,s)-W(s,S{s})s
Bakuriu
W(s,s)=-W(s,S{s})