Project: Random Walk
DUE: November 22nd, 2000.
Please solve the following questions:
  1. Give a precise definition of a Random walk on $ {\mathbb{Z}}$ and $ {\mathbb{Z}}^2.$ When is this Random walk called a simple random walk.
  2. Let $ S_n$ be a simple random walk on $ {\mathbb{Z}}$. Let $ n>0$ and $ z$ be an integers.
    1. A path from the origin to the point $ (n,z)$ is a polygonal line whose vertices have abscissas (first-coordinate) $ 0,1, \ldots, n$ and ordinates (second-coordinate) $ 0,s_1,s_2, \ldots, s_n$ satisfying $ s_k -s_{k-1}= x_k =\stackrel{+}{-}1, k = 1,...,n$ with $ s_n =z$ $ n$ will be called the length of the path. Let $ p$ among the $ x_k$ be positive and $ q$ among them be negative.
      1. Write an expression for $ n$ and $ z$ in terms of $ p$ and $ q$ ?
      2. Let $ N_{n,z}$ denote the number of different paths from the origin to an arbitrary point $ (n,z).$ Write an expression for $ n$ and $ z$ in terms of $ p$ and $ q.$
    2. (Reflection principle) Let $ x,n$ be positive integers and $ p$ be any real number. Show that the number of paths from $ A(0,x)$ to some point $ B(n,p)$ which touch or cross the $ x-axis$ equals the number of all paths from $ A^{\prime}(0,-x)$ to $ B$.
    3. Let $ n,x$ be positive integers. There are exactly $ \frac {xN_{n,x}}{n}$ paths $ (0,s_1,s_2, \ldots,s_n=x)$ from the origin to the point $ (n,x)$ such that $ s_1 >0, \ldots, s_n >0.$
    4. (Ballot Theorem) Suppose that, in a ballot, candidate $ P$ scores $ p$ votes and candidate $ Q$ scores $ q$ votes, where $ p>q$. The probability that throughout the counting there are always more votes for $ P$ than for $ Q$ equals $ \frac {p-q}{p+q}.$


http://www.math.ubc.ca/~athreya/302/projects/Randomwalkq/index.html
[Math 302 -Projects page] [Math 302 page] [Comment on page design]