Complexity Explorer

✓

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$ .

Complexity Explorer Santa Fe Institute

Random Walks