Brownian Motion

Imagine that a pollen particle is suspended in a glass of water. If we were to observe and record the vertical position of the particle over time, we would find that its movements were random. And if we were to plot this position, we’d get a jagged path through time (Figure 11, left). This path would be just one of many possible paths, and if we were to repeat this observational experiment many times, we would not expect to see the same path again. Given this randomness, how can we reason about this phenomenon? Can we say anything interesting or useful about the particle? For most of human history, this was a seemingly impossible task. A key insight, a conceptual pillar in probability theory, is to separate what actually happened (Figure 11, left) from other possible outcomes (Figure 11, right). This approach allows us to reason about the world through counterfactuals: what are all the possible paths the pollen could have taken? How likely is each path? What can we say about the distribution of outcomes? Figure 1. Left. A single random path of a pollen particle's vertical position plotted against time. Right. Many such random paths, all starting at the same initial position. This understanding of the pollen particle as a random process is a deep idea, and it took many decades and scientists to understand. The phenomenon was first observed in the 1830s by the Scottish botanist Robert Brown. Brown used a microscope to observe pollen particles suspended in water, and to his surprise, he saw the particles moving! At first, he thought this meant that the pollen particles were alive, but he tested and then rejected this hypothesis by observing the same effect with particles that he was convinced were inanimate, such as glass powder, minerals, and even pulverized fragments of the Egyptian Sphinx (Góra, 2006)! For roughly half-a-century, the phenomenon remained a mystery, although it became known as Brownian motion. Then starting in 1905, Albert Einstein published a series of papers in which he hythesized that the pollen particles were moving because they were being bombarded by invisible molecules in the liquid (Einstein, 1905). In the following year, the Polish physicist Marian Smoluchowski independently published essentially the same theory (Von Smoluchowski, 1906). At the time, this theory was controversial, because the idea of molecules was not yet widely accepted. However, using statistical mechanics, Einstein and Smoluchowski were able to make testable predictions about the behavior of the particles, and another scientist, Jean Baptiste Perrin, verified the model a few years later (Perrin, 1909). And since Einstein’s breakthrough work, Brownian motion has been widely studied and more deeply understood. In the mathematical community, Brownian motion was formalized by Norbert Wiener (Wiener, 1923), and thus Brownian motion is often referred to as a Wiener process, particularly by mathematicians. The goal of this post is to better understand Brownian motion. Brownian motion is an important concept because it can be used to model many phenomenon, from particles suspended in liquids to the prices of stocks. Ultimately, we’ll reconstruct the marginal distribution of our pollen particle at any given point in time. As we will see this, this is the normal distribution. This deep connection means that we can make mathematically precise probabilistic statements about a completely random process. Random walks Let’s begin with a simplified model of our pollen particle in discrete time. This is a stochastic process called a random walk. In the next section, we’ll extend this to continuous time, which is Brownian motion. Imagine we can discretize time and then observe a single discrete “tick” on the clock. What happens to the pollen particle during this one tick? In our simple model of the world, we’re going to imagine that we flip a coin, not necessarily fair, and that the pollen particle moves up or down the same amount based on the outcome of that coin toss. The coin toss models the fact that the pollen particle is being randomly bombarded by water molecules and thus its position at the next time point is random. So the pollen particle cannot stay in place; after one tick of the clock, it moves up or down. Formally, let S0S_0 be the particle’s initial position (non-random), and let S1S_1 be a univariate random variable denoting the vertical position of the pollen particle after one tick. We assume that the initial position is zero (S0=0S_0 = 0), since this makes our calculations and notation easier and since it is simply a vertical shift in the final path. So we flip a coin with bias pp, where pp is the probability of heads (HH) and q:=1−pq := 1-p is the probability of tails (TT). If the coin is heads, then the pollen particle moves up uu, and if the coin is tails, then the pollen particle moves down uu (to −u-u). Let’s denote the outcome of each coin flip as a random variable ZiZ_i, taking values in {−1,1}\{-1, 1\}. Then the position after a single coin flip is uZ1u Z_1 (Figure 22). Figure 2. A one-period model of a pollen particle. After a coin clip which is heads with probability pp, the pollen particle moves either up to uu or down to −u-u. S0S_0 denotes the initial position, and uZ1u Z_1 denotes the position after the coin flip. Now consider the position SnS_n after nn time steps. At each time point ii, we flip a coin, which we assume is independent of all other coin tosses, to discover whether the pollen particle is displaced up or down from its current position. Then SnS_n is simply the sum Sn=uZ1+uZ2+⋯+uZn.(1) S_n = u Z_1 + u Z_2 + \dots + u Z_n. \tag{1} Since each ZiZ_i is random, SnS_n is also random. Clearly, as we repeatedly flip our coin, the set of possible locations of the pollen particle expands linearly with nn. We can visualize all these possible locations as a directed graph or tree, sometimes called a binomial tree (Figure 33, left)—we’ll explain the name in a moment. The tree layers (vertical slices) are zero-indexed, and so the root node occurs at time n=0n=0. Each node is a possible location, and the nn-th layer is all possible locations by time nn. The directed edges (left to right) are valid moves of the pollen particle. A path in this binomial tree is a sequence of steps which starts at the tree’s root (left-most node) and continues right at each time step until it reaches a leaf node (right-most node). A valid path is one that always moves left-to-right, from root to leaf. A valid path cannot, for example, move straight down at the same time point or move backwards. Figure 3. Left.A binomial tree with depth n=5n=5. Each node is labeled with the net number of up or down moves required to reach that node. Two random paths are shown in yellow and red. Right. The left plot but with the nodes labeled with (n,k)(n,k) tuples, indexing the number of coin filps and thus the possible number of endpoints by that many flips. To help us identify nodes, let’s introduce the counting number kk, which indexes the leaf nodes, taking values in k∈{0,1,…,n}k \in \{0, 1, \dots, n\}. Like the time index nn, the number kk is a zero-based index. Let’s denote the bottom leaf node with k=0k=0 and the top leaf node with k=nk=n. To illustrate this, I’ve visualized the tree with the nodes labeled with tuples (n,k)(n, k) (Figure 33, right). Now that we understand this simple, discrete-time model for our pollen particle, let’s tackle our motivating question: which outcomes (leaf nodes) are most likely? Any given path is random, but can we say something about the distribution of outcomes? To start, let’s compute the probability of arriving at the highlighted leaf node in Figure 44. This is really the probability of arriving at a given node (n,k)(n, k), which in turn is really the probability of flipping kk heads in nn coin tosses. Let’s use KnK_n for this random variable. Arriving at this node requires that we flip two heads and one tails. The probability of this is P({two heads and one tails})=p2q.(2) \mathbb{P}\left(\{ \text{two heads and one tails} \}\right) = p^2 q. \tag{2} However, there are three ways flip two heads in three coin tosses, {HHT,HTH,THH},(3) \{ HHT, HTH, THH \}, \tag{3} which is another way of saying that there are three paths to the highlighted node. Since each path is a mutually exclusive outcome, we compute our desired probability by summing the probability of all outcomes in Equation 22 by the number of paths: P({arriving at node (3,2)})=P(K3=2)=3p2q.(4) \mathbb{P}\left(\{ \text{arriving at node $(3, 2)$} \}\right) = \mathbb{P}(K_3 = 2) = 3 p^2 q. \tag{4} For example, if p=1/2p=1/2, then this probability would be 3/83/8. Figure 4. A binomial tree of depth n=3n=3. There are three possible paths (red, yellow, purple) to arrive at the node (3,2)(3, 2) (circled node). To compute this probability in general, we just need a way to compute the number of ways to get kk successes or heads in nn trials. Since order matters, the number of ways to pick kk heads from nn coin tosses is n(n−1)(n−2)…(n−k+1)=n!(n−k)!.(5) n (n-1) (n-2) \dots (n-k+1) = \frac{n!}{(n-k)!}. \tag{5} First, we can choose any of nn coin tosses to be a heads. Then we can pick any of n−1n-1 coins tosses to be heads. And so on, until we have k−1k-1 heads. (The last pick is completely constrained.) However, this overcounts the possible paths. For example, this does not distinguish between H1H2H_1 H_2 and H2H1H_2 H_1, where the subscript ii denotes the ii-th coin toss. So we need to divide the permutation in Equation 55 by the number of ways we can order elements in a kk-sized set. This is kk factorial. Putting this together, we see that the number of ways to get to each node in the binomial tree is ordered ways to pick k heads from n tossespermutations of k heads    =    n(n−1)(n−2)…(n−k+1)k(k−1)(k−2)…1.(6) \frac{\text{ordered ways to pick $k$ heads from $n$ tosses}}{\text{permutations