A drunkard stands at some integer on a number line. At each step he moves
either left or right to the adjacent number. He chooses the left
or right with equal probability.
Let $S_n$ be his position after $n$ steps,
for $n=0,...,10.$ We may draw a graph of $S_n$
versus $n$ using a zigzag line like the one shown below.
Random walk
The asp=1 in the plot command
keeps the plot area aspect ratio equal to 1, i.e., a
square. The abline command draws a horizontal line
through 0.
x = sample(c(-1,1), 100, rep=T)
plot(cumsum(x),ylab='random walk', xlab='time', ty='l',asp=1)
abline(h=0)
Share market values show such behaviour.
Clearly, there are $2^{10}$ such possible paths. Since the
man is a drunkard we assume that all these are equally likely.
EXAMPLE:
Find the probability that he ends up at his starting position
after 10 steps.
SOLUTION:
It is the
total number of paths from $(0,0)$ to $(10,0)$ divided
by $2^{10}.$ Now, each such path must have the same number
of up's and down's. So the number is $\binom{10}{5}.$
EXERCISE:Find the probability that the drunkard ends up at any given
$k\in{\mathbb Z}$ in exactly $n$ steps.
Clearly, the total number of paths from $(a,p)$
to $(b,q)$ is $N_{b-a,q-p}.$
EXAMPLE:
Consider all paths of length $2n$ starting from $(0,0).$
What is the probability that the path returns
to $0$ at time $2n$?
SOLUTION:
There are $2^{2n}$ paths, all equally likely. So $|\Omega| =
2^{2n}.$
Let $A$ be the event that the path ends at $(2n,0).$
Then $|A| = N_{2n,0}.$
So $P(A) = \frac{|A|}{|\Omega|} =
\frac{N_{2n,0}}{2^{2n}}.
$
EXERCISE:
Find the numerical value of the probability you found in the
above example for $n=5.$ Check it by running the following
code:
event = c()
for(k in 1:5000) {
x = sample(c(-1,1), 10, rep=T)
event[k] = (sum(x)==0)
}
mean(event)
Proof:
Keep an eye on this picture while reading the proof:
Reflection principle
Let $S$ be the set of all paths from $\alpha $
to $\beta $ that meets $L.$
Let $T$ be the set of all paths from $\alpha'$
to $\beta.$
Shall show that $|S|=|T|.$
Enough to show that there is a bijection from $f:S\rightarrow T.$
Step 1: Constructing $f$:
Take any path $p\in S.$ Let $\gamma$ be the first point where the
path meets $L.$ Reflect along $L$ the part of the path
between $\alpha$ and $\gamma.$ This will give a path
from $\alpha'$ to $\beta.$ Define $f(p)$ to be
this path.
Step 2: Showing onto:
Take any $q\in T.$ Since $\alpha'$ and $\beta$ are
on opposite sides of $L,$ so the path must
intersect $L$ some time or other.
(Actually this needs a little proof.)
Let $M$ be the set of all points on $q$ that are
below $L.$
Clearly, $M$ is finite (since $q$ has
finite length).
Also $M\neq \phi,$ since $\alpha'\in M.$
Let the
maximum time coordinate be $k$ among all the points
in $M.$ (Well-defined, since $M$ is finite and nonempty).
Clearly, $k < $ the length of $q$ (since $\beta $
is above $L$).
Then $q$ must meet $L$ at time $k+1.$
Otherwise, at time $k+1,$ the path $q$ must
either be below $L$ (impossible, since $k$ was the maximum)
or be above $L$ (impossible, since then $q$ has to
move more than one step from time $k$ to $k+1.$)
Let $\gamma$ be the
first such point. Reflect the part of $q$ between $\alpha
'$ and $\gamma $ to get a path $p\in S.$
Clearly $f(p)=q.$
Step 3: Showing one-one:
Let $p_1,p_2\in S$ be such that $f(p_1)=f(p_2)=q,$
say. Shall
show that $p_1=p_2.$
Pick the first point $\gamma$ where $q$ meets $L.$
Then by property of $f$, the part of $q$
from $\gamma$ to $\beta$ is the same as the part
of $p_1$ from $\gamma$ to $\beta.$
Similarly, the part of $q$
from $\gamma$ to $\beta$ is the same as the part
of $p_2$ from $\gamma$ to $\beta.$
So $p_1$ matches $p_2$ between $\gamma $ and $\beta.$
Also, the part of $p_1$ from $\alpha$ to $\gamma$
is the reflection of the part of $q$ from $\alpha'$ to $\gamma.$
Similarly, the part of $p_2$ from $\alpha$ to $\gamma$
is the reflection of the part of $q$ from $\alpha'$ to $\gamma.$
So $p_1$ matches $p_2$ between $\alpha$ and $\gamma.$
Hence $p_1=p_2,$ as required.
[QED]
EXAMPLE:
Again take a horizontal line $L$ (at height $h$) and two
points $A:(a,p)$ and $B:(b,q)$ both above (not on)
$L.$ Here $a<b.$ How many paths are there
from $A$ to $B$ that does not meet $L?$
SOLUTION:
First count all paths from $A$ to $B.$ From it subtract
the number of paths that meet $L.$
Total number of paths from $A$ to $B$
is $N_{b-a,q-p}.$
The number of paths from $A$ to $B$ that
meet $L$ may be found using the reflection principle.
The reflection of $A$ along $L$ is at $A':(a,2h-p).$
So the required number is $N_{b-a,q-2h+p}.$
Hence the final answer is $N_{b-a,q-p}-N_{b-a,q-2h+p}.$
EXAMPLE:
How many paths are there from $(0,0)$ to $(10,3)$ that
are strictly positive at all times $>0?$
SOLUTION:
This is very similar to the exercise above (with $L$ given
by the horizontal line at height $0$), except that we start
on the line itself.
However, it is obvious that our path must go to $(1,1)$
after the first step. So the last exercise may be applied
between $A:(1,1)$ and $B:(10,3).$
Proof:
Such a path must either always be positive. Or always be
negative. Clearly, the number of all-positive paths is the same
as that of all-negative paths.
An all-positive path must visit $(1,1)$ immediately
after $(0,0).$ So enough to compute the number of
all-positive paths starting from $(1,1).$
Where can such a path end? It can end at $2r$ for
some $r\in\{1,...,n\}.$
By the reflection principle,
the total number of all-positive paths from $(1,1)$
to $(2n,2r)$ is the total number of $(1,1)\rightarrow(2n,2r)$ paths
minus the total number of $(1,-1)\rightarrow(2n,2r)$ paths, i.e.,
$N_{2n-1,2r-1}-N_{2n-1,2r+1}.$
So the total number of all-positive paths is the telescoping sum
$$
(N_{2n-1,1}-N_{2n-1,3}) +
(N_{2n-1,3}-N_{2n-1,5}) + \cdots + (N_{2n-1,2n-1}-N_{2n-1,2n+1})
= N_{2n-1,1}-N_{2n-1,2n+1} = N_{2n-1,1},
$$
since $N_{2n-1,2n+1}=0$ ($\because 2n+1 > 2n-1$).
Combining all-positive and all-negative paths, the total count is
$2N_{2n-1,1} =
2\binom{2n-1}{n}=\frac{2(2n-1)!}{(n-1)!n!} =\frac{(2n!)}{n!n!}
=\binom{2n}{n} = N_{2n,0}.$
[QED]
Proof:
Let $A$ be the set of all the paths that never return to 0.
Let $B$ be the set of all the paths that never return to
before or at time $2n-2.$ (We are always considering paths
of length $2n.$)
Then we want to find $|B\setminus A|.$
Since $A\subseteq B,$ this is $|B|-|A|.$
Now $|A| = N_{2n,0}$ by the No 0-return theorem.
Also, by the same theorem, $|B| = 2^2N_{2n-2,0}.$
(Why?)
By the No 0-return theorem, total number of paths
of length $2n-2$ that never returns to $0$
is $N_{2n-2,0}.$ Then we are free to choose the next two
steps (from time $2n-2$ to time $2n$), which may be
done in $2^2$ ways.
Hence the result.
[QED]
EXERCISE:
Consider all paths of length $2n$ starting at $(0,0).$
What is the number of these paths that return to $0$
at $2r$ for some given $r < n?$ Also, how many of these
return to 0 from the positive side?
The red dot shows the last 0 hit, which occurs at time $2k.$
We can choose the part before the red dot in $N_{2k,0}$ ways. Also
independently of that, we can choose the part after the red dot
in $N_{2n-2k,0}$ ways, by the no 0-return theorem. Hence the result.
[QED]
We shall now consider the amount of time a path spends in the
positive side.
For example, the following path spends 8 times units in the
positive sides.
EXAMPLE:
Draw a path of length 10 starting from $(0,0)$ that
spends exactly 5 time units in the positive side.
Impossible! Each $0$-hit occurs at even time points, and the
path ends at 10, which is also even.
Proof:
Let's warm up by looking at an example with $n=7$ and $k=4.$
First 0-return at $4$
We shall split the set of all such paths into some disjoint
subsets based on when the first 0-return occurs and from which
side. For example, in the above example, it occurs at 4,
and from the positive side. In general, here are
all the possible cases:
Different cases
Let's first deal with the red case (i.e., when the path never
returns to 0). Obviously, this situation can occur only
when $2k=0$ (the path is always below the $x$-axis) or
when $2k=2n$ (the path is always above the $x$-axis).
In both these cases the result follows immediately
from the No 0-return theorem.
Next let's consider the green case.
How many such
paths are possible such that the first 0-hit occurs at $2r$
from the positive side? The
answer is
#($2r$ length paths with first 0-hit from positive side at $2r$)$\times$ #($2n-2r$ length paths
with exactly $2k-2r$ positive segments).
Out of the two factors we already know a nice formula for the
first one from the First 0-return theorem.
Also, the
second factor is precisely of the type that we want to find in
this theorem. However, it is for a shorter path (length
being $2n-2r$ instead of $2n$). So induction on
path-length may help.
Notice that here $r\in\{1,...,k\}.$ (Otherwise, you get more
than $2k$ segments above the $x$-axis.)
Next look at the blue case.
How many such
paths are possible such that the first 0-hit occurs at $2r$
from the negative side? The
answer is
#($2r$ length paths with first 0-hit from negative side at $2r$)$\times$ #($2n-2r$ length paths
with exactly $2k$ positive segments).
Again, the first factor is tractable by the First 0-return
theorem, and the second factor may hopefully be dealt with by
induction.
Notice that here $r\in\{1,...,n-k\}.$ (Otherwise, you get less
than $2k$ segments above the $x$-axis.)
We shall use induction on $n\geq k.$ (Here we are
holding $k$ fixed.)
Basis: Here we consider $n=k,$ i.e., the case where
all the segments are above the $x$axis. We shall employ a
trick here. Shift the path by $(1,1).$ and
connect $(0,0)$ to $(1,1)$ The following diagrams would
help you to understand the transformation.
The original path
The transformed path (the extra segment shown
in red)
Notice that this gives a bijection between
the set of paths of length $2n$ where all the segments
are above the $x$-axis
the set of positive paths of length $2n+1$ that never return to 0.
Now the size of the
latter set is $N_{2n,0}$(Why?)
Since $2n+1$ is odd, so each element of this set is a
positive path that does not return to 0 up to and including
time $2n$, and then it is free to move wherever it wants at
time $2n+1$ (since it can never hit 0 at an odd time point).
So the size is $\frac 12\times N_{2n,0}\times 2.$
The $\frac 12$ because we are considering
only positive paths. The 2 because the path is free to
move from time $2n$ to $2n+1.$
, completing the proof of the basis.
Hypothesis: Assume the result for $n\in\{k,k+1,...,m-1\}$ for some $m> k.$
Step: Shall show for $n=m.$
Here the required number is
$\frac 12\sum_{r=1}^k$ #{$2r$ length paths with first 0-return at $2r$}$N_{2n-2k,0} N_{2k-2r,0}$
+$\frac 12\sum_{r=1}^{n-k}$ #{$2r$ length paths with
first 0-return at $2r$}$N_{2k,0} N_{2n-2k-2r,0}$
Take terms free of $r$ out of the summations:
$\frac 12N_{2n-2k,0}\sum_{r=1}^k$ #{$2r$ length paths with first 0-return at $2r$}$N_{2k-2r,0}$
+$\frac 12N_{2k,0}\sum_{r=1}^{n-k}$ #{$2r$ length paths with first 0-return at $2r$}$ N_{2n-2k-2r,0}$
The $r$-th sumand is (the number of $2r$ length paths
with first 0-return at $2r$) $\times$ (the number
of $2k-2r$ paths starting and finishing at height 0). This
product is the number of $2r+(2k-2r)=2k$ length paths
starting and ending at height 0 with
first 0-return at $2r.$
Since we are summing over all possible values of $r$, the
sum is the number of $2k$ length paths starting and ending
at height 0. This is precisely $N_{2k,0}.$
If this number is $M_r$ then our answer is $M_r-M_{r+1}.$
This is $N_{n,2r-k}$ by the reflection principle.
So the number of paths with maximum $r$ and ending
at $A$ is
$$
N_{n,2r-k} - N_{n,2(r+1)-k}.
$$
We shall now sum this over $k\leq r.$ Two points are to
be noted about this:
If $N_{n,2r-k}$ is denoted by $a_k,$ then we are
summing
$$
(a_r-a_{r-2}) + (a_{r-1}-a_{r-3}) + (a_{r-2}-a_{r-4}) + \cdots
$$
Notice the two-step telescoping structure: each negative term
cancels the positive term two steps ahead.
The sequence $(a_k)$ eventually becomes 0, as $k$
goes down.
So only the first two two terms survive, i.e., $a_r+a_{r-1}$
or $N_{n,r}+N_{n,r+1}.$
We know that $N_{a,b}$ is 0 if $a,b$ have opposite
parities. Hence the result.
[QED]
Proof:
Such a path must pass through $(n-1,r-1)$ and $(n,r).$
Also it must never meet the the line at height $r$ up to and
including time $n-1.$
By reflection principle the path up to time $n-1$ may be
chosen in $N_{n-1,r-1}-N_{n-1,r+1}$ ways. The step from
time $n-1$ to $n$ is forced (it has to move up).
Hence the result.
[QED]
(Ballot problem) two candidates are contesting in
a vote. There are $n$ voters who have cast their votes. The
votes are being counted with the $n$ ballot papers ordered
randomly.
Candidate $A$ has $p$ votes and
candidate $B$ gets $q=n-p (<p)$ votes. Show that the
probability that during the counting $A$ was always leading
is
$$
\frac{p-q}{p+q}.
$$
Let $a,b>0.$ Show that the number of paths from $(0,0)$ to $(n,a)$ that is
always $>-b$ is $N_{n,a}-N_{n,a+2b}.$
Let $b> a> 0.$ Show that the number of paths
from $(0,0)$ to $(n,a)$ that are
always $<b$ is $N_{n,a}-N_{n,2b-a}.$ (Thanks to
Aadrita for pointing out a mistake here, which I have now corrected).
Let $a>c>0$ and $b>0.$ Show that the number of
paths from $(0,0)$ which touch the
horizontal line at height $a$ and then lead to $(n,c)$
without having touched the horizontal line at height $-b$ is
$N_{n,2a-c}-N_{n,2a+2b+c}.$ (Note that the path may touch
the horizontal line at height $-b$ before hitting
the line at height $a.$)
Prove that there are as many paths from (0,0)
to $(2n+2,0)$ with all interior vertices $>0$ as there
are paths from (0,0) to $(2n,0)$ where all interior
vertices are $\geq 0.$
The probability that before time $2n$ there occur
exactly $r$ returns to the origin equals the probability
that a return occurs at time $2n$ is preceded by at
least $r$ returns.
Consider random paths of length $2n$ starting
from $(0,0).$ Let $k\in{\mathbb Z}.$ Consider the two events:
$A = $ the path passes through $(2n,0)$ and the maximum
height of the interior vertices is $\geq k.$
and
$B = $ the path passes through $(2n,2k).$
Show that $P(A) = P(B).$ [Thanks to Avinash for pointing out
a mistake in this problem, which is now corrected.]
Find the fallacy in the following argument:
Consider the set of all paths of length 10 starting
from $(0,0).$
Let $A = $set of paths that never return to 0.
Let $B = $set of paths that never return to 0 at or before time 8.
Now define $C_k$ as the set of all paths
that do not hit 0 at time $2k.$ Then $A = \cap_1^5 C_k$
while $B = \cap_1^4 C_k.$ So $|A|\leq |B|.$
Again, any path that has not hit 0 at or before time 8 can be
continued for two more time units without hitting
0. So $|B| \leq |A|.$
Hence $|A|=|B|.$
Comments
To post an anonymous comment, click on the "Name" field. This
will bring up an option saying "I'd rather post as a guest."
