Math 2.0

Probability theory and stochastic processes Definition

Random walk

Builds on Independent and identically distributed random variablesStochastic process

Definition

Let d≥1d \ge 1, let x0∈ℝdx_0 \in \mathbb{R}^d, and let ξ1,ξ2,…\xi_1, \xi_2, \dots be i.i.d. random vectors in ℝd\mathbb{R}^d. The random walk with start x0x_0 and steps ξi\xi_i is the stochastic process (Sn)n≥0(S_n)_{n \ge 0} with S0=x0andSn=x0+ξ1+⋯+ξnfor n≥1.S_0 = x_0 \quad \text{and} \quad S_n = x_0 + \xi_1 + \dots + \xi_n \quad \text{for } n \ge 1. The simple random walk on ℤ\mathbb{Z} has d=1d = 1, x0=0x_0 = 0 and P(ξi=1)=P(ξi=−1)=1/2P(\xi_i = 1) = P(\xi_i = -1) = 1/2.

Remarks

For the simple random walk on ℤ\mathbb{Z}, E[Sn]=0E[S_n] = 0 and Var⁡(Sn)=n\operatorname{Var}(S_n) = n. By the central limit theorem, Sn/nS_n/\sqrt{n} converges in distribution to 𝒩(0,1)\mathcal{N}(0, 1). The simple random walk on ℤd\mathbb{Z}^d returns to its start with probability 11 if d≤2d \le 2, and with probability less than 11 if d≥3d \ge 3. This is Pólya's theorem. A random walk is a Markov chain with transition probabilities that do not change under translation. After scaling of time and space, the simple random walk converges to the Wiener process.

Reading path

To understand this page from the ground up, read these 49 pages in order. The foundations come first.

  1. Construction of the reals from Cauchy sequences concept
  2. Element definition
  3. Integers object
  4. Ordered field definition
  5. Proposition concept
  6. Random experiment concept
  7. Rational numbers object
  8. Real numbers object
  9. Set definition
  10. Ring of integers statement
  11. Disjunction definition
  12. Implication definition
  13. Predicate definition
  14. Ordered pair definition
  15. Union definition
  16. Sample space definition
  17. The rationals form a field statement
  18. Existential quantifier definition
  19. Universal quantifier definition
  20. Cartesian product definition
  21. Subset definition
  22. The rationals form an ordered field statement
  23. Uniqueness quantifier definition
  24. Binary relation definition
  25. Universal set definition
  26. Order on the reals definition
  27. Power set definition
  28. Complement definition
  29. Function definition
  30. Interval definition
  31. Preimage of a set definition
  32. Sigma-algebra definition
  33. Event definition
  34. Borel sigma-algebra definition
  35. Probability axioms concept
  36. Probability measure definition
  37. Probability distribution definition
  38. Probability space definition
  39. Conditional probability definition
  40. Random variable definition
  41. Independence of two events definition
  42. Law of a random variable definition
  43. Stochastic process concept
  44. Mutual independence of events definition
  45. Identically distributed random variables definition
  46. Independent sigma-algebras definition
  47. Independence of random variables definition
  48. Independent and identically distributed random variables definition
  49. Random walk definition

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Random_walk, One-dimensional random walk
About this page
Tag0C08YMV95H
URIm2://0C08YMV95H
Kinddefinition
WritingW1 stated
MSC60G50
DefinesRandom walk
UsesIndependent and identically distributed random variables, Stochastic process

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by