# markov_chains.py
import numpy as np
def random_markov(n):
"""Create and return a transition matrix for a random Markov chain with
'n' states. This should be stored as an nxn NumPy array.
"""
arr = np.random.rand(n,n)
for i in range(n):
arr[:,i] = arr[:,i]/sum(arr[:,i])
return arr
def forecast(days):
"""Forecast tomorrow's weather given that today is hot."""
transition = np.array([[0.7, 0.6], [0.3, 0.4]])
weather = 0
li = []
# Sample from a binomial distribution to choose a new state.
for i in range(days):
weather = np.random.binomial(1,transition[1,weather])
li.append(weather)
return li
def four_state_forecast(days):
"""Run a simulation for the weather over the specified number of days,
with mild as the starting state, using the four-state Markov chain.
Return a list containing the day-by-day results, not including the
starting day.
Examples:
>>> four_state_forecast(3)
[0, 1, 3]
>>> four_state_forecast(5)
[2, 1, 2, 1, 1]
"""
li = []
weather = 1
transition = np.array([[0.5,0.3,0.1,0.0],[0.3,0.3,0.3,0.3],[0.2,0.3,0.4,0.5],[0.0,0.1,0.2,0.2]])
for i in range(days):
weather = np.random.multinomial(1, transition[:,weather])
for j in range(len(weather)):
if weather[j] == 1:
weather = j
break
li.append(weather)
return li
def steady_state(A, tol=1e-12, N=40):
"""Compute the steady state of the transition matrix A.
Inputs:
A ((n,n) ndarray): A column-stochastic transition matrix.
tol (float): The convergence tolerance.
N (int): The maximum number of iterations to compute.
Raises:
ValueError: if the iteration does not converge within N steps.
Returns:
x ((n,) ndarray): The steady state distribution vector of A.
"""
n,n = np.shape(A)
x = np.random.rand(n)
x /= sum(x)
x_next = np.zeros(n)
for i in xrange(N):
x_prev = np.copy(x_next)
x_next = np.dot(np.linalg.matrix_power(A,i), x)
if np.allclose(x_next, x_prev,tol):
return x_next
raise ValueError("A does not converge")
class SentenceGenerator(object):
"""Markov chain creator for simulating bad English.
Attributes:
(what attributes do you need to keep track of?)
Example:
>>> yoda = SentenceGenerator("Yoda.txt")
>>> print yoda.babble()
The dark side of loss is a path as one with you.
"""
def __init__(self, filename):
"""Read the specified file and build a transition matrix from its
contents. You may assume that the file has one complete sentence
written on each line.
"""
words = set()
my_file = open(filename)
for word in my_file.read().split():
words.add(word)
word_count = len(words)
self.word_count = word_count
matrix = np.zeros((word_count+2, word_count+2))
states = ["$tart"]
my_file.close()
visited = set()
with open(filename) as f:
lines = f.readlines()
for line in lines:
words = line.split()
for i in xrange(len(words)):
if words[i] not in visited:
states.append(words[i])
visited.add(words[i])
index = states.index(words[i])
if i == 0:
matrix[index][0] += 1
for i in xrange(len(words)):
index = states.index(words[i])
if i != len(words) -1:
y_index = states.index(words[i+1])
else:
y_index = word_count+1
matrix[y_index][index] += 1
for column in range(0,word_count+1):
div = sum(matrix[:,column])
if div != 0:
matrix[:,column] /= div
self.transition = matrix
states.append("$top")
self.states = states
def babble(self):
"""Begin at the start sate and use the strategy from
four_state_forecast() to transition through the Markov chain.
Keep track of the path through the chain and the corresponding words.
When the stop state is reached, stop transitioning and terminate the
sentence. Return the resulting sentence as a single string.
"""
states = []
current_state = 0
count = 1
babble_str = ""
while current_state != (len(self.states)-1):
states.append(current_state)
next = np.random.multinomial(1, self.transition[:,current_state])
for i in range(len(next)):
if next[i] == 1:
current_state = i
count += 1
if count == 1000:
break
for state in states:
if self.states[state] != "$tart":
babble_str += str(self.states[state]) + " "
return babble_str
if __name__ == "__main__":
sg = SentenceGenerator("tswift1989.txt")
print sg.babble()