Stick Breaking Process

Parent: Stochastic Processes

Definition

The Stick-Breaking Process (SBP) is a stochastic process where each sample path is an infinite sequence of random variables \(\pi_1, \pi_2...\) such that each variable \(pi_i \in (0, 1)\) and sum of the sequence \(\sum_{k=1}^{\infty} \pi_1\) equals 1 with probability 1. The way the variables is generated is by sampling an i.i.d. sequence of \(v_k \sim Beta(\alpha, \beta)\) and then defining

\[\pi_K = v_K \prod_{k = 1}^K (1 - v_k)\]

This is the source of the name “stick breaking”: a stick with mass 1 is sequentially broken into smaller and smaller pieces.

Relation to Other Stochastic Processes

Griffiths-Engen-McCloskey (GEM) Distribution

If the stick-breaking weights \(v_k ~ Beta(\alpha, \beta)\) with \(\alpha = 1\), then the infinite random vector \(\pi = (\pi_1, \pi_2, ...)\) is said to be distributed according to the so_called Griffiths-Engen-McCloskey distribution \(GEM(\beta)\).

Dirichlet Process

The SBP is intimately related to the Dirichlet process. Let \(G \sim DP(\alpha, G_0)\) be a random distribution. The distribution is defined as:

\[G = \sum_{k=1}^K \pi_k \delta_{\theta_{k}}\]

where \(\pi_1, \pi_2, ...\) is an infinite sequence of probability masses summing to 1 and \(\theta_1, \theta_2, ...\) is an infinite sequence of elements sampled from the base distribution \(G_0\). From this perspective, one can see that an easy way to sample a random distribution from a DP is through the three-step stick-breaking construction:

1. Sample \(\pi_1, \pi_2, ... \sim_{i.i.d.} SBP(1, \alpha)\)
2. Sample \(\theta_1, \theta_2, ...\) from the base distribution \(G_0\)
3. Create an infinite mixture distribution \(G := \sum_{k=1}^{\infty} \pi_k \delta_{\theta_{k}}\)

This constructed \(G\) is distributed according to \(DP(\alpha, G_0)\), hence the name stick-breaking construction.

Chinese Restaurant Process

The SBP is closely related to the CRP. The difference is that the CRP integrates out the base measure \(G\), meaning that the CRP cares only for how many elements have the same value, regardless of what that value (i.e. the location) is.