<jupyter_start><jupyter_text>Data Science with Python : Markov's Chain 377  What is Markov's Chain ? Markov chains, named after <NAME>, a stochastic model that depicts a sequence of possible events where predictions or probabilities for the next state based solely on its previous event state not the states before. In simple words, the probability that n+1 th steps will be x depends only on the nth steps not the complete sequence of steps that came before n. This property is known as Markov Property or Memorylessness.Let us explore our Markov chain with the help of a diagram,A diagram representing a two-state(here, E and A) Markov process.Here the arrows originated from the current state and points to the future state and the number associated with the arrows indicates the probability of the Markov process changing from one state to another state. For instance,if the Markov process is in state E, then the probability it changes to state A is 0.7, while the probability it remains in same state is 0.3. Similarly, for any process in state A, probability to change to E state is 0.4 and probability to remain in same state is 0.6.  How to Represent Markov Chain ? From the diagram of the two state Markov process ,we can understand that the Markov chain is directed graph. So we can represent is with the help of an adjacency matrix.                   +-------+-------+                          |   A   |   E   |        --- Each element denotes the probability weight of the edge                                +-------+-------+-------+               connecting the two corresponding vertices                                              |   A   |  0.6  |  0.4  |        --- 0.4 is the probability for state A to go to state E and 0.6 is the probability          +-------+-------+-------+               to remain at the same state          |   E   |  0.7  |  0.3  |        --- 0.7 is the probability for state E to go to state A and 0.3 is the probability          +-------+-------+-------+               to remain at the same state                   This matrix is also called Transition Matrix. If the Markov chain has N possible states, the matrix will be an NxN matrix. Each row of this matrix should sum to 1.In addition to this, a Markov chain also has an Initial State Vector of order Nx1.These two entities are must to represent a Markov chain.N-step Transition Matrix : Now let us learn higher order transition matrices. It helps us to find the chance of that transition occurring over multiple steps. To put in simple words, what will be the probability of moving from state A to state E over N step? There is actually a very simple way to calculate it. This can be determined by calculating the value of entry (A,E) of the matrix obtained by raising the transition matrix to the power of N.  Markov Chain in Python : Now we are going to code our Markov chain example above in python. Although for computing efficiently we generally use a library encoded Markov chain.<jupyter_code>#let's import our library
import numpy as np
#Encoding this states to numbers as it is easier to deal with numbers instead of words.
state = {
    0 : "A",
    1 : "E",
}
state
#Assigning the transition matrix to a variable i.e a numpy 2d matrix.
MyMatrix = np.array([[0.6, 0.4], [0.7, 0.3]])
MyMatrix
#Simulating a random walk on our Markov chain with 20 steps.
#Random walk simply means that we start with an arbitary state and then we move along our markov chain.
n = 20
StartingState = 0                                     #decide which state to start with
CurrentState = StartingState
print(state[CurrentState], "--->", end=" ")           #printing the stating state using state dictionary

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])
    print(state[CurrentState], "--->", end=" ")       #printing the path of random walk
    n-=1
print("stop")
#Let us find the stationary distribution of our Markov chain using repeated matrix multiplication
NumberOfSteps = 10**3
MyMatrix_n = MyMatrix

i=0
while i<NumberOfSteps:
    MyMatrix_n =  np.matmul(MyMatrix_n, MyMatrix)     #Multiplying our matrix with itself and storing it into MyMatrix_n
    i+=1

print("MyMatrix^n = \n", MyMatrix_n, "\n")
print("π = ", MyMatrix_n[0])                          #Printing the probability distribution
#Let us find the stationary distribution of our Markov chain by Finding Left Eigen Vectors
#Importing our library
import scipy.linalg
MyValues, left = scipy.linalg.eig(MyMatrix, right = False, left = True)    #We only need the left eigen vectors

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<jupyter_output><empty_output><jupyter_text>Computing the Probability Corresponding to a Particular Sequence:<jupyter_code>#How about finding P(A-->E-->E-->A)

def calculate_probability(sequence, MyMatrix, pi):
    StartingState = sequence[0]
    prob = pi[StartingState]                                       #initializing prob with the prob of the start state
    PreviousState, CurrentState = StartingState, StartingState
    for i in range(1, len(sequence)):
        CurrentState = sequence[i]
        #Multiplying the transition prob from previous to current state with the current value of prob
        prob *= MyMatrix[PreviousState][CurrentState]
        PreviousState = CurrentState
    return prob

print(calculate_probability([0, 1, 1, 0], MyMatrix, pi_normalized))<jupyter_output>0.053454545454545456
{'fraction_non_alphanumeric': 0.07442813246841926, 'fraction_numerical': 0.014168658245134857, 'mean_word_length': 2.974898236092266, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '35451', 'license': 'MIT', 'n_tokens_mistral': 1550, 'n_tokens_neox': 1459, 'n_words': 786, 'path': "Datascience_With_Python/Statistics/Tutorials/Markov's Chain/markovs_chain.ipynb", 'repo_name': 'vishnupriya129/winter-of-contributing', 'size': '5865'}