A mathematical saying goes, "a drunk man will find his way home, but a drunk bird may get
lost forever."
The assumption here is that because both are drunk, they are doing random walks.
The difference is that the man can only walk on the surface of the earth, and so he is
doing a 2-dimensional random walk; but for the bird, in addition to the two dimensions,
it can also fly up and down, and so it is doing a 3D random walk.
It turns out that no matter where the drunk man started, it is mathematically guaranteed
that he will return home - it’s only sooner or later; but for the bird, there is a nonzero
chance that it will get lost forever, even if it started off in its own nest.
Why is there such a stark difference between a 2D and a 3D random walk?
To answer this question, we use the framework of Markov chains.
[CHAPTER 1: MARKOV CHAINS]
A Markov chain consists of three things.
The first is the state space, essentially meaning where you can go.
In the case of random walks, for simplicity, the state space would be just those lattice
points, so the drunk man or bird can only visit those lattice points.
Second thing is the transition probabilities, because Markov chains are not static.
Let’s say you are now at state A, with four other neighbouring states in the state space.
In your next step, you can transition to any other states, and in general, you might also
go back to itself, depending on your setup.
For each possible transition, we just assign a probability to it.
They are the transition probabilities.
For a 2D random walk, each “state” has four neighbours, and because we have no bias
towards any direction, the transition probabilities are all 1/4.
Similarly, for a 3D random walk, each “state” has six neighbours, and so the transition
probabilities are all 1/6.
The final thing is the initial distribution.
In a general Markov chain, you have the freedom to choose which state to start, and so we
can assign a probability to each state, indicating how likely you are to start at that state.
In the case of a random walk, we want to definitively start at the origin, i.e. a probability 1
of starting at the origin, and 0 everywhere else.
Wait, didn’t you say it doesn’t matter where you started for the 2D case?
Don’t worry, I will get there in a minute.
These are the three elements in a Markov chain.
But there is one key feature that makes it a Markov chain - the Markov property.
This is the simple idea that once you have gone to a particular state, you should have
already forgotten **how** you get there, and consider the transition probabilities from
there, without caring about the route that takes you there.
So yes, that’s the whole setup for a Markov chain, but how does that help?
[CHAPTER 2: RECURRENCE AND TRANSIENCE]
Given that a random walk is random, and every time you run it, it gives different results,
what can we say about that?
One thing we can say is whether you will revisit the origin if you started there.
If you are guaranteed to go back, or in other words, the return probability is 1, then we
call that initial state recurrent.
If not, then you are not guaranteed to return, and so the return probability is less than
1.
In such a case, we call it a transient state.
Because you are either guaranteed or not guaranteed to return, a state is either recurrent or
transient.
There is no third option.
It turns out that in 2D, the origin is a recurrent state, and just because this state is recurrent,
we can already infer that it does not matter where the drunk man started, he will go back
to the origin.
That takes one or two lines of reasoning, which I encourage you to do in the comments.
On the other hand, the origin in the 3D random walk is a transient state, so the drunk bird
may never return.
The problem now is how to determine that return probability.
Here is the trick.
We consider a quantity V, which is the number of returns to the origin.
The implicit assumption is to run the random walk to infinity, even if you have returned.
Our focus is the expectation of V, i.e. the expected number of returns.
Now for the recurrent case, we are guaranteed to go back.
But if we continue to run the random walk, by the Markov property, we should have forgotten
that we have returned, and then we will, for sure, return to the origin again, and again.
So the number of returns V is guaranteed to be infinite.
And the expectation would also be infinite.
That is when the state is recurrent.
What if the state is transient?
Here is a very clever general trick.
By definition, the expectation is 0 times the probability that V is 0, plus 1 times
the probability that V is 1 and so on.
But what if we write, for instance, this 2 times probability as actually the sum of two
copies?
And also do this similarly for the other terms in this sum?
Then, instead of summing these row by row, we can sum these column by column.
For the first column, it is exactly the probability that V is at least 1.
Similarly, the next column gives the probability that V is at least 2, and so on.
The reason this method is useful is that if V is at least 1, that exactly means you return
to the origin at some point, and so this is actually the return probability, and for simplicity,
we denote it as r.
What about the probability of returning at least twice?
Well, the probability that you will return is r, but again by the Markov property, you
should forget that you have returned, and so the probability you return *again* is to
multiply by another r, and in general, the probability of returning at least k times
is r^k.
So if we go back to the expectation, each column actually sums up to a power of r, and
the expectation is a geometric series.
So we know what this should sum to, if that return probability is less than 1, which is
precisely the case when the state is transient.
For now, we only need to know that this is finite if r is less than 1.
However, we have also deduced that for a recurrent state, this expected number of returns is
infinite.
So if the state is recurrent, we have the expectation to be infinite; and if the state
is transient, the expectation is finite.
Because a state is either recurrent or transient, no third option, if, say, the expectation
is infinite, the state could not possibly have been transient, and so we can infer that
the state is recurrent.
So if we know whether this expectation is infinite, we are done.
To do that, we need a final trick.
Another way of thinking about V, the number of returns, is that it is a tally.
We first ask the questions “have you returned at step n?”
If yes, then we add 1 to the tally, and if not, then we don’t do anything to it.
Once we answered all these questions, we add up the total, and we obtain V by just adding
up all these +1’s.
If we are asking for the *expected value* of V, we add up the *expected value* of the
first question, the *expected value* of the second question, and so on.
The expected value of these yes-no questions are much easier to handle.
The expected value of this question would be by definition 1 times the probability that
you answer yes, plus 0 times that you answer no.
Well, that’s just the probability that you answer yes.
We usually denote this probability as p with subscript 0,0, and superscript 1.
The double 0 denotes going from the origin to the origin, i.e. revisiting the origin;
and the superscript just represents at which step you revisit.
These probabilities will be the expected value for each question, and the sum of these probabilities
gives us the expected value of V. So we now have a way of explicitly computing the expected
value of V. Previously, we deduced that we can simply use the expected value of V to
infer whether the state is recurrent, and now we also know how to explicitly compute
the expected value.
So once we know whether this series converges, then we know whether the state is recurrent
or transient.
This whole argument actually works for all Markov chains, including the random walk we
are considering.
[CHAPTER 3: BACK TO RANDOM WALKS]
In the previous chapter, we essentially devised a test for recurrence or transience.
A 2D random walk is recurrent, so we want to prove that the series diverges; a 3D random
walk is transient, so we want to prove that it converges.
But whichever the case, we need to compute each term.
In the case of a random walk, you can’t possibly go back to the origin after 1 step,
and so this probability is 0.
This should not be too surprising, because any return paths would have the same number
of steps to the left as those to the right; and of course, same number of steps downwards
as those upwards, and so the total number of steps here has to be even.
So this n-th step probability is 0 if n is odd, and so we can just focus on finding the
even (2n)-th step probabilities.
Let’s say we want a total of 18 steps, then this is a specific possible return path.
This specific path has a probability of (1/4)^(18), because each step is chosen with probability
1/4, and there are 18 steps you need to take.
Of course, this is not the only possible path that returns to the origin after 18 steps.
This one also does.
Even though it has returned to the origin already, as long as you return at step 18,
it still counts, because you will still answer yes in the previous argument.
Anyway, the new path also has probability (1/4)^(18).
More explicitly, when calculating the 18-th step return probability, we just add up these
probabilities.
This part is the probability of getting a specific return path, and we then multiply
by the number of return paths to get the overall probability.
So it all boils down to counting the number of return paths.
For a total of 2n steps, a return path should have the same number of steps to the left
and to the right, and the number of steps upwards is the same as downwards.
Because the total number of steps is 2n, we can express j in terms of i.
For a return path, we can imagine it as a sequence of moves.
Because there are a total of 2n steps, in total there are (2n)! arrangements of these
moves.
However, if, for example, we just rearrange these two left moves, then the resulting path
quite literally hasn’t changed, yet it counted as different in those (2n)! arrangements.
Because there are i steps to the left, there are i!
different permutations in between them.
And of course, the other directions have similar results.
These inter-permutations all counted as different in those (2n)! arrangements, yet they should
have been counted the same, and so the number of return paths for a fixed value of i is
(2n)! divided by all these factorials.
So given a value of i, this is the number, and i can range from 0 to n, and so the final
*total* number of return paths needs to add these up for i ranging from 0 to n.
Finally, this (2n)-th step return probability is (1/4)^(2n) times the total number of return
paths.
That’s just the case in 2D.
What about the 3D random walk?
The only difference is the transition probabilities are all 1/6, and there is one more pair of
directions to consider.
So the (2n)-th step probabilities would be replacing 1/4 by 1/6.
And for the number of return paths, we use a similar method, with the only difference
being there are 3 pairs of directions now.
So similarly, for fixed values of i and j, this is the number of return paths, and adding
all these for i and j ranging from 0 to n will give the total number of return paths,
and finally, for the (2n)-th step return probability, we simply multiply by (1/6)^(2n).
But perhaps it might be useful to remind ourselves why we care about this.
We have demonstrated that a state being recurrent or transient implies whether the series diverges
or converges, so by knowing whether this series converges, we know whether the state is transient.
In this chapter, we calculated those terms in the series, with explicit expressions for
the 2D and 3D cases respectively.
And what remains is to show that the series formed by the 2D case diverges, and the 3D
case converges.
The very quick reason for it is that each term here scales like 1/n.
So it diverges, because the harmonic series diverges; and the other term would scale like
1/n^(3/2), and this will lead to a convergent series instead.
Originally I wanted to make it into the main video, but this is a bit too much manipulation
of expressions, and so I ended up making it a second channel video.
But I want to give a bit more no-calculation explanation here.
We can always think of an inner and an outer region in any dimension, but in higher dimensions,
there is much more space in the outer region, so once you have gone out, it will be less
likely for you to go back in higher dimensions.
The exact cutoff turns out to be between 2 and 3 dimensions.
However, does this inner-outer region explanation, and the cutoff between 2 and 3 dimensions
look familiar?
If you have watched my previous video on Stein’s paradox, then you might remember that whether
the ordinary estimator is admissible has a cutoff between 2 and 3 dimensions, and we
found out that recurrence of random walks also has the same cutoff.
It turns out that this is NOT a coincidence.
Larry Brown wrote in 1971 about the connection between these two problems, but this is way
too involved (to be put) in a YouTube video.
I will put a link in the description for those who want to know more.
Before you go, I just want to thank you for your support, because now I have 100k subs!
To celebrate this milestone, I am going to make a Q&A video.
You can ask me any question, but do so in the Google form below.
And just so you are prepared for the next video, and you might have also guessed from
these two videos, I am currently a 4th year Cambridge maths student.
We call ourselves mathmos, for some unknown reason.
So yes, be prepared for some Cambridge-related math video in the future.
Please consider giving on Patreon, and thanks to the patrons for making this video possible.
As always, subscribe with the bell on, like, comment and share this video.
See you next time!