Universidad Bicentenaria de Aragua
Cátedra: Investigación de Operaciones II
Escuela de Ingeniería en Sistemas
Cadenas de Markov
Una cadena de Markov es una sucesión de ensayos
similares u observaciones en la cual cada ensayo tiene el mismo número finito
de resultados posibles y en donde la probabilidad de cada resultado para un
ensayo dado depende sólo del resultado del ensayo inmediatamente precedente y
no de cualquier resultado previo
Propiedad de Markov
Dada una secuencia de variables aleatorias X1,
X2 ,X3, tales que el valor de xn es
el estado del proceso en el tiempo n.
Si la distribución de probabilidad condicional de Xn+1 en
estados pasados es una función de Xn por
sí sola, entonces:
P
( X+1= xn+1 /Xn= xn
, Xn-1= xn-1 ,....X2= x2 , X1= x1)=
P
(Xn+= xn+1 /Xn= xn
)
Donde xi es el estado del proceso en el instante
i.
Esta identidad es la denominada propiedad de Markov:
El estado en t + 1 sólo depende del estado en t
y no de la evolución anterior del sistema.
Matriz
de transición
Al trabajar con cadenas de Markov, a menudo es útil pensar la sucesión de ensayos como experimentos
efectuados en cierto sistema físico, cada resultado dejando a este sistema en
cierto estado.
Por ejemplo, consideremos una sucesión de elecciones políticas en
cierto país: el sistema podría tomarse como el país mismo y cada elección lo
dejaría en cierto estado, es decir en el control del partido ganador. Si sólo
hay dos partidos políticos fuertes, llamados A y B, los que por lo regular
controlan el gobierno, entonces podemos decir que el país se encuentra en el
estado A o B si el partido A o B ganara la elección. Cada ensayo (o sea cada
elección), coloca al país en uno de los dos estados A o B. Una sucesión de 10 elecciones podría producir
resultados tales como los siguientes:
A, B, A, A, B, B, B, A, B, B
La primera elección en la sucesión
deja en el poder al partido A, la segunda fue ganada por el partido B, y así
sucesivamente, hasta que la décima elección la gane el partido B. Supongamos
que las probabilidades de que el partido A o B ganen la próxima elección son
determinadas por completo por el partido que está en el poder ahora. Por
ejemplo podríamos tener las probabilidades siguientes:
• Si el partido A está en el poder,
existe una probabilidad de ¼ que el partido A ganará la próxima elección y una
probabilidad de ¾ de que el partido B gane la elección siguiente.
• Si el partido B está en el poder, hay
una probabilidad de 1/3 de que el partido A gane la elección siguiente y una
probabilidad de 2/3 que el partido B permanezca en el poder.
Definición: Consideremos un proceso de Markov en que el sistema posee n estados
posibles, dados por los números 1, 2, 3, …., n. Denotemos pij a
la probabilidad de que el sistema pase al estado j después de cualquier ensayo
en donde su estado era i antes del ensayo. Los números pij se denominan probabilidades de transición y la matriz nxn P =
(pij ) se conoce como matriz
de transición del sistema.
Observaciones:
1)
La suma pi1+pi2+......+pin=1 Esta suma
representa la probabilidad de que el sistema pase a uno de los estados 1, 2,
…., n dado que empieza en el estado i. Ya que el sistema ha de estar en uno de
estos n estados, la suma de probabilidades debe ser igual a 1. Esto significa
que los elementos en cualquier renglón de la matriz de transición deben sumar
1.
2)
Cada elemento pij>
o igual a 0.
Procesos
Estocásticos
Se
define entonces una familia de variables aleatorias que dependen de una
variable determinista, (en este caso el tiempo). Se
define el proceso estocástico X(t) como el número de llamadas que
se producen en la centralita en el tiempo (0,t). Así, para cada valor de t que
se elija, tendremos una variable aleatoria distinta, con forma similar pero
distinto valor. En los temas anteriores definimos X(x), en este caso X(λ). Ahora
debemos x t) este caso λ t) representar
X(x,t), en este caso, X(λ,t). En general, diremos X(t) igual que antes
llamábamos X y no X(λ).
Proceso
Estocástico
Es una función de dos variables, t y x, una determinista y otra
aleatoria
a) X(x,t) es una familia de funciones temporales.
b) Si se fija x, tenemos una función temporal X(t) llamada realización
del proceso.
c) Si se fija t, tenemos una Variable Aleatoria.
d) Si se fijan t y x, tenemos un número real o complejo (muy
normal en teoría de la señal).
Los
procesos estocásticos pueden ser clasificados en:
-
Tiempo discreto: Cuando el valor de la variable sólo puede cambiar en una serie de momentos determinados del tiempo
(por ejemplo, los sorteos de la lotería tienen lugar en determinadas fechas).
-
Tiempo continuo: Cuando el valor de la variable puede cambiar en cualquier
momento del tiempo (la temperatura, por ejemplo).
Otra forma de clasificar a los procesos
estocásticos es:
-
Variable continua: La variable puede tomar cualquier valor comprendido en un
rango (la temperatura, por ejemplo)
-
Variable discreta: La variable sólo puede tomar determinados valores o estados
discretos.
Características
de un proceso estocástico
Del mismo modo que en una
variable unidimensional X, podemos calcular su media, su varianza y otras
características, y en variables n-dimensionales obtenemos un vector de medias,
matriz de covarianzas, etc., en un proceso estocástico podemos obtener algunas
características que describen su comportamiento: medias, varianzas y
covarianzas. Puesto que las características del proceso pueden variar a lo
largo de t estas características no serán parámetros sino que serán funciones
de t.
Media : Llamaremos función
de medias del proceso a una función de t que proporciona las medias de las
distribuciones marginales para cada instante t.
E [ x(t) ] = µt
Varianza : Llamaremos
función de varianzas del proceso a una función de t que proporciona las
varianzas de las distribuciones marginales para cada instante t.
Var [ x(t) ] = σ2(t) = E [ (x(t) - µt)2 ]
Autovarianzas : Llamaremos
función de autocovarianzas del proceso a la función que proporciona la
covarianza existente entre dos instante de tiempo cuales quiera.
Cov(t1, t2)=E[(x(t1)-µt1)(x(t2)-µt2)]
Autorrelacion : Llamaremos función
de autocorrelación a la estandarización de la función de
Covarianzas.
ρ(t1, t2)
= Cov (t1, t2) / σ(t1) σ(t2)
Matriz ergodica
Una cadena de markov es ergodica (se conoce cm una cadena
markov a un tipo especial de proceso estocástico discreto en el que la
probabilidad de que ocurra un evento depende del evento inmediatamente
anterior. En efecto, las cadenas de este tipo tienen memoria). Si todos sus
estados son no nulos, no periódicos y recurrentes.
Estado de absorción
Un estado absorbente en un sistema de markov es un estado a
partir de la cual existe cero probabilidades de salir. Un sistema absorbente de
markov es un sistema de markov que contiene al menos un estado absorbente, tal
que es posible llegar a un estado absorbente
después de algún numero de etapas comenzando en cualquier estado no
absorbente.
En el análisis de los sistemas absorbentes, enumeramos los
estados en tal manera que los estados absorbentes son los últimos.
Aquí I esta la matriz unidad m×m(m=numero de estados
absorbentes), S es una matriz cuadrada (n-m)×(n-m) (n=número total de estados,
de modo n-m=el numero de estados absorbentes), 0 es una matriz ceros y T es una
matriz (n-m)×m.
La matriz S es la matriz de transacción para la circulación
entre los estados de absorción.
Bachilleres:
Martinez Elys
Mata Crisbel
Ruiz Solmaira
Escuela de Ingeniería en Sistemas
