String de Markov

Las strings de Markov, llamadas así por Andrey Markov, son un modelo estocástico que representa una secuencia de posibles eventos donde las predicciones o probabilidades para el siguiente estado se basan únicamente en su estado de evento anterior, no en los estados anteriores. En palabras sencillas, la probabilidad de que n+1 ^pasos sean x depende solo del paso n, no de la secuencia completa de pasos anterior a n. Esta propiedad se conoce como propiedad de Markov o falta de memoria. Exploremos nuestra string de Markov con la ayuda de un diagrama,

son procesos de Markov

Un diagrama que representa un proceso de Markov de dos estados (aquí, E y A). Aquí las flechas se originaron en el estado actual y apuntan al estado futuro y el número asociado con las flechas indica la probabilidad de que el proceso de Markov cambie de un estado a otro. Por ejemplo, si el proceso de Markov está en el estado E, entonces la probabilidad de que cambie al estado A es 0,7, mientras que la probabilidad de que permanezca en el mismo estado es 0,3. De manera similar, para cualquier proceso en el estado A, la probabilidad de cambiar a Estado es 0,4 y la probabilidad de permanecer en el mismo estado es 0,6.

¿Cómo representar la string de Markov?

Del diagrama del proceso de Markov de dos estados, podemos entender que la string de Markov es un gráfico dirigido. Entonces podemos representarlo con la ayuda de una array de adyacencia.

                +——+——+          

                 | un | mi | — Cada elemento denota el peso de probabilidad del borde                        

     +——+——+——+ conectando los dos vértices correspondientes                                      

      | un | 0.6 | 0.4 | — 0,4 es la probabilidad de que el estado A pase al estado E y 0,6 es la probabilidad  

     +——+——+——+ para permanecer en el mismo estado  

      | mi | 0.7 | 0.3 | — 0,7 es la probabilidad de que el estado E pase al estado A y 0,3 es la probabilidad  

     +——+——+——+ para permanecer en el mismo estado  

Esta array también se llama Array de Transición . Si la string de Markov tiene N estados posibles, la array será una array NxN. Cada fila de esta array debe sumar 1. Además de esto, una string de Markov también tiene un vector de estado inicial de orden Nx1. Estas dos entidades son imprescindibles para representar una string de Markov.

Array de transición de N pasos: ahora aprendamos arrays de transición de orden superior. Nos ayuda a encontrar la posibilidad de que esa transición ocurra en varios pasos. En pocas palabras, ¿cuál será la probabilidad de pasar del estado A al estado E en el paso N? En realidad, hay una manera muy simple de calcularlo. Esto se puede determinar calculando el valor de entrada (A, ) de la array obtenida al elevar la array de transición a la potencia de N.

Tipos de string de Markov:

Strings de Markov de tiempo discreto : Esto implica que el conjunto de índices T (estado del proceso en el momento t) es un conjunto contable aquí o podemos decir que los cambios ocurren en estados específicos. Generalmente, el término «string de Markov» se usa para DTMC.

Strings de Markov de tiempo continuo : aquí el conjunto de índices T (estado del proceso en el tiempo t) es un continuo, lo que significa que los cambios son continuos en CTMC.

Propiedades de la string de Markov:

1. Se dice que una string de Markov es irreducible si podemos pasar de un estado a otro en un solo paso o en más de uno.
2. Se dice que un estado en una string de Markov es periódico si volver a él requiere un múltiplo de algún número entero mayor que 1, el máximo común divisor de todas las posibles longitudes de la ruta de retorno será el período de ese estado.
3. Se dice que un estado en una string de Markov es Transitorio si existe una probabilidad distinta de cero de que la string nunca vuelva al mismo estado; de lo contrario, es Recurrente.
4. Un estado en una string de Markov se llama Absorbente si no hay forma posible de salir de ese estado. Los estados absorbentes no tienen transiciones salientes.

String de Markov en Python:

# let's import our library
import scipy.linalg
import numpy as np
 
 
# Encoding this states to numbers as it
# is easier to deal with numbers instead
# of words.
state = ["A", "E"]
 
# Assigning the transition matrix to a variable
# i.e a numpy 2d matrix.
MyMatrix = np.array([[0.6, 0.4], [0.7, 0.3]])
 
# Simulating a random walk on our Markov chain
# with 20 steps. Random walk simply means that
# we start with an arbitrary state and then we
# move along our markov chain.
n = 20
 
# decide which state to start with
StartingState = 0
CurrentState = StartingState
 
# printing the stating state using state
# dictionary
print(state[CurrentState], "--->", end=" ")
 
while n-1:
    # Deciding the next state using a random.choice()
    # function,that takes list of states and the probability
    # to go to the next states from our current state
    CurrentState = np.random.choice([0, 1], p=MyMatrix[CurrentState])
     
    # printing the path of random walk
    print(state[CurrentState], "--->", end=" ")
    n -= 1
print("stop")
 
# Let us find the stationary distribution of our
# Markov chain by Finding Left Eigen Vectors
# We only need the left eigen vectors
MyValues, left = scipy.linalg.eig(MyMatrix, right=False, left=True)
 
print("left eigen vectors = \n", left, "\n")
print("eigen values = \n", MyValues)
 
# Pi is a probability distribution so the sum of
# the probabilities should be 1 To get that from
# the above negative values we just have to normalize
pi = left[:, 0]
pi_normalized = [(x/np.sum(pi)).real for x in pi]
pi_normalized

Aplicación de la string de Markov:

Las strings de Markov hacen que el estudio de muchos procesos del mundo real sea mucho más simple y fácil de entender. Usando la string de Markov podemos obtener algunos resultados útiles, como la distribución estacionaria y muchos más. 

1. MCMC (String de Markov Monte Carlo), que da una solución a los problemas que surgen del factor de normalización, se basa en la String de Markov.
2. Las strings de Markov se utilizan en teoría de la información, motores de búsqueda, reconocimiento de voz, etc.
3. La string de Markov tiene enormes posibilidades, futuro e importancia en el campo de la ciencia de datos y se solicita a los lectores interesados ​​que aprendan estas cosas correctamente para ser una persona competente en el campo de la ciencia de datos.

Supuestos para la string de Markov:

1. El sistema estadístico contiene un número finito de estados.
2. Los estados son mutuamente excluyentes y colectivamente exhaustivos.
3. La probabilidad de transición de un estado a otro estado es constante en el tiempo.

Los procesos de Markov son bastante comunes en problemas de la vida real y las strings de Markov se pueden implementar fácilmente debido a su propiedad de falta de memoria. El uso de la string de Markov puede simplificar el problema sin afectar su precisión.

Tomemos un ejemplo para comprender la ventaja de esta herramienta, supongamos que mi amigo sugiere comer. Puedo decir que no quiero una pizza porque la tengo hace una hora. Pero, ¿es apropiado si digo que no quiero una pizza porque la tengo hace dos meses? Eso significa que, en este caso, mi probabilidad de elegir una comida depende completamente de mi comida inmediatamente anterior. Aquí está la efectividad de la String de Markov.