Matriz de estados de transición de una cadena de Markov. cadenas de markov

1. matriz P2 transición del circuito del estado i en un estado j en dos
paso;

2. distribución de probabilidad entre estados en este momento t=2;

3. la probabilidad de que en este momento t=1 estado del circuito será A2;

4. distribución estacionaria.

Solución. Para una cadena de Markov discreta en el caso de su homogeneidad, se cumple la siguiente relación:

donde P1 es la matriz de probabilidades de transición en un paso;
Рn - matriz de probabilidades de transición para n pasos;

1. Encuentre la matriz de transición P2 en dos pasos

Sea la distribución de probabilidad sobre los estados en S el ésimo paso está determinado por el vector
.
Conociendo la matriz pn transición en n pasos, podemos determinar la distribución de probabilidad entre estados en (S+norte)-ésimo paso . (5)

2. Encontremos la distribución de probabilidad sobre los estados del sistema en este momento. t=2. Pongamos (5) S=0 y norte=2. Entonces .

Lo conseguiremos.

3. Encontremos la distribución de probabilidad sobre los estados del sistema en este momento. t=1.

Pongamos (5) s=0 y norte=1, entonces.
¿Cómo podemos ver que la probabilidad de que en este momento t=1 estado del circuito será A2,igual p2(1)=0,69.
La distribución de probabilidad entre estados se llama estacionaria si no cambia de un paso a otro, es decir
Entonces de la relación (5) en norte=1 obtenemos

4. Encontremos la distribución estacionaria. Como =2 tenemos =(р1; р2). escribamos el sistema ecuaciones lineales(6) en forma coordinada

La última condición se llama normalización. En el sistema (6) una ecuación es siempre una combinación lineal de otras. Por tanto, se puede tachar. Resolvamos juntas la primera ecuación del sistema y la ecuación de normalización. tenemos 0.6 p1=0,3p2, eso es p2=2p1. Entonces p1+2p1=1 o , es decir . Por eso, .
Respuesta:
1) la matriz de transición en dos pasos para una cadena de Markov dada tiene la forma ;
2) distribución de probabilidad sobre los estados en este momento t=2 es igual ;
3) la probabilidad de que en este momento t=1 estado del circuito será A2, es igual p2(t)=0,69;
4) la distribución estacionaria tiene la forma

Matriz dada intensidades de transición de una cadena de Markov continua. Cree un gráfico de estado etiquetado correspondiente a la matriz Λ; crear un sistema ecuaciones diferenciales Kolmogorov para probabilidades estatales; Encuentre la distribución de probabilidad límite. Solución. Cadena de Markov homogénea con un número finito de estados. A1, A2,…A caracterizado por la matriz de intensidades de transición ,

Dónde - intensidad de la transición de la cadena de Markov desde el estado Аi en un estado Aj; ðij(Δt)-probabilidad de transición Ay→aj por intervalo de tiempo Δ t.

Las transiciones del sistema de un estado a otro se especifican convenientemente mediante un gráfico de estado etiquetado, en el que están marcados los arcos correspondientes a las intensidades. λ yo>0. Creemos un gráfico de estado etiquetado para una matriz de intensidad de transición dada

Sea un vector de probabilidades. Rj(t),
j=1, 2,…,, el sistema está en el estado Aj en el momento t.

Obviamente 0≤ Rj(t)≤1 y . Luego, de acuerdo con la regla para derivar una función vectorial de un argumento escalar, obtenemos . Probabilidades Rj(t) satisfacer el sistema de ecuaciones diferenciales de Kolmogorov (SDEK), que en forma matricial parece . (7)

Si en el momento inicial el sistema estaba en el estado Aj, entonces el SDUK debería resolverse en las condiciones iniciales
Ri(0)=1, ðj(0)=0, j≠i,j=1, 2,…,. (8)
El conjunto de SDUK (7) y condiciones iniciales(8) describe de forma única una cadena de Markov homogénea con tiempo continuo y un número finito de estados.
Compongamos un SDEK para una cadena de Markov determinada. Como =3, entonces j=1, 2, 3.

De la relación (7) obtenemos

.
Desde aquí tendremos

La última condición se llama normalización.
La distribución de probabilidad entre estados se llama estacionario, si no cambia con el tiempo, es decir, donde Rj=constante, j=1,2,…,. De aquí .

Luego de SDUK (7) obtenemos un sistema para encontrar la distribución estacionaria.
(9)
Para este problema, desde el SDUK tendremos

De la condición de normalización obtenemos 3r2+r2+r2=1 o . Por tanto, la distribución límite tiene la forma .
Tenga en cuenta que este resultado se puede obtener directamente del gráfico de estado etiquetado si usamos la regla: para una distribución estacionaria, la suma de los productos λ JiPi, j≠i, para flechas que vienen de i-ésimo estado es igual a la suma de los productos λ JiPi, j≠i, para flechas incluidas en i-ésimo estado. En realidad,

Es obvio que el sistema resultante es equivalente al compilado usando SDUK. Por tanto tiene la misma solución.
Respuesta: la distribución estacionaria tiene la forma.

Definición. Una cadena de Markov se llama homogénea si la probabilidad condicional (transición de un estado a otro) no depende del número de pruebas. Por eso simplemente escriben.

Ejemplo 1. Caminata aleatoria. Sea una partícula material en línea recta en un punto con coordenadas enteras. En ciertos momentos la partícula experimenta choques. Bajo la influencia de un empujón, la partícula se mueve con probabilidad una unidad hacia la derecha y con probabilidad una unidad hacia la izquierda. Está claro que la posición (coordenada) de una partícula después de un choque depende de dónde estaba la partícula después del choque inmediatamente anterior y no depende de cómo se movió bajo la influencia de otros choques anteriores.

¿Entonces un paseo aleatorio? Un ejemplo de cadena de Markov homogénea de tiempo discreto.

La probabilidad de transición es la probabilidad condicional de que desde el estado (en el que se encontró el sistema como resultado de alguna prueba, sin importar el número) como resultado de la siguiente prueba el sistema pase a ese estado.

Así, en la notación, el primer índice indica el número del anterior, ¿y el segundo? número de estado posterior. Por ejemplo, la probabilidad de pasar del segundo estado al tercero.

Sea finito e igual el número de estados.

La matriz de transición de un sistema es una matriz que contiene todas las probabilidades de transición de este sistema:

Dado que cada fila de la matriz contiene las probabilidades de eventos (transición del mismo estado a cualquier estado posible), que forman grupo completo, entonces la suma de las probabilidades de estos eventos es igual a uno. En otras palabras, la suma de las probabilidades de transición de cada fila de la matriz de transición es igual a uno:

Pongamos un ejemplo de la matriz de transición de un sistema que puede estar en tres estados; la transición de un estado a otro se produce según el esquema de una cadena de Markov homogénea; Las probabilidades de transición están dadas por la matriz:

Aquí vemos que si el sistema estaba en un estado, luego de cambiar el estado en un paso permanecerá en el mismo estado con una probabilidad de 0,5, permanecerá en el mismo estado con una probabilidad de 0,5, entrará en un estado con una probabilidad de 0,2, luego de la transición, puede encontrarse en estados; no puede pasar de un estado a otro. Última línea La matriz nos muestra que de un estado para pasar a cualquiera de los estados posibles con la misma probabilidad de 0,1.

Con base en la matriz de transición del sistema, se puede construir el llamado gráfico de estado del sistema, también llamado gráfico de estado etiquetado. Esto es conveniente para una representación visual del circuito. Veamos el orden de construcción de gráficos usando un ejemplo.

Ejemplo 2. Usando la matriz de transición dada, construya un gráfico de estado.

Porque matriz cuarto orden, entonces, en consecuencia, el sistema tiene 4 estados posibles.

El gráfico no indica las probabilidades de que el sistema pase de un estado al mismo. Al revisar sistemas específicos Es conveniente construir primero un gráfico de estado, luego determinar la probabilidad de que el sistema pase de un estado al mismo (basado en el requisito de que la suma de los elementos de las filas de la matriz sea igual a uno) y luego construir una transición. matriz del sistema.

Este artículo es de carácter abstracto, escrito sobre la base de los que figuran en fin de las fuentes, que se citan en lugares.

Introducción a la teoría de las cadenas de Markov.

Una cadena de Markov es una secuencia de este tipo. eventos aleatorios, en el que la probabilidad de cada evento depende sólo del estado en el que se encuentra el proceso este momento y es independiente de estados anteriores. El circuito discreto final está determinado por:

1. conjunto de estados S = (s 1,…, s n), el evento es una transición de un estado a otro como resultado de una prueba aleatoria
2. vector probabilidades iniciales(distribución inicial) p (0) = ( p (0) (1),…, p (0) (n)), determinando la probabilidad p (0) (i) de que en el tiempo inicial t = 0 el proceso fuera en estado s i
3. matriz de probabilidades de transición P = ( p i j), que caracteriza la probabilidad de transición del proceso con estado actual s i al siguiente estado s j , mientras que la suma de las probabilidades de transiciones de un estado es igual a 1:

∑ j =1… norte p yo j = 1

Un ejemplo de una matriz de probabilidad de transición con un conjunto de estados S = (S 1, ..., S 5), un vector de probabilidades iniciales p (0) = (1, 0, 0, 0, 0):

Usando el vector de probabilidades iniciales y la matriz de transición, podemos calcular el vector estocástico p (n), un vector compuesto por las probabilidades p (n) (i) de que el proceso estará en el estado i en el momento n. Puedes obtener p(n) usando la fórmula:

P(n) = p(0)×Pn

Los vectores p (n) a medida que n crece, en algunos casos, se estabilizan: convergen a un cierto vector de probabilidad ρ, que puede denominarse distribución estacionaria de la cadena. La estacionariedad se manifiesta en el hecho de que tomando p (0) = ρ, obtenemos p (n) = ρ para cualquier n.
El criterio más simple, que garantiza la convergencia a una distribución estacionaria, se ve así: si todos los elementos de la matriz de probabilidades de transición P son positivos, entonces cuando n tiende al infinito, el vector p (n) tiende al vector ρ, que es la única solución. al sistema de la forma
pag × P = pag.
También se puede demostrar que si, para algunos valor positivo n todos los elementos de la matriz P n son positivos, entonces el vector p (n) aún se estabilizará.
La prueba de estas declaraciones se proporciona en detalle.

Una cadena de Markov se representa como un gráfico de transición, cuyos vértices corresponden a los estados de la cadena y los arcos corresponden a transiciones entre ellos. El peso del arco (i, j) que conecta los vértices s i y s j será igual a la probabilidad p i (j) transición del primer estado al segundo. Gráfico correspondiente a la matriz mostrada arriba:

Clasificación de estados de cadenas de Markov.

Al considerar las cadenas de Markov, puede que nos interese el comportamiento del sistema durante un corto período de tiempo. En este caso, las probabilidades absolutas se calculan utilizando las fórmulas del apartado anterior. Sin embargo, es más importante estudiar el comportamiento del sistema en intervalo grande momento en el que el número de transiciones tiende a infinito. A continuación se introducen definiciones de los estados de las cadenas de Markov, que son necesarias para estudiar el comportamiento del sistema a largo plazo.
Las cadenas de Markov se clasifican según la posibilidad de transición de un estado a otro.
Los grupos de estados de una cadena de Markov (subconjuntos de vértices del gráfico de transición), que corresponden a los vértices sin salida del diagrama de orden del gráfico de transición, se denominan clases ergódicas de la cadena. Si consideramos el gráfico mostrado arriba, podemos ver que contiene 1 clase ergódica M 1 = ( S 5 ), alcanzable desde un componente fuertemente conectado correspondiente a un subconjunto de vértices M 2 = ( S 1 , S 2 , S 3 , S 4 ). Los estados que están en clases ergódicas se llaman esenciales, y el resto se llaman no esenciales (aunque tales nombres no encajan bien con sentido común). El estado absorbente s i es un caso especial de la clase ergódica. Luego, una vez en ese estado, el proceso se detendrá. Para S i, p ii = 1 será verdadero, es decir en el gráfico de transición, solo emanará un borde: un bucle.

Absorbente cadenas de markov se utilizan como modelos temporales de programas y procesos computacionales. Al modelar un programa, los estados del circuito se identifican con los bloques del programa, y ​​la matriz de probabilidades de transición determina el orden de las transiciones entre bloques, dependiendo de la estructura del programa y la distribución de datos iniciales, los valores. ​de los cuales influyen en el desarrollo del proceso computacional. Como resultado de representar el programa mediante el circuito absorbente, es posible calcular el número de accesos a los bloques del programa y el tiempo de ejecución del programa, estimado valores promedio, variaciones y, en su caso, distribuciones. Utilizando estas estadísticas en el futuro, podrá optimizar el código del programa: utilice métodos de bajo nivel para acelerar partes críticas del programa. Este método se llama creación de perfiles de código.

Por ejemplo, en el algoritmo de Dijkstra están presentes los siguientes estados del circuito:

• vértice (v), elimine un nuevo vértice de la cola de prioridad, vaya únicamente al estado b;
• comenzar (b), el comienzo del ciclo de búsqueda de arcos salientes para el procedimiento de debilitamiento;
• análisis (a), análisis del siguiente arco, posible transición a a, d o e;
• disminuir (d), disminuyendo la estimación para algún vértice del gráfico, moviéndose a a;
• final (e), finalización del bucle, pasando al siguiente vértice.

Queda por establecer las probabilidades de transición entre vértices, y se puede estudiar la duración de las transiciones entre vértices, las probabilidades de entrar en varios estados y otras características medias del proceso.

De manera similar, el proceso computacional, que se reduce a acceder a los recursos del sistema en el orden determinado por el programa, puede representarse mediante una cadena absorbente de Markov, cuyos estados corresponden al uso de los recursos del sistema: procesador, memoria y transición de dispositivos periféricos; Las probabilidades reflejan el orden de acceso a diversos recursos. Gracias a esto, el proceso computacional se presenta de una forma conveniente para analizar sus características.

Una cadena de Markov se llama irreducible si cualquier estado S j puede alcanzarse desde cualquier otro estado Si en un número finito de transiciones. En este caso, se dice que todos los estados del circuito se están comunicando y el gráfico de transición es un componente de una conectividad fuerte. Un proceso generado por una cadena ergódica, que comienza en un determinado estado, nunca termina, sino que pasa secuencialmente de un estado a otro, terminando en diferentes estados con diferentes frecuencias dependiendo de las probabilidades de transición. Por tanto, la principal característica de una cadena ergódica es
la probabilidad de que el proceso esté en estados S j , j = 1,…, n, la proporción de tiempo que el proceso pasa en cada uno de los estados. Los circuitos irreducibles se utilizan como modelos de confiabilidad del sistema. De hecho, si un recurso que utiliza un proceso falla con mucha frecuencia, la funcionalidad de todo el sistema estará en riesgo. En este caso, duplicar un recurso tan crítico puede ayudar a evitar fallas. En este caso, los estados del sistema, que difieren en la composición de equipos reparables y fallidos, se interpretan como estados del circuito, cuyas transiciones están asociadas con fallas y restauración de dispositivos y cambios en las conexiones entre ellos, realizados para mantener la operatividad del sistema. Las estimaciones de las características de un circuito irreductible dan una idea de la fiabilidad del comportamiento del sistema en su conjunto. Además, dichos circuitos pueden ser modelos de interacción entre dispositivos y tareas enviadas para su procesamiento.

Ejemplos de uso

Sistema de servicio de fallas

Un servidor consta de varios bloques, como módems o tarjetas de red, que reciben solicitudes de servicio de los usuarios. Si todos los bloques están ocupados, la solicitud se pierde. Si uno de los bloques acepta una solicitud, queda ocupado hasta el final de su procesamiento. Tomemos como estados el número de bloques desocupados. El tiempo será discreto. Denotemos por α la probabilidad de recibir una solicitud. También creemos que el tiempo de servicio también es aleatorio y consta de continuaciones independientes, es decir una solicitud con probabilidad β se atiende en un paso, y con probabilidad (1 - β) se atiende después de este paso como una nueva solicitud. Esto da una probabilidad de (1 - β) β para un servicio de dos pasos, (1 - β) 2 β para un servicio de tres pasos, etc. Consideremos un ejemplo con 4 dispositivos funcionando en paralelo. Creemos una matriz de probabilidades de transición para los estados seleccionados:

Se puede observar que tiene una clase ergódica única y, por lo tanto, el sistema p × P = p en la clase de vectores de probabilidad tiene única decisión. Anotamos las ecuaciones del sistema que nos permite encontrar esta solución:

P 0 (1 - α) + p 1 β = p 0 ,
p 0 α + p 1 (1 - α - β) + p 2 2 β = p 1,
p 1 α + p 2 (1 - α - 2 β) + p 3 3 β = p 2,
p 2 α + p 3 (1 - α - 3 β) + p 4 4 β = p 3,
p 3 α + p 4 (1 - 4 β) = p 4 .

De esto obtenemos (con γ = α/β):

PAG 1 = γ pag 0 ,
p 2 = γ 2 p 0 /2,
p 3 = γ 3 p 0 /3,
p 4 = γ 4 p 0 /4,

De la condición de normalización se deduce:

P 0 = C = (1 + γ + γ 2/2 + γ 3/3 + γ 4/4) -1.

Ahora se conoce el conjunto de probabilidades π i de que en el modo estacionario el sistema tendrá i bloques ocupados. Luego, una fracción del tiempo p 4 = C γ 4 /4 todos los bloques del sistema están ocupados, el sistema no responde a las solicitudes. Los resultados obtenidos se aplican a cualquier número de bloques. Ahora puedes aprovecharlos: puedes comparar los costos de dispositivos adicionales y la reducción en el tiempo que el sistema está completamente ocupado.
Puedes leer más sobre este ejemplo en .

Procesos de toma de decisiones con un número finito e infinito de etapas.

Considere un proceso en el que existen varias matrices de probabilidad de transición. Para cada momento del tiempo, la elección de una u otra matriz depende de la decisión que tomemos. Lo anterior se puede entender usando el siguiente ejemplo. Como resultado del análisis del suelo, el jardinero evalúa su condición con uno de tres números: (1) - bueno, (2) - satisfactorio o (3) - pobre. Al mismo tiempo, el jardinero notó que la productividad del suelo en el año en curso depende únicamente de su condición en el año anterior. Por lo tanto, la probabilidad de transición del suelo sin Influencias externas de un estado a otro se puede representar mediante la siguiente cadena de Markov con matriz P1:

Ahora podemos asociar cada transición de un estado a otro con una determinada función de ingreso, que se define como ganancia o pérdida durante un período de un año. El jardinero puede optar por utilizar o no fertilizantes, esto determinará su ingreso o pérdida final. Introduzcamos las matrices R1 y R2, que determinan las funciones de ingreso en función del costo de los fertilizantes y la calidad del suelo:

Finalmente, el jardinero se enfrenta al problema de qué estrategia elegir para maximizar el rendimiento medio esperado. Se pueden considerar dos tipos de problemas: finitos y número infinito etapas. EN en este caso Algún día el trabajo de jardinero definitivamente terminará. Además, los visualizadores resuelven el problema de la toma de decisiones para Número finito etapas. Supongamos que el jardinero tiene la intención de dejar su ocupación después de N años. Nuestra tarea ahora es determinar la estrategia de comportamiento óptima para el jardinero, es decir, la estrategia que maximizará sus ingresos. La finitud del número de etapas de nuestro problema se manifiesta en el hecho de que al jardinero no le importa lo que sucederá con su tierra agrícola en N + 1 año (todos los años hasta N inclusive son importantes para él). Ahora podemos ver que en este caso el problema de búsqueda de estrategias se convierte en un problema de programación dinámica. Si denotamos por f n (i) el ingreso promedio máximo esperado que se puede recibir para las etapas de n a N inclusive, comenzando desde el estado número i, entonces es fácil derivar una relación de recurrencia que conecta f n (i) con los números f n + 1 (j)

F n (i) = max k (∑ j =1 m p ij k [ r ij k + f n +1 (j)]), n = 1, 2, …, N

Aquí k es el número de la estrategia utilizada. Esta ecuación se basa en el hecho de que el ingreso total r ij k + f n +1 (j) se obtiene como resultado de la transición del estado i en la etapa n al estado j en la etapa n +1 con probabilidad p ij k.
Ahora la solución óptima se puede encontrar calculando secuencialmente f n (i) en la dirección descendente (n = N ...1). Al mismo tiempo, introducir un vector de probabilidades iniciales en el planteamiento del problema no complicará su solución.
este ejemplo también discutido en .

Modelar combinaciones de palabras en texto.

Considere un texto que consta de las palabras w. Imaginemos un proceso en el que los estados son palabras, de modo que cuando está en el estado (S i) el sistema pasa al estado (s j) según la matriz de probabilidades de transición. En primer lugar, es necesario “entrenar” el sistema: proporcionar un texto suficientemente extenso como entrada para evaluar las probabilidades de transición. Y luego puedes construir trayectorias de la cadena de Markov. Aumentar la carga semántica de un texto construido utilizando el algoritmo de la cadena de Markov solo es posible aumentando el orden, donde el estado no es una palabra, sino conjuntos con mayor potencia: pares (u, v), triples (u, v, w) , etc. Además, en las cadenas de primer y quinto orden todavía tendrá poco sentido. El significado comenzará a surgir a medida que la dimensión del orden aumente al menos al número promedio de palabras en una frase típica. texto de origen. Pero es imposible avanzar de esta manera, porque el crecimiento de la carga semántica del texto en las cadenas de Markov de alto orden ocurre mucho más lentamente que la disminución de la unicidad del texto. Y un texto construido sobre cadenas de Markov, por ejemplo, de orden trigésimo, todavía no será tan significativo como para interesar a una persona, pero ya será bastante similar a texto original Además, la cantidad de estados en dicho circuito será asombrosa.
Esta tecnología ahora se usa mucho (desafortunadamente) en Internet para crear contenido de páginas web. Personas que desean aumentar el tráfico a su sitio web y mejorar su clasificación. los motores de búsqueda, esfuércese por poner tanto como sea posible en sus páginas. palabras clave Para buscar. Pero los motores de búsqueda utilizan algoritmos que pueden distinguir el texto real de una mezcla incoherente de palabras clave. Luego, para engañar a los motores de búsqueda, utilizan textos creados por un generador basado en una cadena de Markov. Hay, por supuesto, ejemplos positivos el uso de cadenas de Markov para trabajar con texto; se utilizan para determinar la autoría y analizar la autenticidad de los textos.

Cadenas de Markov y loterías

En algunos casos modelo probabilístico Se utiliza para predecir números en varias loterías. Aparentemente, no tiene sentido utilizar cadenas de Markov para modelar la secuencia de diferentes circulaciones. Lo sucedido con las bolas en el sorteo no afectará de ninguna manera los resultados del siguiente sorteo, ya que después del sorteo se recogen las bolas, y en el siguiente sorteo se colocan en la bandeja de lotería en orden fija. En este caso se pierde la conexión con la circulación pasada. Otra cosa es la secuencia de bolas que caen en un sorteo. En este caso, la caída de la siguiente bola está determinada por el estado de la máquina de lotería en el momento de la caída de la bola anterior. Por tanto, la secuencia de bolas caídas en un sorteo es una cadena de Markov, y se puede utilizar ese modelo. Aquí surge una gran dificultad a la hora de analizar las loterías numéricas. El estado de la máquina de lotería después de que caiga la siguiente bola determina los acontecimientos posteriores, pero el problema es que este estado nos es desconocido. Lo único que sabemos es que cierta pelota se cayó. Pero cuando se deja caer esta bola, las bolas restantes se pueden organizar de diferentes maneras, de modo que quede un grupo de bolas muy gran número estados correspondientes al mismo evento observado. Por lo tanto, sólo podemos construir una matriz de probabilidades de transición entre tales grupos de estados. Estas probabilidades son el promedio de las probabilidades de transiciones entre diferentes estados separados, lo que por supuesto reduce la eficiencia de aplicar el modelo de cadena de Markov a las loterías numéricas.
Similar a este caso, tal modelo red neuronal se puede utilizar para pronósticos meteorológicos, cotizaciones de divisas y en conexión con otros sistemas donde hay datos históricos disponibles y la información recién recibida se puede utilizar en el futuro. Buen uso en este caso, cuando sólo se conocen las manifestaciones del sistema, pero no los estados internos (ocultos), se pueden aplicar modelos ocultos de Markov, que se analizan en detalle en Wikilibros (modelos ocultos de Markov).

Literatura

1. Romanovsky I.V. Análisis discreto: un libro de texto para estudiantes, 3ª ed. - San Petersburgo: dialecto Nevsky; BHV Petersburgo, 2003.
2. Taha, Hamdy A. Introducción a la investigación de operaciones, 6ª ed. - M.: Editorial Williams, 2001.
3. Werner M. Conceptos básicos de codificación. Libro de texto para universidades. - M.: Tekhnosfera, 2004.
4. Belyaev A., Gavrilov M., Masalskikh A., Medvinsky M. Procesos de Markov, 2004.

Visualizadores

1. Procesos de toma de decisiones de Alekseev V. Markov, 2002.
2. Cadenas Belyaev A. Markov, 2002.

Métodos descripciones matemáticas markoviano procesos aleatorios en un sistema con estados discretos (DS) dependen de en qué momentos del tiempo (previamente conocidos o aleatorios) pueden ocurrir las transiciones del sistema de un estado a otro.
Si la transición de un sistema de un estado a otro es posible en momentos predeterminados, estamos ante Proceso aleatorio de Markov con tiempo discreto. Si la transición es posible en cualquier momento aleatorio tiempo, entonces estamos tratando con Proceso aleatorio de Markov con tiempo continuo.
Dejalo ser sistema fisico S, que puede estar en norte estados S 1 , S 2 , …, sn. Las transiciones de un estado a otro sólo son posibles en momentos determinados. t 1 , t 2 , …, tk, llamemos a estos momentos en pasos de tiempo. Consideraremos la empresa conjunta en el sistema. S en función del argumento entero 1, 2, ..., k, donde el argumento es el número de paso.
Ejemplo: S 1 → S 2 → S 3 → S 2 .
Acordemos designar si yo (k) – un evento que consiste en el hecho de que después k pasos el sistema está en estado S i.
Para cualquier k eventos S 1 ( k), S 2 ( k) ,…, S norte (k) forma grupo completo de eventos y son incompatible.

Un proceso en un sistema se puede representar como una cadena de eventos.
Ejemplo: S 1 (0) , S 2 (1), S 3 (2), S 5 (3),….
Esta secuencia se llama cadena de markov , si para cada paso la probabilidad de transición desde cualquier estado si yo en cualquier condición sj no depende de cuándo y cómo el sistema alcanzó el estado si yo.
Dejar en cualquier momento después de cualquier k-sistema de paso S puede estar en uno de los estados S 1 , S 2 , …, sn, es decir, puede ocurrir un evento de un grupo completo de eventos: S 1 (k), S 2 ( k) , …, sn (k). Denotemos las probabilidades de estos eventos:
PAG 1 (1) = PAG(S 1 (1)); PAG 2 (1) = PAG(S 2 (1)); …; pn(1) = PAG(sn (k));
PAG 1 (2) = PAG(S 1 (2)); PAG 2 (2) = PAG(S2(2)); ...; pn(2) = PAG(sn (2));
PAG 1 (k) = PAG(S 1 (k)); PAG 2 (k) = PAG(S 2 (k)); …; pn(k) = PAG(sn (k)).
Es fácil ver que para cada número de paso se cumple la condición.
PAG 1 (k) + PAG 2 (k) +…+ pn(k) = 1.
Llamemos a estas probabilidades probabilidades estatales Por lo tanto, la tarea será la siguiente: encuentre las probabilidades de los estados del sistema para cualquier k.
Ejemplo. Que haya algún tipo de sistema que pueda estar en cualquiera de los seis estados. entonces, los procesos que ocurren en él se pueden representar como un gráfico de cambios en el estado del sistema (Fig. 7.9, A), o en forma de gráfico de estado del sistema (Fig. 7.9, b).

A)

Arroz. 7.9
Además, los procesos del sistema se pueden representar como una secuencia de estados: S 1 , S 3 , S 2 , S 2 , S 3 , S 5 , S 6 , S 2 .
Probabilidad de estado en ( k+ 1)el paso depende sólo del estado en k- m paso.
Para cualquier paso k hay algunas probabilidades de que el sistema pase de cualquier estado a cualquier otro estado, llamémoslas probabilidades probabilidades de transición de una cadena de Markov.
Algunas de estas probabilidades serán 0 si la transición de un estado a otro no es posible en un solo paso.
La cadena de Markov se llama homogéneo, si los estados de transición no dependen del número de paso, de lo contrario se llama heterogéneo.
Sea una cadena de Markov homogénea y dejemos que el sistema S Tiene norte estados posibles: S 1 , …, sn. Sea conocida la probabilidad de transición a otro estado en un paso para cada estado, es decir, pij(de si yo V sj en un solo paso), entonces podemos escribir las probabilidades de transición como una matriz.

. (7.1)
A lo largo de la diagonal de esta matriz están las probabilidades de que el sistema pase del estado si yo en el mismo estado si yo.
Usando eventos ingresados ​​previamente , podemos escribir probabilidades de transición como probabilidades condicionales:
.
Obviamente, la suma de términos en cada fila de la matriz (1) es igual a uno, ya que los eventos formar un grupo completo de eventos incompatibles.

Al considerar cadenas de Markov, así como al analizar un proceso aleatorio de Markov, se utilizan varios gráficos de estados (figura 7.10).

Arroz. 7.10

Este sistema puede estar en cualquiera de los seis estados, mientras que pij es la probabilidad de que el sistema pase del estado si yo en un estado sj. Para este sistema, escribimos las ecuaciones de que el sistema estuvo en algún estado y fuera de él durante el tiempo t no salió:

EN caso general la cadena de Markov no es homogénea, es decir, la probabilidad pij cambia de un paso a otro. Supongamos que se da una matriz de probabilidades de transición en cada paso, entonces la probabilidad de que el sistema S en k-el paso será en el estado si yo, se puede encontrar usando la fórmula

Conociendo la matriz de probabilidades de transición y el estado inicial del sistema, se pueden encontrar las probabilidades de los estados. después de cualquier k-ésimo paso. Deje que en el momento inicial el sistema esté en el estado sm. Entonces para t = 0
.
Encontremos las probabilidades después del primer paso. Desde el Estado sm el sistema entrará en estados S 1 , S 2 etc. con probabilidades Pm 1 , Pm 2 , …, Pmmm, …, P.m.n.. Luego, después del primer paso, las probabilidades serán iguales.

. (7.2)
Encontremos las probabilidades del estado después del segundo paso: . Calcularemos estas probabilidades usando la fórmula probabilidad total con hipótesis:
.
Las hipótesis serán las siguientes afirmaciones:

• después del primer paso el sistema estaba en el estado S1-H1;
• después de la segunda etapa el sistema estaba en el estado S2-H2;
• después norte del décimo paso, el sistema estaba en el estado S n -H n.

Probabilidad de cualquier estado después del segundo paso:

(7.3)
La fórmula (7.3) resume todas las probabilidades de transición. pij, pero solo se tienen en cuenta los distintos de cero. Probabilidad de cualquier condición después k-ésimo paso:

(7.4)
Por tanto, la probabilidad de un estado después k El paso está determinado por la fórmula recurrente (7.4) a través de las probabilidades ( k – 1)º paso.

Tarea 6. Se proporciona una matriz de probabilidades de transición para una cadena de Markov en un solo paso. Encuentre la matriz de transición de un circuito determinado en tres pasos .
Solución. La matriz de transición de un sistema es una matriz que contiene todas las probabilidades de transición de este sistema:

Cada fila de la matriz contiene las probabilidades de eventos (transición del estado i en un estado j), que forman un grupo completo, por lo que la suma de las probabilidades de estos eventos es igual a uno:

Denotemos por p ij (n) la probabilidad de que, como resultado de n pasos (pruebas), el sistema pase del estado i al estado j. Por ejemplo, p 25 (10) es la probabilidad de transición del segundo estado al quinto en diez pasos. Tenga en cuenta que para n=1 obtenemos probabilidades de transición p ij (1)=p ij .
Se nos asigna una tarea: conociendo las probabilidades de transición p ij, encontrar las probabilidades p ij (n) de la transición del sistema desde el estado i en un estado j detrás norte pasos. Para ello, introducimos un intermedio (entre i Y j) estado r. En otras palabras, asumiremos que desde el estado inicial i detrás metro pasos el sistema irá a un estado intermedio r con probabilidad p ij (n-m), después de lo cual, para el resto n-m pasos desde el estado intermedio r pasará al estado final j con probabilidad p ij (n-m). Usando la fórmula de probabilidad total obtenemos:
.
Esta fórmula se llama igualdad de Markov. Con esta fórmula, puede encontrar todas las probabilidades p ij (n) y, en consecuencia, la propia matriz P n. Dado que el cálculo matricial conduce a la meta más rápidamente, escribimos la relación matricial resultante de la fórmula resultante en forma general.
Calculemos la matriz de transición de la cadena de Markov en tres pasos usando la fórmula resultante:

Respuesta:.

Tarea número 1. La matriz de probabilidad de transición de la cadena de Markov tiene la forma:
.
La distribución entre estados en el momento t=0 está determinada por el vector:
π 0 =(0,5; 0,2; 0,3)
Encontrar: a) distribución por estados en los momentos t=1,2,3,4.
c) distribución estacionaria.

La cadena de Markov es un proceso de Markov de tiempo discreto definido en un espacio mensurable.

Introducción

Los procesos aleatorios de Markov llevan el nombre del destacado matemático ruso A.A. Markov (1856-1922), quien fue el primero en iniciar el estudio de la conexión probabilística de variables aleatorias y creó una teoría que puede denominarse "dinámica de probabilidad".

EN más conceptos básicos esta teoría fue la base inicial teoria general procesos aleatorios, así como tan importantes Ciencias Aplicadas, como la teoría de los procesos de difusión, teoría de la confiabilidad, teoría hacer cola etc. Actualmente, la teoría de los procesos de Markov y sus aplicaciones son ampliamente utilizadas en diversos campos.

Debido a la comparativa simplicidad y claridad del aparato matemático, la alta confiabilidad y precisión de las soluciones obtenidas, Atención especial Procesos de Markov adquirido de especialistas involucrados en la investigación de operaciones y la teoría de la toma de decisiones óptimas.

Ejemplo sencillo: lanzar una moneda al aire

Antes de dar una descripción esquema general, pasemos a ejemplo sencillo. pretendamos que estamos hablando acerca de sobre lanzamientos sucesivos de una moneda en un juego de lanzamiento; Se lanza una moneda en momentos condicionales de tiempo t = 0, 1, ... y en cada paso el jugador puede ganar ±1 con la misma probabilidad de 1/2, por lo que en el momento t su ganancia total es valor aleatorioξ(t) con valores posibles j = 0, ±1, ...

Siempre que ξ(t) = k, en el siguiente paso la ganancia ya será igual a ξ(t+1) = k ± 1, tomando valores especificados j = k ± 1 con igual probabilidad 1/2.

Convencionalmente, podemos decir que aquí, con la probabilidad correspondiente, se produce una transición del estado ξ(t) = k al estado ξ(t+1) = k ± 1.

Fórmulas y definiciones

Generalizando este ejemplo, podemos imaginar un "sistema" con un número contable de posibles estados de "fase", que en el transcurso de un tiempo discreto t = 0, 1, ... pasa aleatoriamente de un estado a otro.

Sea ξ(t) su posición en el tiempo t como resultado de una cadena de transiciones aleatorias

ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)

Denotemos formalmente todo estados posibles números enteros i = 0, ±1, ... Supongamos que para un estado conocido ξ(t) = k, en el siguiente paso el sistema pasa al estado ξ(t+1) = j con probabilidad condicional

p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)

independientemente de su comportamiento en el pasado, más precisamente, independientemente de la cadena de transiciones (1) hasta el momento t:

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) para todos t, k, j... (3) - Propiedad de Markov.

Este esquema probabilístico se llama cadena de Markov homogénea con un número contable de estados- su homogeneidad radica en que los definidos en (2) probabilidades de transición p kj, ∑ j p kj = 1, k = 0, ±1, ..., no dependen del tiempo, es decir P(ξ(t+1) = j|ξ(t) = k) = P ij - matriz de probabilidad de transición en un paso no depende de n.

Está claro que Pij - matriz cuadrada con elementos no negativos y sumas unitarias en las filas.

Tal matriz (finita o infinita) se llama matriz estocástica. Cualquier matriz estocástica puede servir como matriz de probabilidades de transición.

En la práctica: entrega de equipos a los distritos

Supongamos que una determinada empresa entrega equipos en Moscú: distrito norte(denotado por A), sur (B) y central (C). La empresa cuenta con un equipo de mensajería que presta servicios en estas zonas. Está claro que para realizar la siguiente entrega, el mensajero se dirige a la zona que actualmente está más cerca de él. Se determinó estadísticamente lo siguiente:

1) después de la entrega a A, la siguiente entrega se realiza en 30 casos en A, en 30 casos - en B y en 40 casos - en C;

2) después de la entrega a B, la siguiente entrega se realiza en 40 casos en A, en 40 casos - en B y en 20 casos - en C;

3) después de la entrega a C, la siguiente entrega se realiza en 50 casos en A, en 30 casos - en B y en 20 casos - en C.

Por lo tanto, la siguiente zona de entrega está determinada únicamente por la entrega anterior.

La matriz de probabilidad de transición se verá así:

Por ejemplo, p 12 = 0,4 es la probabilidad de que después de la entrega en el área B, la siguiente entrega se realice en el área A.

Supongamos que cada entrega seguida del traslado a la siguiente área tarda 15 minutos. Entonces, según las estadísticas, después de 15 minutos el 30% de los mensajeros que estaban en A estarán en A, el 30% estarán en B y el 40% estarán en C.

Dado que en el próximo momento cada uno de los mensajeros definitivamente estará en uno de los distritos, la suma de las columnas es igual a 1. Y como estamos tratando con probabilidades, cada elemento de la matriz es 0<р ij <1.

La circunstancia más importante que nos permite interpretar este modelo como una cadena de Markov es que la ubicación del mensajero en el tiempo t+1 depende solo desde la ubicación en el momento t.

Ahora hagamos una pregunta simple: si el mensajero parte de C, ¿cuál es la probabilidad de que después de realizar dos entregas esté en B, es decir? ¿Cómo puedes lograr B en 2 pasos? Entonces, hay varios caminos de C a B en 2 pasos:

1) primero de C a C y luego de C a B;

2) C-->B y B-->B;

3) C-->A y A-->B.

Dada la regla de la multiplicación eventos independientes, encontramos que la probabilidad deseada es igual a:

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

Sustituyendo valores numéricos:

P = 0,5*0,3 + 0,3*0,4 + 0,2*0,3 = 0,33

El resultado obtenido sugiere que si el mensajero empezó a trabajar desde C, en 33 de cada 100 casos estará en B después de dos entregas.

Claramente los cálculos son simples, pero si necesitas determinar la probabilidad después de 5 o 15 entregas, puede llevar bastante tiempo.

Mostremos una forma más sencilla de calcular tales probabilidades. Para obtener las probabilidades de transición de varias condiciones en 2 pasos elevamos al cuadrado la matriz P:

Entonces el elemento (2, 3) es la probabilidad de transición de C a B en 2 pasos, que se obtuvo anteriormente de otra manera. Tenga en cuenta que los elementos de la matriz P2 también varían de 0 a 1, y la suma de las columnas es 1.

Eso. si necesita determinar las probabilidades de transición de C a B en 3 pasos:

1 vía. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0,37*0,3 + 0,33*0,4 + 0,3*0,3 = 0,333, donde p(CA) - la probabilidad de transición de C a A en 2 pasos (es decir, este es el elemento (1, 3) de la matriz P 2).

Método 2. Calcular la matriz P3:

La matriz de probabilidades de transición a la séptima potencia se verá así:

Es fácil notar que los elementos de cada línea tienden a algunos números. Esto sugiere que después de suficiente gran cantidad Entrega, no importa en qué distrito comenzó a trabajar el mensajero. Eso. al final de la semana aproximadamente el 38,9% estará en A, el 33,3% estará en B y el 27,8% estará en C.

Se garantiza que dicha convergencia se producirá si todos los elementos de la matriz de probabilidad de transición pertenecen al intervalo (0, 1).