Learn & Review: Stochastic Processes I Learn with Asksia AI

Introduction to Stochastic Processes

This lecture introduces the concept of stochastic processes, which are collections of random variables indexed by time. The focus is on discrete-time stochastic processes, where the time variable progresses in distinct steps.

Defining Stochastic Processes

• Definition 1: Collection of Random Variables: A stochastic process can be viewed as a sequence of random variables, $X_0, X_1, X_2, \dots$, indexed by time.

  • Discrete Time: The index set is discrete (e.g., $0, 1, 2, \dots$).
  • Continuous Time: The index set is continuous (e.g., all non-negative real numbers).
  • A realization or path of a stochastic process is one specific sequence of outcomes.

• Definition 2: Probability Distribution over Paths: An alternative, more formal definition views a stochastic process as a probability distribution over a space of possible paths. This perspective is often more useful for mathematical analysis.

Examples of Stochastic Processes

Three examples illustrate different types of dependencies and randomness:

1. Deterministic Process: $f(t) = t$ with probability 1. This is not a stochastic process as there is no randomness.
2. Dependent Random Paths: $f(t) = t$ with probability 0.5, or $f(t) = -t$ with probability 0.5. Here, the choice of path is made once, and all values of $f(t)$ for different $t$ are determined by that initial choice. If $f(t) = t$, then $f(1)=1, f(2)=2$, etc. If $f(t) = -t$, then $f(1)=-1, f(2)=-2$, etc.
3. Independent Random Values at Each Time: For each $t$, $f(t) = t$ with probability 0.5, or $f(t) = -t$ with probability 0.5. At each time point $t$, the value is randomly chosen to be $t$ or $-t$, independently of other time points. This can lead to paths that "bounce back and forth."

The lecture emphasizes that understanding the dependencies and how the past influences the future is crucial when modeling real-world phenomena like stock prices.

Types of Questions in Stochastic Process Study

1. Dependencies: Analyzing how past values influence future values (e.g., stock price prediction).
2. Long-Term Behavior: Studying the behavior of the process as time goes to infinity (related to concepts like the Law of Large Numbers and Central Limit Theorem).
3. Boundary Events: Investigating the frequency of extreme events (e.g., how often a stock price drops by a certain percentage).

Discrete Time Stochastic Processes

The course will focus on discrete-time processes, with a transition to continuous-time processes later.

Simple Random Walk

A fundamental discrete-time stochastic process is the simple random walk.

• Definition:

  • Let $Y_i$ be independent and identically distributed (IID) random variables taking values $+1$ or $-1$, each with probability $1/2$.
  • Define $X_0 = 0$.
  • For $t \ge 1$, $X_t = \sum_{i=1}^{t} Y_i$.
  • The sequence $X_0, X_1, X_2, \dots$ is called a one-dimensional simple random walk.

• Properties and Behavior:

  • Visualization: The process can be visualized as a path on a line, starting at 0, and at each step moving up or down by 1.
  • Central Limit Theorem Application: For large $t$, $X_t / \sqrt{t}$ approaches a normal distribution with mean 0 and variance 1. This implies that $X_t$ is distributed like a normal distribution with mean 0 and variance $t$. The walk tends to stay within the bounds of $-\sqrt{t}$ and $\sqrt{t}$.
  • Hitting Boundaries: The process is guaranteed to cross any horizontal line infinitely often as $t \to \infty$.
  • Key Properties:
    1. Expectation: $E[X_k] = 0$ for all $k$.
    2. Independent Increments: For non-overlapping time intervals $[t_i, t_{i+1}]$, the changes in the process ($X_{t_{i+1}} - X_{t_i}$) are mutually independent. This means the past movement doesn't influence future movements, given the current position.
    3. Stationarity: The distribution of $X_{t+h} - X_t$ is the same for any starting point $t$, as long as the interval length $h$ is constant.

• Gambling Example (First Passage Time):

  • Consider a game where a player bets $1 at each step, winning $1 with probability 0.5 (Heads) and losing $1 with probability 0.5 (Tails). The player's balance follows a simple random walk.
  • Stopping Condition 1: If the player stops when their balance reaches $100 or -$100, the probability of stopping at $100 is 0.5 due to symmetry.
  • Stopping Condition 2: If the player stops when their balance reaches $100 or -$50, the probability of stopping at $100 is $1/3$. This can be derived using a recursive formula based on the probability of hitting boundaries. The general formula for hitting $b$ before $-a$ starting from $k$ is $(k+a)/(b+a)$.

Markov Chains

A Markov chain is a type of stochastic process that satisfies the Markov property.

• Markov Property: The future state of the process depends only on the current state, not on the sequence of events that preceded it. Mathematically, for a discrete-time process: $P(X_{t+1} = s | X_t = x_t, X_{t-1} = x_{t-1}, \dots, X_0 = x_0) = P(X_{t+1} = s | X_t = x_t)$ The past history is irrelevant if the current state is known.

• Simple Random Walk as a Markov Chain: The simple random walk is a Markov chain because the next step ($+1$ or $-1$) only depends on the current position $X_t$.

• Transition Probability Matrix: For a Markov chain with a finite state space $S = {1, 2, \dots, m}$, the transition probability matrix $P$ is an $m \times m$ matrix where $P_{ij}$ is the probability of transitioning from state $i$ to state $j$ in one time step.

  • $P_{ij} = P(X_{t+1} = j | X_t = i)$.
  • The sum of probabilities in each row must be 1 ($\sum_{j \in S} P_{ij} = 1$).
  • The probability of transitioning from state $i$ to state $j$ in $k$ steps is given by the $(i, j)$ entry of the matrix $P^k$.

• Example: Machine State: A machine can be "working" or "broken."

  • If working: $P(\text{working tomorrow} | \text{working today}) = 0.99$, $P(\text{broken tomorrow} | \text{working today}) = 0.01$.
  • If broken: $P(\text{working tomorrow} | \text{broken today}) = 0.8$, $P(\text{broken tomorrow} | \text{broken today}) = 0.2$.
  • The transition matrix is: $$ P = \begin{pmatrix} 0.99 & 0.01 \ 0.8 & 0.2 \end{pmatrix} $$ (Assuming state 1 is "working" and state 2 is "broken").

• Stationary Distribution: For a finite Markov chain with positive transition probabilities, there exists a unique probability distribution $\pi = (\pi_1, \dots, \pi_m)$ such that if the system starts in this distribution, it remains in this distribution after any number of steps. This is found by solving $\pi P = \pi$. This vector $\pi$ represents the long-term behavior of the Markov chain. The Perron-Frobenius theorem guarantees the existence and uniqueness of such a distribution when all entries of $P$ are positive.

Martingales

A martingale is a stochastic process that models a "fair game."

• Definition: A stochastic process $X_t$ is a martingale if, for any time $t$: $E[X_{t+1} | X_t, X_{t-1}, \dots, X_0] = X_t$ This means the expected value of the next state, given all past and present states, is equal to the current state.

• Fair Game Interpretation: In expectation, a player's balance in a martingale process neither increases nor decreases.

• Examples:

  • Simple Random Walk: Is a martingale because $E[X_{t+1} | X_t, \dots] = E[X_t + Y_{t+1} | X_t, \dots] = X_t + E[Y_{t+1}] = X_t + 0 = X_t$.
  • Casino Games (e.g., Roulette): Are generally not martingales because the expected value of the player's balance is typically less than zero (the house has an edge).
  • Custom Process: A process defined by $X_0=1$ and $X_k = X_{k-1} \cdot Y_k$, where $Y_k$ is 2 with probability 1/3 and 1/2 with probability 2/3. $E[X_k | X_{k-1}, \dots] = X_{k-1} \cdot E[Y_k] = X_{k-1} \cdot (2 \cdot 1/3 + 1/2 \cdot 2/3) = X_{k-1} \cdot (2/3 + 1/3) = X_{k-1}$. This is a martingale.

• Relationship to Markov Chains: Simple random walk is both a Markov chain and a martingale. However, these are distinct concepts; some processes are one but not the other.

Optional Stopping Theorem

• Stopping Time: A random variable $\tau$ is a stopping time if the decision to stop at time $\tau$ depends only on the history of the process up to time $\tau$. Formally, for any $k$, the event ${\tau \le k}$ depends only on ${X_0, X_1, \dots, X_k}$.

  • Example: Stopping when the balance reaches $100 or -$50 is a stopping time. Stopping at the "first peak" is not a stopping time because deciding if it's a peak requires looking at the next value ($X_{t+1}$).

• Theorem Statement: If $X_t$ is a martingale and $\tau$ is a stopping time such that $E[\tau] < \infty$ and $E[|X_\tau|] < \infty$ (e.g., if there's a bound on how long you can play), then $E[X_\tau] = E[X_0]$.

• Corollary Application: For the game where the player stops at $100 or -$50, let $p$ be the probability of stopping at $100. The optional stopping theorem implies $E[X_\tau] = E[X_0] = 0$. Since $X_\tau$ is $100$ with probability $p$ and $-50$ with probability $1-p$, we have $100p + (-50)(1-p) = 0$, which yields $150p = 50$, so $p = 1/3$. This confirms the earlier calculation.

The lecture concludes by emphasizing that if a situation can be perfectly modeled by a martingale, one cannot expect to gain or lose money in expectation, regardless of strategy.