MarkovChains.md (3459B)
1 # Markov Chains 2 3 L13 4 5 **Definition:** A markov chain is a sequence of events where the probability of any given event is **entirely** based on the previous event. 6 7 Given that the state needs to have all relevant information, we need to choose our states properly to ensure accuracy. 8 9 Anything that evolves with time can be described as a markov chain. 10 11 These types of processes are not memoryless like [BernoulliProcess](BernoulliProcess.md) or [[PoissonDistribution.md]]. 12 13 #### Markov Assumption 14 15 The Markov assumption is the assumption that each state describes the probability of all transitions related to it regardless of prior states/transitions. 16 17 #### Finite Markov Chain Example 18 19 Checkout counter: 20 21 Customers get in queue (bernoulli process) and then they are served one at a time. 22 23 If customer is in queue they are then served which takes a random amount of time. 24 25 What is the probability of a customer departing at a given time? 26 - If the queue is empty the odds are 0 (assuming the person being seen is still in the 'queue') 27 - If the queue is not empty then the odds are not 0 28 29 As such, this depends on the state of the system making it a markov chain. 30 31 If there are only 10 customers who can be in the place then we can write out all states from 0 people to 10 people along with relations between them relating to people moving up the queue, being added to the queue, no changes, and adding to queue and removing at the same time. All of these probabilities summed have to equal 1 for each state. 32 33 Each of these connections (transitions) have their own probabilities. 34 35 #### Creation 36 37 Identify all possible states (think about if each state is sufficient to assign transition probabilities) 38 39 Identify transitions 40 41 Find transition probabilities (sum to 1) 42 43 #### n-step transition probability 44 45 n-step transition probabilities are probabilities that starting at state i after n steps we are now in state j. This is stated as: 46 47 r_{ij}(n) = P(X_n=j | X_0=i) 48 49 To calculate this we can find the probability of each transition for all steps until and including step number n. This is done by multiplying the probablity of a given state by the probability of the transition. The solution will be the final probability of the state j. 50 51 Alternatively, we can use recursive approach to find the probability of each transition that connects to the state i. 52 53 #### Steady State (Convergence) 54 55 The steady state of a markov chain is the constant probability of some given state after an arbitrarily long period of time. This can be thought of the limit as n approaches infinity. If there is not convergence then there is not a steady state. 56 57 In most cases we will reach a steady state but this might not happen in cases of [PeriodicChain](PeriodicChain.md) or irreducability where not all states there are two seperate recurrent loops. The seperate recurrent loops cause a non-steady state because steady states need to be initial condition agnostic. 58 59 #### Recurrent 60 61 A state is recurrent if starting from the state there is always a way to get back. We will always end up in a recurrent state after an arbitrarily long period of time as transient states will enventually become unreachable. 62 63 #### Transient 64 65 Transient states are states that are not recurrent meaning there are cases where you can not get back to them assuming they are the initial state. 66 67 As such, the probability of the current state being a transient state after an arbitrarily long time is 0.