Una cadena de Markov es un proceso estocastico en tiempo discreto \(\{X_n:n \geq 0\}\), con espacio discreto, tal que, para cualquier entero \(n \geq 0\), y para cualquier estado \(s_0,\dots, s_n,s_{n+1}\), se cumple
\[ Pr\{s_{n+1}|s_0,\dots, s_n\} = Pr\{s_{n+1}| s_n\}\]
Si al tiempo \(n + 1\) se le considera como un tiempo futuro, al tiempo \(n\) como el presente y a los tiempos \(0, 1, \dots , n - 1\) como el pasado, entonces la condición anterior establece que la distribucion de probabilidad del estado del proceso al tiempo futuro \(n+1\) depende únicamente del estado del proceso al tiempo \(n\), y no depende de los estados en los tiempos pasados.
Probabilidades de transición
Sean \(i\) y \(j\) dos estados de una cadena de Markov. A la probabilidad \[ Pr\{s_{n+1}| s_n\} \]
se le denota por \(p_{ij}^{(n,n+1)}\) y representa la probabilidad de transicion del estado \(i\) en el tiempo \(n\), al estado \(j\) en el tiempo \(n + 1\). Estas probabilidades se conocen como la probabilidades de transicion en un paso. Cuando \(p_{ij}(n,n+1)\) no depende de \(n\) se dice que la cadena es estacionaria.
Por simplicidad se asume tal situacion de modo qu las probabilidades, por lo cual las probabilidades de transicion en un paso se escriben como \(p_{ij}\). Variando los indices, es posible obtener la matriz estocastica, dicha matriz debe cumplir las siguientes 2 propiedades \[ p_{ij} \geq 0 \] \[ \sum_{j} p_{ij} = 1 \] Esto quiere decir que a partir de cualquier estado \(i\) la cadena pasa necesariamente a algun elemento del espacio de estados en el siguiente momento. Una propiedad importante es que si \(A\) y \(B\) son matrices estocasticas,entonces \(C = AB\) tambien es estocastica.
Distribucion de probabilidad inicial
En general la cadena de Markov puede iniciar desde cualquier estado \(i\), o mas generalmente considernado una distrubucion de probablidad inicial sobre el espacio de estadoss. Esto basicamente es un conjunto de numeros \(p_0,p_1,\dots\) no negativos y que suman uno. El numero \(p_i\) corresponde a la probabilidad de que la cadena inicie en el estado \(i\). En general, la distribucion inicial no juega un papel muy importante en el estudio de las cadenas.
Ecuación de Chapman-Kolmogorov
Esta ecuacion permite descomponer la probabilidad de pasar del estado \(i\) al estado \(j\) en \(n\) pasos, en la suma de probabilidad es de la trayectorias que van de \(i\) a \(j\), y que atraviesan por un estado \(k\) cualquiera en un tiempo intermedio \(r\).
Para cualquier par de numeros enteros \(r\) y \(n\) tales que \(0 \leq r \leq n\), y para cualquier estados \(i\) y \(j\) se cumple \[ p_{ij}^{(n)} = \sum_k p_{ik}^{(r)}p_{kj}^{(n-r)} \]
Ademas es facil ver que para cualquier estado \(k\) y para \(0 \leq r \leq n\), se tiene \[ p_{ij}^{(n)} \geq p_{ik}^{(r)}p_{kj}^{(n-r)}\] Como una consecuencia importante de la ecuaci´on de Chapman-Kolmogorov se tiene el siguiente resultado
La probabilidad de transicion en \(n\) pasos, $p_{ij}^{(n)}, esta dada por la entrada \((i, j\) de la n-esima potencia de la matriz \(P\), es decir, \[ p_{ij}^{(n)} = (P^n)_{ij} \]
Cuando la matriz estocastica \(P\) es diagonalizable, es decir, cuando puede ser escrita en la forma \(QDQ^{-1}\) en donde D es una matriz diagonal, las potencias de \(P\) se calculan facillmente, pues \(P^n = QD^nQ^{-1}\).
Comunicacion
Se dice que el estado \(j\) es accesible desde el estado \(i\) si existe un entero \(n\geq 0\) tal que \(p_{ij}^{(n)} > 0\), es decir que es posible llegar del estado \(i\) al estado \(j\) es un numero finito de pasos, esto se escribe simplemente como \(i\rightarrow j\). Se dice ademas que los estados \(i\) y \(j\) son comunicantes, y se escribe \(i\leftrightarrow j\).
Es facil verificar que la comunicación es una relación de equivalencia, es decir, cumple las siguientes propiedades.
- Reflexiva: \(i\leftrightarrow i\)
- Simetrica: Si \(i \leftrightarrow j\) entonces \(j \leftrightarrow i\)
- Transitiva: Si \(i \leftrightarrow k\) u \(k \leftrightarrow j\), entonces \(i \leftrightarrow j\)
En consecuencia, la comunicación induce una particion del espacio de estados de una cadena de Markov dada por los subconjuntos de estados comunicantes, es decir, dos estados pertenecen al mismo elemento de la particion si, y solo si, son estados que se comunican. De este modo el espacio de estados de una cadena de Markov se subdivide en clases de comunicacion. A la clase de comunicacion de un estado \(i\) se le denotara por \(C(i)\). Por lo tanto, \(i\leftrightarrow j\) si, y solo si, \(C(i) = C(j)\)
Irreductibilidad
Se dice que una cadena de Markov es irreducible si todos los estados se comunican entre si, en otras palabras se dice que una cadena de Markov es irreducible si solo existe una clase de equivalencia.
Periodo
El periodo de un estado \(i\) es un numero entero no negativo denotado por \(d(i)\), y definido de la siguiente manera \[ d(i) = gcd\{n\geq 1 : p_{ii}^{(n)} > 0\} \]
una propiedad muy interesante del periodo de es la siguiente. Si los estados \(i\)y \(j\) pertenecen a la misma clase de equivalencia, entonces poseen el mismo periodo. El reciproco del es en general falso.
LS0tCnRpdGxlOiAiQ2FkZW5hIGRlIE1hcmtvdiIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKVW5hIGNhZGVuYSBkZSBNYXJrb3YgZXMgdW4gcHJvY2VzbyBlc3RvY2FzdGljbyBlbiB0aWVtcG8gZGlzY3JldG8gCiRce1hfbjpuIFxnZXEgMFx9JCwgY29uIGVzcGFjaW8gZGlzY3JldG8sIHRhbCBxdWUsIHBhcmEgY3VhbHF1aWVyIGVudGVybyAKJG4gXGdlcSAwJCwgeSBwYXJhIGN1YWxxdWllciBlc3RhZG8gJHNfMCxcZG90cywgc19uLHNfe24rMX0kLCBzZSBjdW1wbGUKCiQkIFByXHtzX3tuKzF9fHNfMCxcZG90cywgc19uXH0gPSBQclx7c197bisxfXwgc19uXH0kJAoKU2kgYWwgdGllbXBvICRuICsgMSQgc2UgbGUgY29uc2lkZXJhIGNvbW8gdW4gdGllbXBvIGZ1dHVybywgYWwgdGllbXBvICRuJApjb21vIGVsIHByZXNlbnRlIHkgYSBsb3MgdGllbXBvcyAkMCwgMSwgXGRvdHMgLCBuIC0gMSQgY29tbyBlbCBwYXNhZG8sIGVudG9uY2VzCmxhIGNvbmRpY2nDs24gYW50ZXJpb3IgZXN0YWJsZWNlIHF1ZSBsYSBkaXN0cmlidWNpb24gZGUgcHJvYmFiaWxpZGFkIGRlbCBlc3RhZG8gCmRlbCBwcm9jZXNvIGFsIHRpZW1wbyBmdXR1cm8gJG4rMSQgZGVwZW5kZSDDum5pY2FtZW50ZSBkZWwgZXN0YWRvIGRlbCBwcm9jZXNvIGFsCnRpZW1wbyAkbiQsIHkgbm8gZGVwZW5kZSBkZSBsb3MgZXN0YWRvcyBlbiBsb3MgdGllbXBvcyBwYXNhZG9zLgoKIyMgUHJvYmFiaWxpZGFkZXMgZGUgdHJhbnNpY2nDs24KU2VhbiAkaSQgeSAkaiQgZG9zIGVzdGFkb3MgZGUgdW5hIGNhZGVuYSBkZSBNYXJrb3YuIEEgbGEgcHJvYmFiaWxpZGFkCiQkIFByXHtzX3tuKzF9fCBzX25cfSAkJAoKc2UgbGUgZGVub3RhIHBvciAkcF97aWp9XnsobixuKzEpfSQgeSByZXByZXNlbnRhIGxhIHByb2JhYmlsaWRhZCBkZSB0cmFuc2ljaW9uIApkZWwgZXN0YWRvICRpJCBlbiBlbCB0aWVtcG8gJG4kLCBhbCBlc3RhZG8gJGokIGVuIGVsIHRpZW1wbyAkbiArIDEkLiBFc3Rhcwpwcm9iYWJpbGlkYWRlcyBzZSBjb25vY2VuIGNvbW8gbGEgcHJvYmFiaWxpZGFkZXMgZGUgdHJhbnNpY2lvbiBlbiB1biBwYXNvLgpDdWFuZG8gJHBfe2lqfShuLG4rMSkkIG5vIGRlcGVuZGUgZGUgJG4kIHNlIGRpY2UgcXVlIGxhIGNhZGVuYSBlcyBlc3RhY2lvbmFyaWEuCgpQb3Igc2ltcGxpY2lkYWQgc2UgYXN1bWUgdGFsIHNpdHVhY2lvbiBkZSBtb2RvIHF1IGxhcyBwcm9iYWJpbGlkYWRlcywgcG9yIGxvIApjdWFsIGxhcyBwcm9iYWJpbGlkYWRlcyBkZSB0cmFuc2ljaW9uIGVuIHVuIHBhc28gc2UgZXNjcmliZW4gY29tbyAkcF97aWp9JC4KVmFyaWFuZG8gbG9zIGluZGljZXMsIGVzIHBvc2libGUgb2J0ZW5lciBsYSBtYXRyaXogZXN0b2Nhc3RpY2EsIGRpY2hhIG1hdHJpeiAKZGViZSBjdW1wbGlyIGxhcyBzaWd1aWVudGVzIDIgcHJvcGllZGFkZXMKJCQgcF97aWp9IFxnZXEgMCAkJAokJCBcc3VtX3tqfSBwX3tpan0gPSAxICQkCkVzdG8gcXVpZXJlIGRlY2lyIHF1ZSBhIHBhcnRpciBkZSBjdWFscXVpZXIgZXN0YWRvICRpJCBsYSBjYWRlbmEgcGFzYSAKbmVjZXNhcmlhbWVudGUgYSBhbGd1biBlbGVtZW50byBkZWwgZXNwYWNpbyBkZSBlc3RhZG9zIGVuIGVsIHNpZ3VpZW50ZSBtb21lbnRvLgpVbmEgcHJvcGllZGFkIGltcG9ydGFudGUgZXMgcXVlIHNpICRBJCB5ICRCJCBzb24gbWF0cmljZXMgZXN0b2Nhc3RpY2FzLGVudG9uY2VzCiRDID0gQUIkIHRhbWJpZW4gZXMgZXN0b2Nhc3RpY2EuCgojIyMgRGlzdHJpYnVjaW9uIGRlIHByb2JhYmlsaWRhZCBpbmljaWFsCkVuIGdlbmVyYWwgbGEgY2FkZW5hIGRlIE1hcmtvdiBwdWVkZSBpbmljaWFyIGRlc2RlIGN1YWxxdWllciBlc3RhZG8gJGkkLCBvIG1hcwpnZW5lcmFsbWVudGUgY29uc2lkZXJuYWRvIHVuYSBkaXN0cnVidWNpb24gZGUgcHJvYmFibGlkYWQgaW5pY2lhbCBzb2JyZSBlbCAKZXNwYWNpbyBkZSBlc3RhZG9zcy4gRXN0byBiYXNpY2FtZW50ZSBlcyB1biBjb25qdW50byBkZSBudW1lcm9zICRwXzAscF8xLFxkb3RzJApubyBuZWdhdGl2b3MgeSBxdWUgc3VtYW4gdW5vLiBFbCBudW1lcm8gJHBfaSQgY29ycmVzcG9uZGUgYSBsYSBwcm9iYWJpbGlkYWQgZGUKcXVlIGxhIGNhZGVuYSBpbmljaWUgZW4gZWwgZXN0YWRvICRpJC4gRW4gZ2VuZXJhbCwgbGEgZGlzdHJpYnVjaW9uIGluaWNpYWwgbm8KanVlZ2EgdW4gcGFwZWwgbXV5IGltcG9ydGFudGUgZW4gZWwgZXN0dWRpbyBkZSBsYXMgY2FkZW5hcy4KCiMjIEVjdWFjacOzbiBkZSBDaGFwbWFuLUtvbG1vZ29yb3YKRXN0YSBlY3VhY2lvbiBwZXJtaXRlIGRlc2NvbXBvbmVyIGxhIHByb2JhYmlsaWRhZCBkZSBwYXNhciBkZWwgZXN0YWRvICRpJCBhbAplc3RhZG8gJGokIGVuICRuJCBwYXNvcywgZW4gbGEgc3VtYSBkZSBwcm9iYWJpbGlkYWQgZXMgZGUgbGEgdHJheWVjdG9yaWFzIHF1ZQp2YW4gZGUgJGkkIGEgJGokLCB5IHF1ZSBhdHJhdmllc2FuIHBvciB1biBlc3RhZG8gJGskIGN1YWxxdWllcmEgZW4gdW4gdGllbXBvCmludGVybWVkaW8gJHIkLgoKUGFyYSBjdWFscXVpZXIgcGFyIGRlIG51bWVyb3MgZW50ZXJvcyAkciQgeSAkbiQgdGFsZXMgcXVlICQwIFxsZXEgciBcbGVxIG4kLCB5IApwYXJhIGN1YWxxdWllciBlc3RhZG9zICRpJCB5ICRqJCBzZSBjdW1wbGUgCiQkIHBfe2lqfV57KG4pfSA9IFxzdW1fayBwX3tpa31eeyhyKX1wX3tran1eeyhuLXIpfSAkJAoKQWRlbWFzIGVzIGZhY2lsIHZlciBxdWUgcGFyYSBjdWFscXVpZXIgZXN0YWRvICRrJCB5IHBhcmEgJDAgXGxlcSByIFxsZXEgbiQsIHNlIAp0aWVuZQokJCBwX3tpan1eeyhuKX0gXGdlcSBwX3tpa31eeyhyKX1wX3tran1eeyhuLXIpfSQkCkNvbW8gdW5hIGNvbnNlY3VlbmNpYSBpbXBvcnRhbnRlIGRlIGxhIGVjdWFjacK0b24gZGUgQ2hhcG1hbi1Lb2xtb2dvcm92CnNlIHRpZW5lIGVsIHNpZ3VpZW50ZSByZXN1bHRhZG8KCkxhIHByb2JhYmlsaWRhZCBkZSB0cmFuc2ljaW9uIGVuICRuJCBwYXNvcywgJHBfe2lqfV57KG4pfSwgZXN0YSBkYWRhIHBvciBsYSAKZW50cmFkYSAkKGksIGokIGRlIGxhIG4tZXNpbWEgcG90ZW5jaWEgZGUgbGEgbWF0cml6ICRQJCwgZXMgZGVjaXIsCiQkIHBfe2lqfV57KG4pfSA9IChQXm4pX3tpan0gJCQKCkN1YW5kbyBsYSBtYXRyaXogZXN0b2Nhc3RpY2EgJFAkIGVzIGRpYWdvbmFsaXphYmxlLCBlcyBkZWNpciwgY3VhbmRvIHB1ZWRlIHNlcgplc2NyaXRhIGVuIGxhIGZvcm1hICRRRFFeey0xfSQgZW4gZG9uZGUgRCBlcyB1bmEgbWF0cml6IGRpYWdvbmFsLCBsYXMgcG90ZW5jaWFzCmRlICRQJCBzZSBjYWxjdWxhbiBmYWNpbGxtZW50ZSwgcHVlcyAkUF5uID0gUUReblFeey0xfSQuCgojIyBDb211bmljYWNpb24KU2UgZGljZSBxdWUgZWwgZXN0YWRvICRqJCBlcyBhY2Nlc2libGUgZGVzZGUgZWwgZXN0YWRvICRpJCBzaSBleGlzdGUgdW4gZW50ZXJvIAokblxnZXEgMCQgdGFsIHF1ZSAkcF97aWp9Xnsobil9ID4gMCQsIGVzIGRlY2lyIHF1ZSBlcyBwb3NpYmxlIGxsZWdhciBkZWwgZXN0YWRvCiRpJCBhbCBlc3RhZG8gJGokIGVzIHVuIG51bWVybyBmaW5pdG8gZGUgcGFzb3MsIGVzdG8gc2UgZXNjcmliZSBzaW1wbGVtZW50ZSAKY29tbyAkaVxyaWdodGFycm93IGokLiBTZSBkaWNlIGFkZW1hcyBxdWUgbG9zIGVzdGFkb3MgJGkkIHkgJGokIHNvbiBjb211bmljYW50ZXMsCnkgc2UgZXNjcmliZSAkaVxsZWZ0cmlnaHRhcnJvdyBqJC4KCkVzIGZhY2lsIHZlcmlmaWNhciBxdWUgbGEgY29tdW5pY2FjacOzbiBlcyB1bmEgcmVsYWNpw7NuIGRlIGVxdWl2YWxlbmNpYSwgZXMKZGVjaXIsIGN1bXBsZSBsYXMgc2lndWllbnRlcyBwcm9waWVkYWRlcy4KCiAgKiBSZWZsZXhpdmE6ICRpXGxlZnRyaWdodGFycm93IGkkCiAgKiBTaW1ldHJpY2E6IFNpICRpIFxsZWZ0cmlnaHRhcnJvdyBqJCBlbnRvbmNlcyAkaiBcbGVmdHJpZ2h0YXJyb3cgaSQKICAqIFRyYW5zaXRpdmE6IFNpICRpIFxsZWZ0cmlnaHRhcnJvdyBrJCB1ICRrIFxsZWZ0cmlnaHRhcnJvdyBqJCwgZW50b25jZXMgJGkgXGxlZnRyaWdodGFycm93IGokCgpFbiBjb25zZWN1ZW5jaWEsIGxhIGNvbXVuaWNhY2nDs24gaW5kdWNlIHVuYSBwYXJ0aWNpb24gZGVsIGVzcGFjaW8gZGUgZXN0YWRvcyBkZQp1bmEgY2FkZW5hIGRlIE1hcmtvdiBkYWRhIHBvciBsb3Mgc3ViY29uanVudG9zIGRlIGVzdGFkb3MgY29tdW5pY2FudGVzLCBlcyAKZGVjaXIsIGRvcyBlc3RhZG9zIHBlcnRlbmVjZW4gYWwgbWlzbW8gZWxlbWVudG8gZGUgbGEgcGFydGljaW9uIHNpLCB5IHNvbG8gc2ksCnNvbiBlc3RhZG9zIHF1ZSBzZSBjb211bmljYW4uIERlIGVzdGUgbW9kbyBlbCBlc3BhY2lvIGRlIGVzdGFkb3MgZGUgdW5hIGNhZGVuYSAKZGUgTWFya292IHNlIHN1YmRpdmlkZSBlbiBjbGFzZXMgZGUgY29tdW5pY2FjaW9uLiBBIGxhIGNsYXNlIGRlIGNvbXVuaWNhY2lvbiBkZQp1biBlc3RhZG8gJGkkIHNlIGxlIGRlbm90YXJhIHBvciAkQyhpKSQuIFBvciBsbyB0YW50bywgJGlcbGVmdHJpZ2h0YXJyb3cgaiQgc2ksCnkgc29sbyBzaSwgJEMoaSkgPSBDKGopJAoKIyMjIyBJcnJlZHVjdGliaWxpZGFkClNlIGRpY2UgcXVlIHVuYSBjYWRlbmEgZGUgTWFya292IGVzIGlycmVkdWNpYmxlIHNpIHRvZG9zIGxvcyBlc3RhZG9zIHNlIApjb211bmljYW4gZW50cmUgc2ksIGVuIG90cmFzIHBhbGFicmFzIHNlIGRpY2UgcXVlIHVuYSBjYWRlbmEgZGUgTWFya292IGVzCmlycmVkdWNpYmxlIHNpIHNvbG8gZXhpc3RlIHVuYSBjbGFzZSBkZSBlcXVpdmFsZW5jaWEuCgojIyBQZXJpb2RvCkVsIHBlcmlvZG8gZGUgdW4gZXN0YWRvICRpJCBlcyB1biBudW1lcm8gZW50ZXJvIG5vIG5lZ2F0aXZvIGRlbm90YWRvIHBvciAkZChpKSQsCnkgZGVmaW5pZG8gZGUgbGEgc2lndWllbnRlIG1hbmVyYQokJCBkKGkpID0gZ2NkXHtuXGdlcSAxIDogcF97aWl9Xnsobil9ID4gMFx9ICQkCgp1bmEgcHJvcGllZGFkIG11eSBpbnRlcmVzYW50ZSBkZWwgcGVyaW9kbyBkZSBlcyBsYSBzaWd1aWVudGUuClNpIGxvcyBlc3RhZG9zICRpJHkgJGokIHBlcnRlbmVjZW4gYSBsYSBtaXNtYSBjbGFzZSBkZSBlcXVpdmFsZW5jaWEsIGVudG9uY2VzCnBvc2VlbiBlbCBtaXNtbyBwZXJpb2RvLiBFbCByZWNpcHJvY28gZGVsIGVzIGVuIGdlbmVyYWwgZmFsc28u