The objective of this practical is to make you see a Markov chain in action. In particular, you will observe what happens if the conditions of the Perron-Frobenius theorem are not met.
In [ ]:
%pylab inline
from matplotlib import animation, rc
from IPython.display import HTML
# Uncomment the following line if you want to pimp your animation a little bit
# with xkcd-like display (will cost extra computation time)
# xkcd()
Right stochastic matrix. Let $A = (a_{i,j})$ be a $n \times n$ matrix. We say that $A$ is a right stochastic matrix if:
Homogeneous Markov chain. An $n \times n$ right stochastic matrix $A = (a_{i,j})$ can define a Markov Chain that describes the evolution of a distribution over $n$ states as follows: if one is in state $i$ at step $k$ of the process, the probability to be in state $j$ at step $k+1$ is $a_{i,j}$.
With this matrix notation, the evolution of the Markov chain is easy to study: if $P_k$ is the probability distribution at step $k$ (in particular, $P_k\geq 0$ and $\sum_{i}P_k[i]=1$), then we have $$P_{k+1}=P_k A, \quad \forall k \in \mathbb{N}.$$
Irreducibility. Let $A$ be a non-negative matrix ($\forall i,j, a_{i,j}\geq 0$). Let $G=(V,E)$ be the oriented graph associated to $A$: $(i,j)\in E$ if, and only if $A[i,j]>0$. The following propositions are equivalent:
Intuitively, the irreducibility property indicates that, starting from any state, the Markov chain can reach any state with a positive (e.g. >0) probability after some steps.
Aperiodicity (from Wikipedia). The period of a state $i$ is the greatest common divisor of the lengths of the cycles that state $i$ belongs to. If we reformulate this definition in terms of the transition matrix, the period of state $i$ is the greatest common divisor of all natural numbers $k$ such that $A^k[i,i] > 0$. When the Markov chain is irreducible, the period of every state is the same and is called the period of the Markov chain.
A Markov chain is said aperiodic if the period of each state is 1.
Intuitively, a period $k>1$ indicates that the length of any cycle must be a multiple of $k$.
Perron-Frobenius Theorem (a variant, actually). If a matrix $A$ is right stochastic, irreducible and aperiodic, then $A^k \to B$ as $k \to +\infty$, where $B$ is the right stochastic matrix having all its rows equal to the same row vector $Q$ defined as the unique normalized solution to the equation $QA = Q$.
Interpretation. When the condition of the Perron-Frobenius theorem are met, the Markov chain will eventually converge to a unique distribution, independently of its initial state which is forgotten.
To start with, we consider a small experiment that plays with the assumptions of Perron-Frobenius theorem.
Consider a circular game board made of $ n = 36 $ squares numbered from $ 0 $ to $ 35 $. At the (discrete) turn $ k=0 $, a player stands on square $ 0 $. Between two successive turns, the player moves of a certain number of squares that depends on the game rules. Remember that the board is circular: if the player is in square $35$ and moves one square forward, she lands in square $0$.
The objective of this exercice is to visualize the impact of the game rules on the (probabilistic) position of the player on the board.
We now give you the code to visualize the game evolution in a toy example. For now, the player (deterministically) moves one square forward at each turn.
The function evolution displays the evolution of a distribution. It takes three arguments:
next_step: a function that takes a distribution as input and returns the resulting distribution after one step of the Markov process.k_max: the number of steps you want to watch.n: the size of the game board
In [ ]:
def evolution(next_step, k_max=180, n=36):
# Turn interactive plotting off
plt.ioff()
# Initiate figure
fig, ax = subplots()
# Initiate probability distribution: the initial position of the player is known: she is in square 0
P = zeros(n)
P[0] = 1
# Display probability
pbar = ax.bar(range(n), P, 1)
xlim([0, n])
#Init only required for blitting to give a clean slate.
def init():
for rect, y in zip(pbar, P):
rect.set_height(y)
return pbar
# animate tells what to do at step i of the process
def animate(i):
for rect, y in zip(pbar, P):
rect.set_height(y)
P[:] = next_step(P) # Update the values using the next_step function
return pbar
# create the animation object
ani = animation.FuncAnimation(
fig, animate, frames=k_max, init_func=init, interval=50, blit=True)
# return the video as HTML to display in the output of the cell
return HTML(ani.to_html5_video())
The rule for the toy example is to move one case forward. This can be easily done with the function roll from numpy package.
In [ ]:
def next_step(P):
# Roll, baby!
return roll(P, 1)
We now call the function evolution. It can take a few seconds to initiate, depending on the k_max you choose.
In [ ]:
evolution(next_step, 180)
Answer:
We now change the rules. At each turn, the player tosses an unbiased coin. If it is a head, she moves forward $ a = 1 $ step. If it is a tail, she moves forward $ b = 2 $ steps. Visualize the evolution of the position of the player. Comment what you observe.
Remark: The game rules are not trivial any more, so that we will play with more general Markov chains. Updating the vector P by applying the function roll won't be enough anymore. You may want to use dot(P, A), which multiplies a vector $P$ and a matrix $A$, with a properly built matrix $A$. To do so, we define below the function next_stepA(P) that takes a vector $P$ as input. In each question of the exercise, you will simply have to
evolution(next_stepA, nb_of_steps) to generate the video, where nb_of_steps is the number of steps you wish to observe;
In [ ]:
def next_stepA(P):
return dot(P, A)
Answer:
Answer:
Answer:
Answer:
Answer:
The goal of this second exercise is to test a few variants of PageRank on small graphs and see how they differ. The next practical will give you the opportunity to experience PageRank on larger (and more realistic) graphs.
Let $ h $ be an integer (we will use $h = 2$ for the toy evaluation and $h = 9$ for the complete evaluation). We consider the following web graph $ G $:
Remark: there is at most one edge from a node $i$ to a node $j$, even when several rules indicate the existence of the edge.
Build the transition matrix $A$ associated to the Markov chain defined by the position of the random surfer on the graph $G$ described above. For memory, this matrix is defined by $ a_{i,j} = \frac1{\text{deg}_+(i)}$ if there is an edge from $ i $ to $ j $, and $a_{i,j} = 0$ otherwise (where $\text{deg}_+(i)$ is the outdegree of a node $i$).
Answer:
Answer:
Compute the PageRank $P$ which is a solution of $ P = P A $. Proceed iteratively, starting from the uniform distribution $ P = \frac{\mathbf{1}}n $ and updating $ P \leftarrow P A $ until $ ||P-PA||_1<\epsilon $ (recommendation: $ \epsilon = 10^{-8} $).
You function should display:
You should impose a maximum number of authorized iterations to avoid infinite loops (recommendation: 2000 iterations). When reaching the maximal number of iterations, your function should display a message saying the process has not converged and giving the last top ten that was computed.
Answer:
We supplement the web graph $G$ with $b = 10$ new nodes numbered from $ n $ to $ n+b-1 $. For each new node $ i $, we add an edge from $ i-1 $ to $i$.
Answer:
We add a single edge to the previous graph, from node $ n+b-1 $ to node $ n+b-2 $.
Answer:
Answer: