Taking A random walk in a city -- but will I get back home?

Marek R. Rychlik

A sample problem

Imagine that you are stranded in an infinite city, in which streets and avenues run from the south to the north, and from the west to the east, and are separated by a distance of one mile. Let us assume that the streets and avenues are numbered by integers, both positive and negative, and that you live at the intersetion of 0th Avenue and 0th Street.

Suppose that you want to take walk in the city. That is a random walk. Every time you are at the intersection you are going to toss a coin twice, to determine which of the four possible directions to take.

Assume that you walk 1 mile a minute.

Here are the questions?

1. What is the probability that you will be home in not more than 10 minutes?
2. How long on the average will it take you to get back home, i.e. to the intersection of 0th Avenue with 0th Street?

Mathematical formulation

Let your current position be $(x_n,y_n)$ where $x_n$ and $y_n$ are the number of the avenue and the street that you are on after $n$ minutes of walking. Now you need to draw two numbers, $u_n$ and $v_n$ from the set $\{-1,1\}$ with replacement (i.e. after you have drawn a number, you immediately put it back in the set). Obriously, the situation in the problem can be modelled by the following system of difference equations:

$$x_{n+1} = x_n+u_n,$$

$$y_{n+1} = y_n+v_n.$$

Now, suppose that you have created a random sequence of $n$ pairs $(x_k,y_k)$, $k=0, 1, 2, \ldots, n$. If for some $k\le n$ both $x_n$ and $y_n$ are zero then obviously you returned home in $n$ minutes. Compute the probability of returning home in exactly $n$ minutes as follows.

First, fix two numbers $n$ (the length of sequence) and $l$ (the number of runs). In each run, classify the sequences by the minimal value of $k$ for which $x_k=y_k=0$. Let $p_k^l$ be the number of such sequences divided by $l$. Ideally, you would define the probability of returning in $k$ minutes as:

$$p_k = \lim_{l\to\infty}p_k^l.$$

The average time of returning home is:

$$T = \sum_{n=0}^\infty k \cdot p_k.$$ (1)

About this document ...

Taking A random walk in a city -- but will I get back home?

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 randomwalk.tex

The translation was initiated by Marek Rychlik on 2003-09-26