Description of the simple symmetric random walk on Z often utilizes the imagery of a drunken man attempting to walk home. The idea is that the man starts at some initial location, call it 0, and then randomly moves forward or backwards; moving one step in either direction per time period.  So the man starts at location 0 and moves either to −1 or 1 in the first time period with equal probability of 1/2 (this equal probability of moving forward or backwards is what is meant by ”symmetric”).  Then, from this new location (for descriptions sake, say he moved to position 1 during the first time period) he moves to either 0 or 2, again with equal probability. Likewise from this new position (for descriptions sake, say he moved to position 2 during the second time period) he then moves to position 1 or 3 with equal probability in the third time period, and so on… The descriptive ’simple’ is meant to indicate that from any point in Z, the probability of moving forward and backwards is exactly the same as at any other point in Z.

Linked,  I show that given an infinite amount of time, the drunken man will not essentially go anywhere. That is, he will cross the origin, 0, an infinite number of times. It turns out that this is also the case in Z2, where the simple forward and backward motion of the Z case is augmented to the 2-dimensional situation of being able to move in 4 directions from any point each with equal probability of 1/4. However, interestingly the scenario in 3-dimensions (Z3) is different. In three dimensions, our drunken man may move any of 6 directions from any point (up, down, left, right, forward, backwards), each with equal probability of 1/6. Here, what we’ll show is that the man does indeed ’get somewhere’. That is, given an infinite amount of time, the man will cross the origin point only a finite number of times, which is to say that he’ll eventually wander off in a direction and never again return to his starting position.

Recurrence Of Simple Symmetric Random Walk

The OST says that given a finite amount of money and a finite time horizon, any betting sequence/strategy cannot improve the expected earnings from a sequence of fair gambles.  More to the point, the theorem is proof that you can’t expect to make money playing a fair game (a martingale) and you can’t bet in such a way that you can expect to beat an unfair game (a supermartingale).  Attached, I’ve written a rundown of the result along with a nice short proof.

The Optional Stopping/Sampling Theorem

Stochastic Process, Optional Stopping Theorem, Expected Value, Conditional Expectation, Martingale