Theorem 2.1

Theorem2_1.py

import sys
import random
from numpy import *
import time

class Markov(object):
	def __init__(self, transition_matrix, start_state):
		self.P = transition_matrix
		self.state = start_state

	@classmethod
	def sample_from_distro(self, v):
		summation = 0
		uniform = random.random()
		for i in range(len(v)):
			summation += v[i]
			if summation > uniform:
				return i
		return null

	def take_step(self):
		self.state = self.sample_from_distro(self.P[self.state])

if __name__ == "__main__":
	start_state, num_experiments = int(sys.argv[1]), int(sys.argv[2])
	transition_matrix = [[1.0/3, 1.0/2, 1.0/6],
						 [3.0/4, 1.0/8, 1.0/8],
						 [98.0/100, 1.0/100, 1.0/100]]
	M = Markov(transition_matrix, start_state)

	avg_count = 0
	for i in range(num_experiments):
		count = 1
		M.take_step()

		while M.state != start_state:
			count += 1
			M.take_step()
		avg_count += count
	print (1.0 * avg_count)/num_experiments