Cadena de Màrkov de temps discret

Una cadena de Markov amb dos estats, A i E.

En probabilitat, una cadena de Màrkov de temps discret (DTMC) és una seqüència de variables aleatòries, coneguda com a procés estocàstic, en què el valor de la següent variable depèn només del valor de la variable actual, i no de cap variable en el passat. Per exemple, una màquina pot tenir dos estats, A i E. Quan es troba a l'estat A, hi ha un 40% de possibilitats que es mogui a l'estat E i un 60% de possibilitats que quedi a l'estat A . Quan es troba a l'estat E, hi ha un 70% de possibilitats que es mogui a A i un 30% de possibilitats que es quedi a E. La seqüència d'estats de la màquina és una cadena de Màrkov. Si denotem la cadena per $X_{0},X_{1},X_{2},...$ aleshores $X_{0}$ és l'estat en què comença la màquina i $X_{10}$ és la variable aleatòria que descriu el seu estat després de 10 transicions. El procés continua per sempre, indexat pels nombres naturals.

Un exemple d'un procés estocàstic que no és una cadena de Màrkov és el model d'una màquina que té els estats A i E i es mou a A des d'un dels dos estats amb un 50% de possibilitats si alguna vegada ha visitat A abans, i un 20% de possibilitats si ho ha fet. mai no heu visitat A abans (deixant un 50% o un 80% de possibilitats que la màquina es mogui a E). Això es deu al fet que el comportament de la màquina depèn de tot l'historial: si la màquina està en E, pot tenir un 50% o un 20% de possibilitats de passar a A, depenent dels seus valors passats. Per tant, no té la propietat de Màrkov.

Una cadena de Màrkov es pot descriure mitjançant una matriu estocàstica, que enumera les probabilitats de passar a cada estat des de qualsevol estat individual. A partir d'aquesta matriu, es pot calcular la probabilitat d'estar en un estat particular n passos en el futur. L'espai d'estats d'una cadena de Màrkov es pot dividir en classes comunicatives que descriuen quins estats són accessibles els uns dels altres (en una transició o en molts). Cada estat es pot descriure com a transitori o recurrent, depenent de la probabilitat que la cadena torni a aquest estat. Les cadenes de Màrkov poden tenir propietats que inclouen periodicitat, reversibilitat i estacionarietat. Una cadena de Màrkov de temps continu és com una cadena de Màrkov de temps discret, però mou els estats contínuament a través del temps en lloc de com a passos de temps discrets. Altres processos estocàstics poden satisfer la propietat de Màrkov, la propietat que el comportament passat no afecta el procés, només l'estat actual.

Definició

Una cadena de Màrkov de temps discret és una seqüència de variables aleatòries $X_{0},X_{1},X_{2},...$ amb la propietat de Màrkov, és a dir, que la probabilitat de passar al següent estat depèn només de l'estat actual i no dels estats anteriors:

$\Pr(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x\mid X_{n}=x_{n}),$ si ambdues probabilitats condicionals estan ben definides, és a dir, si $\Pr(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.$

Els valors possibles de X _i formen un conjunt comptable S anomenat espai d'estats de la cadena.

Les cadenes de Màrkov sovint es descriuen mitjançant una seqüència de gràfics dirigits, on les vores del gràfic n estan etiquetades per les probabilitats de passar d'un estat en el temps n als altres estats en el temps n+1, $\Pr(X_{n+1}=x\mid X_{n}=x_{n}).$ La mateixa informació està representada per la matriu de transició del temps n al temps n+1. Tanmateix, sovint s'assumeix que les cadenes de Markov són homogènies en el temps (vegeu les variacions a continuació), en aquest cas el gràfic i la matriu són independents de n i, per tant, no es presenten com a seqüències.