## Random Walks

A *random walk* is a formalization of a discrete process wherein a random selection is made between two alternatives (often ±1) at fixed time intervals. There are several standard examples:

**Tossing a coin.**At times t = 1, 2, 3, ... a coin is tossed with two possible outcomes: H (heads) or T (tails).**A game of chance.**A repeatedly played game such that at each round a player may win or lose a fixed amount of money.**Ballot counting.**In an election with two candidates, a vote may go to either one or the other of the candidates.

The theory of random walks expands into a more general theory of *Markov chains* in which the random fluctuations need not be of fixed size.

In theory, each of the two possible outcomes turn up with fixed probabilities, say, p for one and q for the other so that

Formally speaking, a random walk is a sequence _{1}, S_{2}, ..., S_{n})_{k} that take on two values, say, ±1.

Random walks are naturally represented by a two-dimensional diagram as in the applet below. (By no means, this is the only possibility. Any configuration of Pascal's triangle will do as good a job as the one we chose here.)

From any given state

Every node of the walk corresponds to the accumulated value _{k} = S_{1} + S_{2} + ... + S_{k},

What if applet does not run? |

First let's count the number of ways to get from point

On the other hand, if point B is reachable from point A the numbers u and v, of upward and downward steps, are determined uniquely. The only distinction between different walks is in the sequencing of the upward and downward steps.

To simplify the notations, we seek the number of ways to get from

u + v | = N | |

u - v | = B |

from which u = (N + c)/2 and v = (N - c)/2. The number of ways to get from

The probability of getting from ^{u}q^{v}^{u} in the binomial expansion of ^{u + v}.^{u}q^{v}.

In particular, if B = (2w, 0), the probability of getting from ^{w}q^{w}.

### References

- W. Feller,
*An Introduction to Probability Theory and Its Applications*, Vol. 1, 3rd Edition, Wiley, 1968

### Pascal's Triangle and the Binomial Coefficients

- Binomial Theorem
- Arithmetic in Disguise
- Construction of Pascal's Triangle
- Dot Patterns, Pascal Triangle and Lucas Theorem
- Integer Iterations on a Circle
- Leibniz and Pascal Triangles
- Lucas' Theorem
- Lucas' Theorem II
- Patterns in Pascal's Triangle
- Random Walks
- Sierpinski Gasket and Tower of Hanoi
- Treatise on Arithmetical Triangle
- Ways To Count
- Another Binomial Identity with Proofs
- Vandermonde's Convolution Formula
- Counting Fat Sets
- e in the Pascal Triangle
- Catalan Numbers in Pascal's Triangle
- Sums of Binomial Reciprocals in Pascal's Triangle
- Squares in Pascal's Triangle
- Cubes in Pascal's Triangle
- Pi in Pascal's Triangle
- Pi in Pascal's Triangle via Triangular Numbers
- Ascending Bases and Exponents in Pascal's Triangle
- Determinants in Pascal's Triangle

|Activities| |Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2017 Alexander Bogomolny

62637483 |