Please provide tutorial for CodeChef: Practical coding for everyone
Google “Markov Chains”
1 Like
Let A represent the matrix, and A_{ij} represent the element at the ith row and $jth$column. First divide A_{ij} by \sum A_i, so that A_{ij} Now represents the probability of going from the ith state to the jth state in one step.
What is the probability of going from some state x to some state y in 2 steps?
It’s just \sum P(x->i)\times P(i->y), where P(i->j) represents the probability of going from the ith state to the jth state.We know that is just A_{ij} so the answer is \sum A_{xi}A_{iy}. This is because we will start at x, go to some intermediate state i and then go to y. We are just adding the probability for all possible intermediate states.
This is just the calculation of Matrix multiplication.
So the matrix that tells us the probabilty of going from x to y in 2 steps is just A^2. In fact, This is true for any power, and we can prove it by induction.
Let us assume A^a is the matrix representing the probability matrix for a
steps, and A^b is the matrix representing the probability matrix for b steps.
So we know that A^{a+b}_{xy} = \sum A^a_{xi}A^b_{iy}, which is still the algorithm for matrix multiplication. This time we are not reaching i immediately, but after a steps. We know that there must be some i we will have to be after a steps. We are just adding all of them.
This is also known as a Markov chain.
4 Likes