Complexity Explorer Santa Few Institute

Random Walks

Lead instructor:

Your progress is not being saved! Enroll now or log in to track your progress or submit homework.

6.1 First Passage Phenomena » Quiz Solutions

Question 1

Let $E_n$ denote the probability for a random walk that starts at site $n$ to reach $x=3$ without ever reaching $x=0$

Using the backward Kolmogorov approach, these exit probabilities obey the recursions:

$E_1= \tfrac{2}{3} E_2$

$E_2= \tfrac{1}{3}E_1+\tfrac{2}{3}$

Solving these two equations for the two unknowns gives $E_1=\frac{4}{7}$ and $E_2=\frac{6}{7}$.

Note that this problem can also be solved by enumerating all paths that take the walk from $x=1$ to $x=3$

This enumeration approach becomes impossibly complicated for long intervals, however, while the backward Kolmogorov approach works easily for an interval of any length.

 

Question 2

Let $t_n$ denote the average time for the random walk to exit the interval $[0,3]$ when the walk starts at site $n$.  Again using the backward Kolmogorov approach, these exit times obey the recursions 

$t_1= \tfrac{1}{2} +\tfrac{1}{2}(1+t_2)$

$t_2= \tfrac{1}{2} +\tfrac{1}{2}(1+t_1)$

Solving these two equations for the two unknowns gives $t_1=t_2=2$.

This problem can also be solved by enumerating all paths that take the walk from $x=1$ to either $x=0$ or $x=3$.  This enumeration becomes impossibly complicated for long intervals, however, while the backward Kolmogorov approach again works easily for an interval of any length.

 

Question 3

For the interval $[0,4]$ the backward Kolmogorov equations for the exit times are:

$t_1= \tfrac{1}{2} +\tfrac{1}{2}(1+t_2)$

$t_2= \tfrac{1}{2}(1+t_1) +\tfrac{1}{2}(1+t_3)$

$t_3= \tfrac{1}{2} +\tfrac{1}{2}(1+t_2)$

Solving these equations for the three unknowns gives $t_1=3$, $t_2=4$ and $t_3=3$.