• Author / Uploaded
• diego_ivanrk

Citation preview

Introducci´ on a las cadenas de Markov: I Tiempo discreto

Introducci´ on a las cadenas de Markov: I Tiempo discreto V´ıctor RIVERO Centro de Investigaci´ on en Matem´ aticas A. C.

XI Escuela de Probabilidad y Estad´ıstica, 29 de Febrero a 2 de Marzo, 2012, CIMAT

1/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Preliminares

Preliminares (Ω, F, P) un espacio de probabilidad • Probabilidad condicional A, B ∈ F, tal que P(B ) > 0, la probabilidad del evento A dado B P(A|B ) =

P(A ∩ B ) . P(B )

2/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Preliminares

Preliminares (Ω, F, P) un espacio de probabilidad • Probabilidad condicional A, B ∈ F, tal que P(B ) > 0, la probabilidad del evento A dado B P(A|B ) =

P(A ∩ B ) . P(B )

• Formula de probabilidad total Sean B1 , . . . , Bn , . . . ∈ Ω, tales que ∪∞ k =1 Bk = Ω entonces ∀A ∈ F P(A) =

∞ X k =1

P(A ∩ Bk ) =

∞ X

P(A|Bk ) P(Bk ).

k =1

2/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Preliminares

Preliminares (Ω, F, P) un espacio de probabilidad • Probabilidad condicional A, B ∈ F, tal que P(B ) > 0, la probabilidad del evento A dado B P(A|B ) =

P(A ∩ B ) . P(B )

• Formula de probabilidad total Sean B1 , . . . , Bn , . . . ∈ Ω, tales que ∪∞ k =1 Bk = Ω entonces ∀A ∈ F P(A) =

∞ X k =1

P(A ∩ Bk ) =

∞ X

P(A|Bk ) P(Bk ).

k =1

• Formula de Bayes Sean A, B , B1 , . . . , Bn ∈ F, tales que P(B ) > 0 y Ω = ∪nk=1 Bk se tiene que P(B |A) P(A) P(B |A) P(A) P(A|B ) = Pn = Pn . k =1 P(B ∩ Bk ) k =1 P(B |Bk ) P(Bk )

2/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Preliminares

• A, B ∈ F son independientes si P(A ∩ B ) = P(A) P(B )

3/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Preliminares

• A, B ∈ F son independientes si P(A ∩ B ) = P(A) P(B ) • A, B ⊆ F son independientes si P(A ∩ B ) = P(A) P(B ),

∀A ∈ A y ∀B ∈ B.

3/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Preliminares

• A, B ∈ F son independientes si P(A ∩ B ) = P(A) P(B ) • A, B ⊆ F son independientes si P(A ∩ B ) = P(A) P(B ),

∀A ∈ A y ∀B ∈ B.

• X : Ω → E es una variable aleatoria si para todo A ⊂ E , B := {X ∈ A} := {ω ∈ Ω|X (ω) ∈ A} ∈ F.

3/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Preliminares

• A, B ∈ F son independientes si P(A ∩ B ) = P(A) P(B ) • A, B ⊆ F son independientes si P(A ∩ B ) = P(A) P(B ),

∀A ∈ A y ∀B ∈ B.

• X : Ω → E es una variable aleatoria si para todo A ⊂ E , B := {X ∈ A} := {ω ∈ Ω|X (ω) ∈ A} ∈ F. Traducci´ on: ω ∈ Ω un experimento, X (ω) una caracter´ıstica del experimento; B es el evento “los experimentos son tales que la caracter´ıstica de inter´es toma un valor en A” y le podemos calcular probabilidad ya que B ∈ F.

3/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Preliminares

• A, B ∈ F son independientes si P(A ∩ B ) = P(A) P(B ) • A, B ⊆ F son independientes si P(A ∩ B ) = P(A) P(B ),

∀A ∈ A y ∀B ∈ B.

• X : Ω → E es una variable aleatoria si para todo A ⊂ E , B := {X ∈ A} := {ω ∈ Ω|X (ω) ∈ A} ∈ F. Traducci´ on: ω ∈ Ω un experimento, X (ω) una caracter´ıstica del experimento; B es el evento “los experimentos son tales que la caracter´ıstica de inter´es toma un valor en A” y le podemos calcular probabilidad ya que B ∈ F. • X , Y variables aleatorias son independientes si para todo A, B ⊂ E , los eventos {X ∈ A} y {Y ∈ B } son independientes. 3/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Procesos Estoc´ asticos Definici´ on Sea (Ω, F, P) un espacio de probabilidad y E un conjunto no vac´ıo. Un proceso estoc´ astico es una colecci´ on de variables aleatorias, {Xt : Ω → E , t ∈ T }, indexadas por alg´ un conjunto T .

4/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Procesos Estoc´ asticos Definici´ on Sea (Ω, F, P) un espacio de probabilidad y E un conjunto no vac´ıo. Un proceso estoc´astico es una colecci´ on de variables aleatorias, {Xt : Ω → E , t ∈ T }, indexadas por alg´ un conjunto T . Usualmente, ( {0, 1, 2, . . .} proceso estoc´ astico a tiempo discreto, T = + R ´ o R proceso estoc´ astico a tiempo continuo.

4/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Procesos Estoc´ asticos Definici´ on Sea (Ω, F, P) un espacio de probabilidad y E un conjunto no vac´ıo. Un proceso estoc´astico es una colecci´ on de variables aleatorias, {Xt : Ω → E , t ∈ T }, indexadas por alg´ un conjunto T . Usualmente, ( {0, 1, 2, . . .} proceso estoc´astico a tiempo discreto, T = R ´ o R+ proceso estoc´astico a tiempo continuo. El conjunto E es el espacio de estados. Si E es numerable se dice que el proceso tiene espacio de estados discreto mientras que si E es continuo decimos que tiene espacio de estados continuo.

4/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Procesos Estoc´ asticos Definici´ on Sea (Ω, F, P) un espacio de probabilidad y E un conjunto no vac´ıo. Un proceso estoc´astico es una colecci´ on de variables aleatorias, {Xt : Ω → E , t ∈ T }, indexadas por alg´ un conjunto T . Usualmente, ( {0, 1, 2, . . .} proceso estoc´astico a tiempo discreto, T = R ´ o R+ proceso estoc´astico a tiempo continuo. El conjunto E es el espacio de estados. Si E es numerable se dice que el proceso tiene espacio de estados discreto mientras que si E es continuo decimos que tiene espacio de estados continuo. Estudiaremos solamente procesos estoc´ asticos con espacio de estados y tiempo discreto. 4/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplos de proceso estoc´ astico Ejemplo Lanzamiento de una moneda, E = {´aguila, sol} = {0, 1}. ( ´aguila p Xn = , p ∈ [0, 1], n ∈ Z+ . sol 1−p

5/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplos de proceso estoc´ astico Ejemplo Lanzamiento de una moneda, E = {´aguila, sol} = {0, 1}. ( ´aguila p Xn = , p ∈ [0, 1], n ∈ Z+ . sol 1−p

Ejemplo (Pacientes) Sea Xn el numero de pacientes graves que solicitan tratamiento el d´ıa n en la sala de emergencias del hospital la Raza en M´exico D.F. E = {0, 1, . . . , K } donde K es el numero m´aximo de pacientes que puede ser recibido en la recepci´ on de emergencias por d´ıa.

5/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplos de proceso estoc´ astico Ejemplo Lanzamiento de una moneda, E = {´aguila, sol} = {0, 1}. ( ´aguila p Xn = , p ∈ [0, 1], n ∈ Z+ . sol 1−p

Ejemplo (Pacientes) Sea Xn el numero de pacientes graves que solicitan tratamiento el d´ıa n en la sala de emergencias del hospital la Raza en M´exico D.F. E = {0, 1, . . . , K } donde K es el numero m´aximo de pacientes que puede ser recibido en la recepci´ on de emergencias por d´ıa. En ambos ejemplos las variables aleatorias son independientes entre si. 5/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Ajedrez) Sea Xn la posici´ on de un caballo en un tablero de ajedrez despu´es de n movimientos.

6/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Ajedrez) Sea Xn la posici´ on de un caballo en un tablero de ajedrez despu´es de n movimientos. Ejemplo Para ir de M´exico D.F. a Guanajuato se puede ir por la carretera libre o la autopista de cuota. Sea Xn la distancia recorrida despu´es de n-minutos por un autom´ ovil que se dirige a Guanajuato desde el D.F. (X ) (X ) Claramente, Xn+1 = Xn + Yn+10 donde Yn+10 denota la distancia recorrida en el periodo [n, n + 1[ y esta depende del punto inicial.

6/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Ajedrez) Sea Xn la posici´ on de un caballo en un tablero de ajedrez despu´es de n movimientos. Ejemplo Para ir de M´exico D.F. a Guanajuato se puede ir por la carretera libre o la autopista de cuota. Sea Xn la distancia recorrida despu´es de n-minutos por un autom´ ovil que se dirige a Guanajuato desde el D.F. (X ) (X ) Claramente, Xn+1 = Xn + Yn+10 donde Yn+10 denota la distancia recorrida en el periodo [n, n + 1[ y esta depende del punto inicial. En ambos ejemplos el valor de Xn depende de X0 , X1 , . . . , Xn−1 .

6/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Ajedrez) Sea Xn la posici´ on de un caballo en un tablero de ajedrez despu´es de n movimientos. Ejemplo Para ir de M´exico D.F. a Guanajuato se puede ir por la carretera libre o la autopista de cuota. Sea Xn la distancia recorrida despu´es de n-minutos por un autom´ ovil que se dirige a Guanajuato desde el D.F. (X ) (X ) Claramente, Xn+1 = Xn + Yn+10 donde Yn+10 denota la distancia recorrida en el periodo [n, n + 1[ y esta depende del punto inicial. En ambos ejemplos el valor de Xn depende de X0 , X1 , . . . , Xn−1 . Ejemplo (El merenguero) Si el resultado de un volado es ´aguila el merenguero gana un peso y en caso contrario nosotros ganamos un peso. Sea Sn la fortuna del merenguero despu´es de n-lanzamientos y n ∈ {0, 1, 2, . . .}. El espacio de estados es E = {0, 1, . . . , N + M }, donde N =nuestra fortuna y M =fortuna del merenguero.

6/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Evoluci´ on de una epidemia en una poblaci´ on) Un individuo de la poblaci´ on puede estar en los siguientes estados: enfermo(e), contagiado y por lo tanto contagioso (c), inmune a la enfermedad (i), sano pero no inmune (s), muerto (m).

7/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Evoluci´ on de una epidemia en una poblaci´ on) Un individuo de la poblaci´ on puede estar en los siguientes estados: enfermo(e), contagiado y por lo tanto contagioso (c), inmune a la enfermedad (i), sano pero no inmune (s), muerto (m). Seg´ un la informaci´ on dada por el sistema de salud de la poblaci´on se tienen las siguientes transiciones: ( contagiado (contagioso) sano —> no contagiado (sano) ( enfermo contagiado (contagioso)—> sano inmune ( sano inmune enfermo —> muerto sano inmune —> sano inmune, muerto —> muerto. 7/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Procesos de Ramificaci´ on) Al tiempo inicial n = 0 hay una part´ıcula. Al tiempo n = 1 esta part´ıcula muere y da nacimiento a X part´ıculas id´enticas (entre si y a su progenitor). A cada generaci´ on subsecuente n = 2, 3, . . . cada part´ıcula existente muere y da nacimiento a un n´ umero aleatorio de part´ıculas id´enticas, sus descendientes. Supondremos que todos los tama˜ nos de las familias son independientes y que todos tiene la misma ley que X .

8/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Procesos de Ramificaci´ on) Al tiempo inicial n = 0 hay una part´ıcula. Al tiempo n = 1 esta part´ıcula muere y da nacimiento a X part´ıculas id´enticas (entre si y a su progenitor). A cada generaci´ on subsecuente n = 2, 3, . . . cada part´ıcula existente muere y da nacimiento a un n´ umero aleatorio de part´ıculas id´enticas, sus descendientes. Supondremos que todos los tama˜ nos de las familias son independientes y que todos tiene la misma ley que X . Sea (Zn , n ≥ 0) los tama˜ nos de las poblaci´ on en la n-´esima generaci´on.

8/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Procesos de Ramificaci´ on) Al tiempo inicial n = 0 hay una part´ıcula. Al tiempo n = 1 esta part´ıcula muere y da nacimiento a X part´ıculas id´enticas (entre si y a su progenitor). A cada generaci´ on subsecuente n = 2, 3, . . . cada part´ıcula existente muere y da nacimiento a un n´ umero aleatorio de part´ıculas id´enticas, sus descendientes. Supondremos que todos los tama˜ nos de las familias son independientes y que todos tiene la misma ley que X . Sea (Zn , n ≥ 0) los tama˜ nos de las poblaci´ on en la n-´esima generaci´on. Este es un proceso estoc´astico llamado Proceso de Ramificaci´ on.

8/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Procesos de Ramificaci´ on) Al tiempo inicial n = 0 hay una part´ıcula. Al tiempo n = 1 esta part´ıcula muere y da nacimiento a X part´ıculas id´enticas (entre si y a su progenitor). A cada generaci´ on subsecuente n = 2, 3, . . . cada part´ıcula existente muere y da nacimiento a un n´ umero aleatorio de part´ıculas id´enticas, sus descendientes. Supondremos que todos los tama˜ nos de las familias son independientes y que todos tiene la misma ley que X . Sea (Zn , n ≥ 0) los tama˜ nos de las poblaci´ on en la n-´esima generaci´on. Este es un proceso estoc´astico llamado Proceso de Ramificaci´ on. E = Z+ , y el n´ umero de part´ıculas al tiempo n + 1 depende solamente de aquellas presentes al tiempo n y no de las generaciones anteriores. De hecho Zn+1 =

Zn X

(n)

Xi

,

i=1 (n)

donde Xi el n´ umero de descendientes del i -´esimo individuo presente en la poblaci´ on en la n-´esima generaci´ on. 8/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Procesos de Ramificaci´ on) Al tiempo inicial n = 0 hay una part´ıcula. Al tiempo n = 1 esta part´ıcula muere y da nacimiento a X part´ıculas id´enticas (entre si y a su progenitor). A cada generaci´ on subsecuente n = 2, 3, . . . cada part´ıcula existente muere y da nacimiento a un n´ umero aleatorio de part´ıculas id´enticas, sus descendientes. Supondremos que todos los tama˜ nos de las familias son independientes y que todos tiene la misma ley que X . Sea (Zn , n ≥ 0) los tama˜ nos de las poblaci´ on en la n-´esima generaci´on. Este es un proceso estoc´astico llamado Proceso de Ramificaci´ on. E = Z+ , y el n´ umero de part´ıculas al tiempo n + 1 depende solamente de aquellas presentes al tiempo n y no de las generaciones anteriores. De hecho Zn+1 =

Zn X

(n)

Xi

,

i=1 (n)

donde Xi el n´ umero de descendientes del i -´esimo individuo presente en la poblaci´ on en la n-´esima generaci´ on. Modelo introducido por Galton y Watson para estudio de la desaparici´ on de familias.

8/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Inventarios) Una tienda de aparatos electr´ onicos vende televisiones y opera bajo el siguiente esquema. Si al final del d´ıa el n´ umero de unidades disponibles es 1 o´ 0, se ordenan nuevas unidades para llevar el total a 5. Supondremos que la mercanc´ıa llega antes de que la tienda abra al d´ıa siguiente. Sea Xn el n´ umero de unidades disponibles en la tienda al final del n-´esimo d´ıa y supongamos que diariamente el n´ umero de clientes que compran un ipod es 0, 1, 2 ´ o 3 con probabilidad 0.3; 0.4; 0.2; y 0.1 respectivamente.

9/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Introducci´ on Procesos Estoc´ asticos

Ejemplo (Inventarios) Una tienda de aparatos electr´ onicos vende televisiones y opera bajo el siguiente esquema. Si al final del d´ıa el n´ umero de unidades disponibles es 1 o´ 0, se ordenan nuevas unidades para llevar el total a 5. Supondremos que la mercanc´ıa llega antes de que la tienda abra al d´ıa siguiente. Sea Xn el n´ umero de unidades disponibles en la tienda al final del n-´esimo d´ıa y supongamos que diariamente el n´ umero de clientes que compran un ipod es 0, 1, 2 ´ o 3 con probabilidad 0.3; 0.4; 0.2; y 0.1 respectivamente. ( (Xn − Dn+1 )+ si Xn > 1 Xn+1 = (5 − Dn+1 )+ si Xn ≤ 1 Con Dn+1 la demanda el d´ıa n + 1.

9/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Definici´ on de Cadena de Markov

En los ejemplos del merenguero, la epidemia, el proceso de ramificaci´on y los inventarios se tiene que el proceso estoc´astico subyacente es tal que el futuro depende solamente del presente y no del pasado estricto.

10/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Definici´ on de Cadena de Markov

En los ejemplos del merenguero, la epidemia, el proceso de ramificaci´on y los inventarios se tiene que el proceso estoc´astico subyacente es tal que el futuro depende solamente del presente y no del pasado estricto. Esto es lo que se llama la propiedad de Markov

10/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Definici´ on de Cadena de Markov

En los ejemplos del merenguero, la epidemia, el proceso de ramificaci´on y los inventarios se tiene que el proceso estoc´astico subyacente es tal que el futuro depende solamente del presente y no del pasado estricto. Esto es lo que se llama la propiedad de Markov Dicho de otro, dado el presente, el futuro es independientemente del pasado, P ({Evento del pasado} ∩ {Evento del futuro}|Evento del presente) = P ({Evento del pasado}|Evento del presente) × P ({Evento del futuro}|Evento del presente) .

10/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Definici´ on de Cadena de Markov

Cadenas de Markov Definici´ on Sea (Ω, F, P) un espacio de probabilidad y E un conjunto no vac´ıo, finito o numerable. Un proceso estoc´astico o sucesi´ on de variables aleatorias {Xn : Ω → E , n ∈ N}, se llama cadena de Markov con espacio de estados E si satisface la condici´ on de Markov, es decir, si para todo n ≥ 1 y toda sucesi´on x0 , x1 , . . . , xn−1 , xn , xn+1 ∈ E , se cumple: P (Xn+1 = xn+1 |Xn = xn , Xn−1 = xn−1 , . . . , X0 = x0 ) = P (Xn+1 = xn+1 |Xn = xn ) .

(1)

La distribuci´ on de X0 se llama distribuci´ on inicial de la cadena y en muchos casos la denotaremos por π(x ) = P(X0 = x ), x ∈ E . 11/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Algunas precisiones

• Supondremos que E ⊆ Z, y en consecuencia E es ordenado.

12/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Algunas precisiones

• Supondremos que E ⊆ Z, y en consecuencia E es ordenado. • La familia {P (Xn+1 = y|Xn = x ) , n ∈ N, x , y ∈ E }, se le llama familia de probabilidades de transici´ on de la cadena. Estas describen la evoluci´ on de la cadena en el tiempo.

12/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Algunas precisiones

• Supondremos que E ⊆ Z, y en consecuencia E es ordenado. • La familia {P (Xn+1 = y|Xn = x ) , n ∈ N, x , y ∈ E }, se le llama familia de probabilidades de transici´ on de la cadena. Estas describen la evoluci´ on de la cadena en el tiempo. • Para todo n ∈ N y x ∈ E se tiene que 1 = P (Xn+1 ∈ E |Xn = x ) = P (∪y∈E {Xn+1 = y}|Xn = x ) X = P (Xn+1 = y|Xn = x ) . y∈E

12/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Algunas precisiones

• Si las probabilidades de ir de un estado a otro en una unidad de tiempo no depende del instante de tiempo en el cual se inicia, es decir si P (Xn+1 = y|Xn = x ) = Px ,y no depende de n, ∀x , y ∈ E , diremos que la cadena es homog´ enea con respecto al tiempo.

13/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Algunas precisiones

• Si las probabilidades de ir de un estado a otro en una unidad de tiempo no depende del instante de tiempo en el cual se inicia, es decir si P (Xn+1 = y|Xn = x ) = Px ,y no depende de n, ∀x , y ∈ E , diremos que la cadena es homog´enea con respecto al tiempo. • En este curso solo nos interesaremos por las cadenas de Markov homog´ eneas en el tiempo y en la mayor´ıa de los casos con espacio de estados E finito.

13/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Algunas precisiones

• Si las probabilidades de ir de un estado a otro en una unidad de tiempo no depende del instante de tiempo en el cual se inicia, es decir si P (Xn+1 = y|Xn = x ) = Px ,y no depende de n, ∀x , y ∈ E , diremos que la cadena es homog´enea con respecto al tiempo. • En este curso solo nos interesaremos por las cadenas de Markov homog´eneas en el tiempo y en la mayor´ıa de los casos con espacio de estados E finito. • La familia de probabilidades de transici´ on P = {Px ,y , (x , y) ∈ E × E }, ser´a llamada matriz de transici´ on de la cadena. P cumple que X X Px ,y = P (Xn+1 = y|Xn = x ) = 1, x ∈ E. y∈E

y∈E

Se dice que P , es una matriz estoc´ astica o de Markov. 13/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Algunas precisiones

• Si las probabilidades de ir de un estado a otro en una unidad de tiempo no depende del instante de tiempo en el cual se inicia, es decir si P (Xn+1 = y|Xn = x ) = Px ,y no depende de n, ∀x , y ∈ E , diremos que la cadena es homog´enea con respecto al tiempo. • En este curso solo nos interesaremos por las cadenas de Markov homog´eneas en el tiempo y en la mayor´ıa de los casos con espacio de estados E finito. • La familia de probabilidades de transici´ on P = {Px ,y , (x , y) ∈ E × E }, ser´a llamada matriz de transici´ on de la cadena. P cumple que X X Px ,y = P (Xn+1 = y|Xn = x ) = 1, x ∈ E. y∈E

y∈E

Se dice que P , es una matriz estoc´astica o de Markov. • Diremos que el proceso estoc´astico {Xn , n ∈ N} es una cadena de Markov (π, P), donde π es la distribuci´ on de X0 y P es la matriz de probabilidades de transici´ on.

13/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

El sistema Bonus-Malus en el seguro de autom´ oviles En Hong Kong y en otros lugares del mundo, se usa un sistema para fijar las primas de seguro de autom´ ovil conocido como Bonus-Malus que consiste de 6 clases de tarificaci´ on, de 1 fort bonus a 6 fort malus, que se rige por las siguientes reglas: si un asegurado no tuvo siniestros durante el periodo, entonces pasa de la categor´ıa i a la categor´ıa max{1, i − 1}, si el asegurado tiene al menos un siniestro entonces pasa de la categor´ıa i a la 6. Si Xn denota la categor´ıa en cual se encuentra un individuo al n-´esimo periodo entonces {Xn , n ≥ 0} es una cadena de Markov con espacio de estados {1, 2, . . . , 6}. Un asegurado tiene un siniestro con probabilidad 1 − p en un periodo.

14/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

La matriz de transici´ on asociada  p 0  p 0   0 p P=  0 0   0 0 0 0

est´a dada por 0 0 0 p 0 0

0 0 0 0 p 0

0 0 0 0 0 p

1−p 1−p 1−p 1−p 1−p 1−p

    .   

15/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

La matriz de transici´ on asociada  p 0  p 0   0 p P=  0 0   0 0 0 0

est´a dada por 0 0 0 p 0 0

0 0 0 0 p 0

0 0 0 0 0 p

1−p 1−p 1−p 1−p 1−p 1−p

    .   

¿Cu´ al es la proporci´ on de tiempo que un cliente pasa en el estado j despu´ es de n pasos, n −1 Nnj , dado que X0 = j ?

15/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

La matriz de transici´ on asociada  p 0  p 0   0 p P=  0 0   0 0 0 0

est´a dada por 0 0 0 p 0 0

0 0 0 0 p 0

0 0 0 0 0 p

1−p 1−p 1−p 1−p 1−p 1−p

    .   

¿Cu´al es la proporci´ on de tiempo que un cliente pasa en el estado j despu´es de n pasos, n −1 Nnj , dado que X0 = j ? ¿Cu´ al es la prima promedio que paga un asegurado?

15/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

La matriz de transici´ on asociada  p 0  p 0   0 p P=  0 0   0 0 0 0

est´a dada por 0 0 0 p 0 0

0 0 0 0 p 0

0 0 0 0 0 p

1−p 1−p 1−p 1−p 1−p 1−p

    .   

¿Cu´al es la proporci´ on de tiempo que un cliente pasa en el estado j despu´es de n pasos, n −1 Nnj , dado que X0 = j ? ¿Cu´al es la prima promedio que paga un asegurado? Sea c una funci´on que determina la prima a pagar en funci´ on de la categor´ıa. c es una funci´ on definida en {1, 2, . . . , 6} no-decreciente que toma solo valores positivos. La prima promedio que pagar´a un individuo en n periodos ser´a entonces: (n) n 6 X Nj 1X c(Xj ), = c(j ) n j =1 n j =1 15/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Ejemplo (Merenguero) En este ejemplo, M la fortuna del merenguero, N nuestra fortuna, p la probabilidad de ´aguila, y de que el merenguero gane un peso, y Sn =la fortuna del merenguero despu´es de n volados, n ≥ 0. {Sn , n ≥ 0} es una cadena de Markov con matriz de transici´ on

16/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Ejemplo (Merenguero) En este ejemplo, M la fortuna del merenguero, N nuestra fortuna, p la probabilidad de ´aguila, y de que el merenguero gane un peso, y Sn =la fortuna del merenguero despu´es de n volados, n ≥ 0. {Sn , n ≥ 0} es una cadena de Markov con matriz de transici´ on   si i , j = 0 1,    p si 0 < i < N + M , j = i + 1  P(Sn+1 = j |Sn = i ) = Pi,j = 1 − p si 0 < i < N + M , j = i − 1    1 si i , j = N + M    0 en otro caso y ley inicial P(S0 = M ) = 1.

16/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Ejemplo (Merenguero) En este ejemplo, M la fortuna del merenguero, N nuestra fortuna, p la probabilidad de ´aguila, y de que el merenguero gane un peso, y Sn =la fortuna del merenguero despu´es de n volados, n ≥ 0. {Sn , n ≥ 0} es una cadena de Markov con matriz de transici´ on   si i , j = 0 1,    p si 0 < i < N + M , j = i + 1  P(Sn+1 = j |Sn = i ) = Pi,j = 1 − p si 0 < i < N + M , j = i − 1    1 si i , j = N + M    0 en otro caso ando retirarse del juego? ¿Cu´ al es la y ley inicial P(S0 = M ) = 1. ¿Cu´ probabilidad de que el merenguero pierda todo su cap´ıtal?¿Cu´ al es el tiempo promedio que durar´ a el juego? 16/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Lema Sea {Sn , n ≥ 0} una caminata aleatoria simple en {0, 1, . . . , N }, con barreras absorbentes en 0 y N ; Pi,i+1 = p y q = Pi,i−1 = 1 − p, 0 < i < N , P0,0 = 1 = PN ,N . Se tiene que  q j q N  ( p ) −( p ) , si p 6= q N 1−( pq ) P(Caminata absorbida en 0|S0 = j ) =  N −j si p = q = 1/2. N , Si T es el tiempo de absorci´ on en {0, N }, T = inf{n ≥ 0 : Sn ∈ {0, N }} entonces  q j  j − N 1−( p ) , si p 6= q q−p q−p 1−( q )N E (T |S0 = j ) = p  j (N − j ), si p = q = 1/2.

17/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Demostraci´ on: T´ ecnica del primer paso

h(j ) = P(Caminata absorbida en 0|S0 = j ) es soluci´on al sistema de ecuaciones lineales h(j ) = ph(j + 1) + qh(j − 1), 0 < j < N ,

h(0) = 1, h(N ) = 0.

L(j ) = E (T |S0 = j ) , es soluci´ on al sistema de ecuaciones lineales L(0) = 0 = L(N ),

L(j ) = 1 + pL(j + 1) + qL(j − 1),

0 < j < N.

18/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Caminatas aleatorias en Zd

S0 ∈ Zd , (Yi , i ≥ 1) v.a.i.i.d. toman en Zd , y son independientes de S0 . Al proceso estoc´astico (Sn , n ≥ 0) Sn+1 = Sn + Yn+1 ,

n ≥ 0,

se le llama caminata aleatoria.

19/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Caminatas aleatorias en Zd

S0 ∈ Zd , (Yi , i ≥ 1) v.a.i.i.d. toman en Zd , y son independientes de S0 . Al proceso estoc´astico (Sn , n ≥ 0) Sn+1 = Sn + Yn+1 ,

n ≥ 0,

se le llama caminata aleatoria. En Z2 se ve

19/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

En Z3 ,

20/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

En Z3 , mientras que en Londres se ve como

20/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Ejemplo (La cadena de Ehrenfest) T. Ehrenfest describi´ o un experimento con 2 urnas, A y B , dentro de las cuales est´an distribuidas N mol´eculas. En cada paso del experimento, se escoge al azar una y solo una mol´ecula, esta es removida de la urna en la cual se encuentra y es colocada en la otra urna. El proceso estoc´astico {Xn , n ∈ N} definido por Xn = #mol´eculas presentes en la urna A al instante n,

n ∈ N,

21/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Ejemplo (La cadena de Ehrenfest) T. Ehrenfest describi´ o un experimento con 2 urnas, A y B , dentro de las cuales est´an distribuidas N mol´eculas. En cada paso del experimento, se escoge al azar una y solo una mol´ecula, esta es removida de la urna en la cual se encuentra y es colocada en la otra urna. El proceso estoc´astico {Xn , n ∈ N} definido por Xn = #mol´eculas presentes en la urna A al instante n,

n ∈ N,

es una cadena de Markov y su espacio de estados {0, 1, 2, . . . , N }.

21/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Ejemplo (La cadena de Ehrenfest) T. Ehrenfest describi´ o un experimento con 2 urnas, A y B , dentro de las cuales est´an distribuidas N mol´eculas. En cada paso del experimento, se escoge al azar una y solo una mol´ecula, esta es removida de la urna en la cual se encuentra y es colocada en la otra urna. El proceso estoc´astico {Xn , n ∈ N} definido por Xn = #mol´eculas presentes en la urna A al instante n,

n ∈ N,

es una cadena de Markov y su espacio de estados {0, 1, 2, . . . , N }. ¿Cuales son las probabilidades de transici´ on?

21/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Ejemplos de matrices de transici´ on

Ejemplo (La cadena de Ehrenfest) T. Ehrenfest describi´ o un experimento con 2 urnas, A y B , dentro de las cuales est´an distribuidas N mol´eculas. En cada paso del experimento, se escoge al azar una y solo una mol´ecula, esta es removida de la urna en la cual se encuentra y es colocada en la otra urna. El proceso estoc´astico {Xn , n ∈ N} definido por Xn = #mol´eculas presentes en la urna A al instante n,

n ∈ N,

es una cadena de Markov y su espacio de estados {0, 1, 2, . . . , N }. ¿Cuales son las probabilidades de transici´ on? Se tiene que ( ( 1 si j = 1, 1 j = N − 1, P0,j = PN ,j = 0 en otro caso 0 en otro caso,

Pi,j =

 0,    i N

N −i     N 0

si|i − j | > 1, si j = i − 1, , si j = i + 1, si i = j .

para i ∈ {1, 2, . . . , N − 1}. 21/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Recurrencia aleatoria y simulaci´ on

Recurrencia aleatoria y simulaci´ on

Sean X0 es una variable aleatoria que toma valores en E , {Yn : Ω → S , n ∈ N}, una sucesi´ on de variables aleatorias independientes entre si y de X0 y F : E × S → E . En general, cualquier fenomeno descrito por una relaci´ on en recurrencia aleatoria de la forma Xn+1 = F (Xn , Yn+1 ),

n ∈ N,

es una cadena de Markov.

22/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Recurrencia aleatoria y simulaci´ on

Toda cadena de Markov con espacio de estados finito se puede simular usando esto. Sea {Xn , n ≥ 0} una cadena de Markov (π, P) y b0 ∼ X0 , E = {0, 1, . . . , M }. El proceso estoc´astico definido mediante X bn+1 = F (X bn , Yn+1 ), X para n ≥ 0,

.

23/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Recurrencia aleatoria y simulaci´ on

Toda cadena de Markov con espacio de estados finito se puede simular usando esto. Sea {Xn , n ≥ 0} una cadena de Markov (π, P) y b0 ∼ X0 , E = {0, 1, . . . , M }. El proceso estoc´astico definido mediante X bn+1 = F (X bn , Yn+1 ), X para n ≥ 0, con F : E × [0, 1] → E , definida como x ∈ E , z ∈ [0, 1], F (x , z ) = min{i ∈ E :

i X

Px ,j > z },

j =0

y Yi ∼ Uniforme[0, 1], tiene la misma distribuci´ on que X = (Xn , n ≥ 0).

23/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Nociones b´ asicas de cadenas de Markov Recurrencia aleatoria y simulaci´ on

Toda cadena de Markov con espacio de estados finito se puede simular usando esto. Sea {Xn , n ≥ 0} una cadena de Markov (π, P) y b0 ∼ X0 , E = {0, 1, . . . , M }. El proceso estoc´astico definido mediante X bn+1 = F (X bn , Yn+1 ), X para n ≥ 0, con F : E × [0, 1] → E , definida como x ∈ E , z ∈ [0, 1], F (x , z ) = min{i ∈ E :

i X

Px ,j > z },

j =0

y Yi ∼ Uniforme[0, 1], tiene la misma distribuci´ on que b est´an dadas por on de X X = (Xn , n ≥ 0). Las probabilidades de transici´ bn+1 = l |X bn = x ) = P (F (x , Yn+1 ) = l ) P(X =P

l−1 X j =0

Px ,j ≤ Yn+1
0, (ii) Px ,x1 Px1 ,x2 · Pxn−2 ,xn−1 Pxn−1 ,y > 0, para algunos x1 , . . . , xn−1 ∈ E ; o dicho de otro modo, con probabilidad positiva existe una trayectoria que lleva de x a y. (iii) P(Xn = y para alg´ un n ≥ 1|X0 = x ) > 0.

39/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Recurrencia y Transitoriedad

Definici´ on Para x ∈ E , definimos Tx = inf{n ≥ 1 : Xn = x }, el primer tiempo de entrada a x . Diremos que un estado x ∈ E es recurrente si P(Tx < ∞|X0 = x ) = P(Xn = x para alg´ un n ≥ 1|X0 = x ) = 1. Diremos que un estado x ∈ E es transitorio si P(Tx < ∞|X0 = x ) = P(Xn = x para alg´ un n ≥ 1|X0 = x ) < 1.

40/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Recurrencia y Transitoriedad

Proposici´ on Si x es recurrente P(Xn = x para una infinidad de n’s |X0 = x ) = 1 Si x es transitorio P(Xn = x para una infinidad de n’s |X0 = x ) = 0. Sean ρx = P(Tx < ∞|X0 = x ) y Nx la variable aleatoria que cuenta el numero total de visitas al estado x . Se tiene que Nx sigue una ley geom´etrica, es decir que k −1

P(Nx = k |X0 = x ) = (ρx )

(1 − ρx ),

k ≥ 1.

41/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Ley fuerte

Sea Nny el n´ umero de visitas al estado y en n pasos. Teorema (Ley fuerte) Para y ∈ E estado transitorio Nny < ∞ con probabilidad 1.

42/ 55

Introducci´ on a las cadenas de Markov: I Tiempo discreto Ley fuerte

Sea Nny el n´ umero de visitas al estado y en n pasos. Teorema (Ley fuerte) Para y ∈ E estado transitorio Nny < ∞ con probabilidad 1. Para y ∈ E estado recurrente, lim

n→∞

1{Ty