In this post, we consider one-dimensional random walks:
assume that is a random walk on the integers with
initial value , where are independent and
identically distributed random variables.
For termination analysis, we introduce a stopping time: a nonnegative
integer-valued random variable such that for every integer , the
indicator function of the event is a function of
.
Symmetric Random Walk
For each , we consider
.
Symmetric random walks are known to be recurrent, i.e., with probability
one, any state is visited infinitely often.
Let us consider the case where the random walk terminates when it reaches the
level , i.e., , and is
clearly a stopping time.
How do we establish the recurrence property for , i.e., ?
Moreover, what can we say about ?
One method is to derive ‘s probability generating function,
which is defined for all real values of less than in absolute value.
The strategy for the derivation is to condition on the first step of the random
walk to obtain a functional equation for ; there are two possibilities:
if , then and ; or
if , then , and the random walk must first return to the
origin, and the amount of time it takes to reach starting from has the
same distribution as—and is conditionally independent of— itself (i.e.,
the amount of time to reach from ).
Thus, .
This is a functional equation, whose solution is .
Moreover, observing that takes values between 0 and 1 when ,
we obtain the unique solution .
Then, by the monotone convergence theorem, we have
Similarly, noting that ,
we can express as .
Because ,
we have , i.e., the expected termination time is infinity.
Gambler’s Ruin
Let us consider another termination criterion for symmetric random walks:
it is set up so that Alice and Bob bet one dollar against each other on the
results of a fair coin flip until one play runs out of money. Suppose that Alice
starts with dollars and Bob starts with dollars.
We define a termination time to model the gamble:
, which is clearly a stopping time.
By a similar argument, we can show both
where ,
and where .
Thus, we know that as .
But what about in this case?
We use another technique called Wald identities, two of which have the form below
in a random-walk setting:
If the step distribution has a finite first moment and the stopping
time has a finite expectation, then .
If the step distribution has a finite second moment and the stopping
time has a finite expectation, then .
Let us assume first.
By the definition of , we know that and .
By the first Wald identity, we have .
The random variable takes only two values, and , with probabilities
and such that .
By the second Wald identity, we know that .
Thus, we can compute from ‘s distribution:
.
To show at the first place, we observe that if at any
time during the gamble Alice wins consecutive rounds, then Bob must run out
of money and the gamble must terminate. Thus,
and .
Asymmetric Random Walk (Uneven Steps)
For each , we consider
.
For the termination criterion, we define for any positive integer .
Let us fixed an and write .
This time, we do not argue that , but reason about directly.
We want to construct a martingale,
which is adapted to , as follows:
We can verify the martingale property by
Then the stopped process is a nonnegative
martingale, because .
Therefore, by Doob’s martingale convergence theorem,
is almost-surely well-defined and .
On the other hand, the random variable takes only two values, and , so
we have , thus .
To obtain an exact result for , we can reason about the distribution
of (via recurrence solving) and apply the first Wald identity.
The result is .
Asymmetric Random Walk (Uneven Probabilities)
For each , we consider
.
For the termination criterion, we define for any positive integer .
This time, we want to reason about both and .
We can use the techniques in previous sections to derive that
and .
For second (or even higher) moments, we can again use probability generating functions
.
Observing that a random walk with the target level can be decomposed into
independent random walks that reach starting from ,
we have .
We follow the strategy that conditions on the first step of the random walk to obtain
a functional equation for ; there are two possibilities:
if , then and ; or
if , then and the problem can be reduced to reaching starting from .
Thus, .
The solution is .
Again, because takes values between 0 and 1 when , we obtain the unique solution
.
Let us write .
By the property of probability generating functions, we have .
Therefore, .
What’s More
In our paper, we present a systematic and automated
framework for upper- and lower-bounding higher moments of cost accumulators (e.g., termination time)
in probabilistic programs (e.g., random walks).