Complexity Explorer

✓

4.1 Part I » Quiz Solutions

4.1 Q1

Consider a 10-step symmetric nearest-neighbor random walk in one dimension.

(a) What is the probability that the walk is at x=10?

$t = 10; d = 1; p_{r} = 1/2; p_{t} = 1/2; P\left ( x = 10, t = 10 \right ) ?$

$P\left ( x,t \right )\sim \frac{t!}{\left ( \frac{t + x}{2} \right )!\cdot \left ( \frac{t-x}{2} \right )!}\cdot \left ( p_{r} \right )^{t}$

$P\left ( x,t \right )\sim \frac{10!}{\left ( \frac{10 + 10}{2} \right )!\cdot \left ( \frac{10-10}{2} \right )!}\cdot \left ( \frac{1}{2} \right )^{10} = 1\cdot \left ( \frac{1}{2} \right )^{10} = 2^{-10}$

4.1 Q2

Consider a 10-step symmetric nearest-neighbor random walk in one dimension.

(b) What is the (approximate) probability that the walk is at the origin?

$t = 10; d = 1; p_{r} = 1/2; p_{t} = 1/2; P\left ( x = 0, t = 10 \right ) ?$

$P\left ( x,t \right )\sim \frac{10!}{\left ( \frac{10 + 0}{2} \right )!\cdot \left ( \frac{10-0}{2} \right )!}\cdot \left ( \frac{1}{2} \right )^{10} = \frac{3628800}{14400}\cdot \left ( \frac{1}{2} \right )^{10} = 0.24609$

4.1 Q3

(Harder) Consider a 6-step nearest-neighbor random walk in one dimension in which the
walk hops to the right with probability 2/3 and hops to the left with
probability 1/3.

(a) What is the probability that the walk is at x=6?

$t = 6; d = 1; p_{r} = 2/3; p_{t} = 1/3; P\left ( x = 6, t = 6 \right ) ?$

$P\left ( x,t \right )\sim \frac{6!}{\left ( \frac{6 + 6}{2} \right )!\cdot \left ( \frac{6-6}{2} \right )!}\cdot \left ( \frac{2}{3} \right )^{6} = 1\cdot \left ( \frac{2}{3} \right )^{6}$

4.1 Q4

(Harder) Consider a 6-step nearest-neighbor random walk in one dimension in which the
walk hops to the right with probability 2/3 and hops to the left with
probability 1/3.

(b) What is the (approximate) probability that the walk is at the origin?

$P\left ( x,t \right )\sim \frac{t!}{\left ( \frac{t + x}{2} \right )!\cdot \left ( \frac{t-x}{2} \right )!}\cdot \left ( p_{r} \right )^{3}\cdot \left ( p_{e} \right )^{3}$

$P\left ( x,t \right )\sim \frac{6!}{\left ( \frac{6 + 0}{2} \right )!\cdot \left ( \frac{6-0}{2} \right )!}\cdot \left ( \frac{2}{3} \right )^{3} \cdot \left ( \frac{1}{3} \right )^{3}= 0.2194$

Complexity Explorer Santa Few Institute

Random Walks