IB DP Maths: AI HL复习笔记4.13.2 Transition Matrices

What is a transition matrix?

• A transition matrix T shows the transition probabilities between the current state and the next state
  • The columns represent the current states
  • The rows represent the next states

• The element of T in the i^th row and j^th column gives the transition probability t_ij of :

• • the next state being the state corresponding to row i
  • given that the current state is the state corresponding to column j
• The probabilities in each column must add up to 1
• The transition matrix depends on how you assign the states to the columns
  • Each transition matrix for a Markov chain will contain the same elements
    • The rows and columns may be in different orders though
    • E.g. Sunny (S) & Cloudy (C) could be in the order S then C or C then S

What is an initial state probability matrix?

• An initial state probability matrix s₀ is a column vector which contains the probabilities of each state being chosen as the initial state
  • If you know which state was chosen as the initial state then that entry will be 1 and the others will all be zero
• You can find the state probability matrix s₁ which contains the probabilities of each state being chosen after one interval of time
  • s₁ = Ts₀

How do I find expected values after one interval of time?

• Suppose the Markov change represents a population moving between states
  • Examples include:
    • People in a town switching gyms each year
    • Children choosing a type of sandwich for their lunch each day
• Suppose the total population is fixed and equals N
• You can multiply the state probability matrix s₁ by N to find the expected number of members of the population at each state

How do I find powers of a transition matrix?

• You can simply use your GDC to find given powers of a matrix
• The power could be left in terms of an unknown n
  • In this case it would be more helpful to write the transition matrix in diagonalised form (see section 1.8.2 Applications of Matrices) T = PDP^-1 where
    • D is a diagonal matrix of the eigenvalues
    • P is a matrix of corresponding eigenvectors
  • Then Tⁿ = PDⁿP^-1
    • This is given in the formula booklet
  • Every transition matrix always has an eigenvalue equal to 1

What is represented by the powers of a transition matrix?

• The powers of a transition matrix also represent probabilities

• The element of Tⁿ in the i^th row and j^th column gives the probability tⁿ_ij of :

• • the future state after n intervals of time being the state corresponding to row i
  • given that the current state is the state corresponding to column j

• For example: Let T be a transition matrix with the element t_2,3 representing the probability that tomorrow is sunny given that it is raining today

• • The element t⁵_2,3 of the matrix T⁵ represents the probability that it is sunny in 5 days’ time given that it is raining today
• The probabilities in each column must still add up to 1

How do I find the column state matrices?

• The column state matrix s_n is a column vector which contains the probabilities of each state being chosen after n intervals of time given the current state
  • s_n depends on s₀
• To calculate the column state matrix you raise the transition matrix to the power n and multiply by the initial state matrix
  • You are given this in the formula booklet
• You can multiply s_n by the fixed population size to find the expected number of members of the population at each state after n intervals of time

What is the steady state of a regular Markov chain?

• The vector s is said to be a steady state vector if it does not change when multiplied by the transition matrix
  • Ts = s
• Regular Markov chains have steady states
  • A Markov chain is said to be regular if there exists a positive integer ksuch that none of the entries are equal to 0 in the matrix T^k
    • For this course all Markov chains will be regular
• The transition matrix for a regular Markov chain will have exactly one eigenvalue equal to 1 and the rest will all be less than 1
• As n gets bigger Tⁿtends to a matrix where each column is identical
  • The column matrix formed by using one of these columns is called the steady state column matrix s
  • This means that the long-term probabilities tend to fixed probabilities
    • s_n tends to s

How do I use long-term probabilities to find the steady state?

• As Tⁿtends to a matrix whose columns equal the steady state vector
  • Calculate Tⁿ for a large value of n using your GDC
  • If the columns are identical when rounded to a required degree of accuracy then the column is the steady state vector
  • If the columns are not identical then choose a higher power and repeat

How do I find the exact steady state probabilities?

• As Ts= sthe steady state vector sis the eigenvector of T corresponding to the eigenvalue equal to 1 whose elements sum to 1:
  • Let shave entries x₁, x₂, ..., x_n
  • Use Ts= sto form a system of linear equations
  • There will be an infinite number of solutions so choose a value for one of the unknowns
    • For example: let x_n = 1
  • Ignoring the last equation solve the system of linear equations to find x₁, x₂, ..., x_{n – 1}
  • Divide each value x_i by the sum of the values
    • This makes the values add up to 1
• You might be asked to show this result using diagonalisation
  • Write T = PDP^-1 where D is the diagonal matrix of eigenvalues and P is the matrix of eigenvectors
  • Use Tⁿ = PDⁿP^-1
  • As n gets large Dⁿtends to a matrix where all entries are 0 apart from one entry of 1 due to the eigenvalue of 1
  • Calculate the limit of Tⁿ which will have identical columns
    • You can calculate this by multiplying the three matrices (P, D^∞, P^-1) together