Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 36 ยท Getting Started

States, Time and Sample Paths

Understand state spaces, index sets, sample paths, finite-dimensional distributions and information over time, with Python plots of random-walk paths.

Once you know that a stochastic process is a family , three questions come up at once. What values can the process take? How does time enter? And how do we describe the probability of a whole path, not just of one value at one time? This lesson answers all three.

State space and index set

The state space S is the set of possible values. It can be:

  • finite: {sunny, cloudy, rainy};
  • countably infinite: the non-negative integers, for a queue length;
  • continuous: the real line, for a temperature or a stock price.

The index set T is the set of times at which you look. We write X_n for discrete time (n = 0, 1, 2, ...) and X(t) or X_t for continuous time. Throughout this track, "chain" usually means discrete state, and "walk" usually means a process built from adding up steps.

Sample paths

A sample path is one complete history. For a random walk, where each step is +1 or -1 with probability 1/2, a path might start 0, 1, 0, -1, -2, -1, ....

Python Simulate a symmetric random walk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every path of this walk changes by exactly 1 at each step. That is a property of the paths, and it holds for all outcomes. Properties like this (continuity, monotonicity, jumps) matter a lot in continuous time, where they decide which questions even make sense.

Finite-dimensional distributions

You cannot list all paths: there are too many. Instead, a process is pinned down by the joint distributions of its values at finitely many times:

Text
P(X_(t1) = x1, X_(t2) = x2, ..., X_(tk) = xk)

These are the finite-dimensional distributions. If two processes have the same ones, they have the same law for all practical purposes in this course.

For the random walk above (starting at 0), take k = 2, t1 = 1, t2 = 2. The first step is +1 or -1, each with probability 1/2, and so is the second:

(X_1, X_2) probability
(1, 2) 1/4
(1, 0) 1/4
(-1, 0) 1/4
(-1, -2) 1/4
Python Check the joint distribution by simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Increments

The increment of a process between times s < t is X_t - X_s. Two properties of increments define important families:

  • independent increments: increments over non-overlapping time intervals are independent;
  • stationary increments: the distribution of X_(t+h) - X_t depends only on the length h, not on t.

The random walk has both: each step is a fresh independent coin flip. Later we will see that the Poisson process and Brownian motion do too, and that this is almost enough to characterize them.

Information over time: the history

At time n you know the past X_0, X_1, ..., X_n. This accumulated knowledge is called the history (formally a filtration). It grows with time: you never forget. Many key definitions are phrased with respect to it:

  • A Markov process says the future given the history depends only on the present state.
  • A martingale says the expected future value, given the history, equals the present value.

Both ideas are introduced properly later. Keep the picture in mind: a process is a story that is revealed one chapter at a time.

flowchart LR
    A["X_0"] --> B["X_1"] --> C["X_2"] --> D["X_3"]
    H1["history after time 1:<br/>X_0, X_1"] -.-> B
    H2["history after time 2:<br/>X_0, X_1, X_2"] -.-> C

The history grows as time moves forward.

Drawing many paths

A picture helps. This plot draws five independent random-walk paths. Notice how they start together but spread out over time: the typical distance from 0 grows like the square root of the number of steps.

Python Five random-walk paths

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When you see a plot of a stochastic process, remember it shows one sample path (or a handful). The process is the whole distribution over paths.

Check your understanding

Quick check ยท 3 questions

of 3 answered You scored / 3 ยท perfect!

  1. 1. What does a finite-dimensional distribution describe?

    It is P(X_t1 = x1, ..., X_tk = xk) for a finite list of times.
  2. 2. A process has stationary increments when...

    Stationary increments mean the increment distribution depends on the interval length only, not on where it sits.
  3. 3. In the symmetric random walk, what is P(X_1 = 1, X_2 = 2)?

    Both of the first two steps must be +1, so the probability is (1/2)(1/2) = 1/4.

Summary

  • The state space S holds the possible values; the index set T holds the times.
  • A sample path is one complete history; the process is the law over all paths.
  • Finite-dimensional distributions describe joint behavior at finitely many times.
  • Independent and stationary increments are structural properties used again and again.
  • The history grows with time; Markov and martingale properties are statements about it.

Next: Simulating Stochastic Processes in Python