Solutions for http://quant-econ.net/py/finite_markov.html
In [1]:
%matplotlib inline
In [2]:
from __future__ import print_function, division # Omit for Python 3.x
import numpy as np
import matplotlib.pyplot as plt
from quantecon import MarkovChain
Compute the fraction of time that the worker spends unemployed, and compare it to the stationary probability.
In [3]:
alpha = beta = 0.1
N = 10000
p = beta / (alpha + beta)
P = ((1 - alpha, alpha), # Careful: P and p are distinct
(beta, 1 - beta))
mc = MarkovChain(P)
fig, ax = plt.subplots(figsize=(9, 6))
ax.set_ylim(-0.25, 0.25)
ax.grid()
ax.hlines(0, 0, N, lw=2, alpha=0.6) # Horizonal line at zero
for x0, col in ((0, 'blue'), (1, 'green')):
# == Generate time series for worker that starts at x0 == #
X = mc.simulate(x0, N)
# == Compute fraction of time spent unemployed, for each n == #
X_bar = (X == 0).cumsum() / (1 + np.arange(N, dtype=float))
# == Plot == #
ax.fill_between(range(N), np.zeros(N), X_bar - p, color=col, alpha=0.1)
ax.plot(X_bar - p, color=col, label=r'$X_0 = \, {} $'.format(x0))
ax.plot(X_bar - p, 'k-', alpha=0.6) # Overlay in black--make lines clearer
ax.legend(loc='upper right')
Out[3]:
First save the data into a file called web_graph_data.txt by executing the next cell
In [4]:
%%file web_graph_data.txt
a -> d;
a -> f;
b -> j;
b -> k;
b -> m;
c -> c;
c -> g;
c -> j;
c -> m;
d -> f;
d -> h;
d -> k;
e -> d;
e -> h;
e -> l;
f -> a;
f -> b;
f -> j;
f -> l;
g -> b;
g -> j;
h -> d;
h -> g;
h -> l;
h -> m;
i -> g;
i -> h;
i -> n;
j -> e;
j -> i;
j -> k;
k -> n;
l -> m;
m -> g;
n -> c;
n -> j;
n -> m;
In [5]:
"""
Return list of pages, ordered by rank
"""
import numpy as np
from operator import itemgetter
import re
infile = 'web_graph_data.txt'
alphabet = 'abcdefghijklmnopqrstuvwxyz'
n = 14 # Total number of web pages (nodes)
# == Create a matrix Q indicating existence of links == #
# * Q[i, j] = 1 if there is a link from i to j
# * Q[i, j] = 0 otherwise
Q = np.zeros((n, n), dtype=int)
f = open(infile, 'r')
edges = f.readlines()
f.close()
for edge in edges:
from_node, to_node = re.findall('\w', edge)
i, j = alphabet.index(from_node), alphabet.index(to_node)
Q[i, j] = 1
# == Create the corresponding Markov matrix P == #
P = np.empty((n, n))
for i in range(n):
P[i,:] = Q[i,:] / Q[i,:].sum()
# == Create the corresponding MarkovChain instance == #
mc = MarkovChain(P)
Verify that our Markov chain mc is irreducible,
so that it has a unique stationary distribution,
and that it is in addition aperiodic,
so that it is uniformly ergodic.
In [6]:
mc.is_irreducible and mc.is_aperiodic
Out[6]:
Now obtain the list of pages ordered by rank.
In [7]:
# == Compute the stationary distribution r == #
r = mc.stationary_distributions[0]
ranked_pages = {alphabet[i] : r[i] for i in range(n)}
# == Print solution, sorted from highest to lowest rank == #
print('Rankings\n ***')
for name, rank in sorted(ranked_pages.items(), key=itemgetter(1), reverse=1):
print('{0}: {1:.4}'.format(name, rank))
A solution from the quantecon library can be found here
In [7]: