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
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
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 + b)/2 and v = (N - b)/2. The number of ways to get from
The probability of getting from
In particular, if B = (2w, 0), the probability of getting from
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
- Tony Foster's Integer Powers in Pascal's Triangle
|Activities| |Contact| |Front page| |Contents| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny
71470866