Quelles sont les chaînes de Markov?

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 × S → R$(\mathcal{S}, Q)$$\mathcal{S} = \{x_1, x_2, \ldots, x_n\}$$Q: \mathcal{S} \times \mathcal{S} \to \mathbb{R}^+$

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, \pi)$ où $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 $\pi$ 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 \setminus \{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.

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 × $N$$N \times 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]$\pi$

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]$$P$$1$$\pi$$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).

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».