From Independent Increments to a Random Walk
A sequence of independent random variables can be turned into a process by accumulating their values. The resulting process is a random walk: each new value is the previous value plus one new increment. This construction connects the distribution of a path to the distributions of the summands. It also explains why the values of the process are usually dependent, even when its increments are independent.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((Y_n)_{n\ge1}\) be a sequence of independent real-valued random variables, and choose a fixed starting value \(x\in\mathbb{R}\). The process has discrete time \(n\ge0\) and state space \(S=\mathbb{R}\). Its natural filtration is \(\mathcal{F}_n=\sigma(S_0,\ldots,S_n)\), the information generated by its values up to time \(n\).
Independence of the summands means that probabilities involving separate increments factor into products. The process values, however, reuse earlier summands: \(S_2=x+Y_1+Y_2\) contains the same \(Y_1\) as \(S_1=x+Y_1\). Thus independent increments do not mean independent process values.
Finite-Time Distributions from the Summands
Let \(\nu_r\) denote the probability distribution of \(Y_r\). The distribution of \(S_n\) is the distribution of \(x+Y_1+\cdots+Y_n\), so it is the convolution of the first \(n\) increment laws, shifted by \(x\). In particular, for a Borel set \(A\subseteq\mathbb{R}\),
Here the product of the measures is valid because the increments are independent. To describe several times, choose \(0=n_0<n_1<\cdots<n_m\), and define the block increments \(D_r=S_{n_r}-S_{n_{r-1}}\). Each \(D_r\) is a sum of the \(Y_j\) in its time block. Different blocks use disjoint sets of independent summands, so \(D_1,\ldots,D_m\) are independent. The process values are recovered from these blocks by \(S_{n_r}=x+D_1+\cdots+D_r\). Therefore, if \(\eta_r\) is the distribution of \(D_r\), then for Borel sets \(A_1,\ldots,A_m\),
This formula also describes finite-dimensional distributions: the joint laws of the process at any finite collection of times. Repeated observation times add no new information and can be removed before applying the formula.
Proof. For the first assertion, suppose first that the summands are independent. Increments over disjoint time intervals are sums over disjoint sets of summands. Independence of the summands implies independence of these sums, so the process has independent increments. Conversely, each summand is a one-step process increment, \(Y_n=S_n-S_{n-1}\). The independent-increments property applied to the disjoint one-step intervals implies that the \(Y_n\) are independent.
For the second assertion, stationary increments means that the distribution of \(S_{m+k}-S_m\) depends on the interval length \(k\), not on its starting time \(m\). If the summands are identically distributed and independent, a block of length \(k\) is a sum of \(k\) independent variables with the same common law, regardless of its starting time; hence its distribution depends only on \(k\). Conversely, take \(k=1\). Stationarity then says that \(S_{m+1}-S_m=Y_{m+1}\) has the same distribution for every \(m\ge0\), so the summands are identically distributed. \(\square\)
When the increments have finite second moments, the same construction gives simple moment formulas.
Proof. By the definition of \(S_n\) and linearity of expectation, \(\mathbb{E}[S_n]=x+\sum_{r=1}^n\mathbb{E}[Y_r]\). For the variance, adding the constant \(x\) does not change variance. Expanding the variance of the sum gives the sum of individual variances plus twice the sum of pairwise covariances. Independence and finite second moments give \(\operatorname{Cov}(Y_r,Y_s)=0\) for \(r\ne s\), so only the individual variances remain. \(\square\)
Calculating Distributions and Path Events
Worked Example: A Symmetric Walk at Three Times
Let \(S_0=0\), and let the independent increments each equal \(1\) or \(-1\) with probability \(\tfrac12\). Find \(\mathbb{P}(S_3=1)\) and the probability of the path event \(S_1=1,\ S_2=0,\ S_3=1\).
Every one of the \(2^3=8\) three-increment sequences has probability \((\tfrac12)^3=\tfrac18\). To have \(S_3=1\), a sequence must contain two \(+1\) increments and one \(-1\) increment. The three possible sequences are \((1,1,-1)\), \((1,-1,1)\), and \((-1,1,1)\). Thus
The specified path values require \(Y_1=1\), \(Y_2=-1\), and \(Y_3=1\), since each increment is the difference between consecutive values. There is exactly one such sequence, so its probability is \(\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18\). As a check, its partial sums are \(0+1=1\), \(1-1=0\), and \(0+1=1\), as required.
Worked Example: Independent but Nonidentical Increments
Let \(S_0=0\). Suppose \(Y_1,Y_2,Y_3\) are independent, with \(\mathbb{P}(Y_1=1)=\tfrac12\), \(\mathbb{P}(Y_2=1)=\tfrac13\), and \(\mathbb{P}(Y_3=1)=\tfrac14\); each increment is otherwise \(0\). Find the distributions of \(S_2\) and \(S_3\), and decide whether the process has stationary increments.
For \(S_2=Y_1+Y_2\), the probability of zero is \(\tfrac12\cdot\tfrac23=\tfrac13\). The probability of two is \(\tfrac12\cdot\tfrac13=\tfrac16\). The remaining probability is for one, namely \(1-\tfrac13-\tfrac16=\tfrac12\). Thus the probabilities at \(0,1,2\) are \(\tfrac13,\tfrac12,\tfrac16\), which sum to \(1\).
For \(S_3\), zero successes has probability \(\tfrac12\cdot\tfrac23\cdot\tfrac34=\tfrac14\), while three successes has probability \(\tfrac12\cdot\tfrac13\cdot\tfrac14=\tfrac1{24}\). Exactly one success has probability
Exactly two successes has probability
The four probabilities at \(0,1,2,3\) are therefore \(\tfrac14,\tfrac{11}{24},\tfrac14,\tfrac1{24}\). Their sum is \(\tfrac6{24}+\tfrac{11}{24}+\tfrac6{24}+\tfrac1{24}=1\). The increments are independent, so the process has independent increments. They are not identically distributed: \(\mathbb{P}(S_1-S_0=1)=\tfrac12\), whereas \(\mathbb{P}(S_2-S_1=1)=\tfrac13\). Thus the process does not have stationary increments.
Worked Example: Probability of Staying Nonnegative
Let \(S_0=0\), with independent increments satisfying \(\mathbb{P}(Y_n=1)=\tfrac23\) and \(\mathbb{P}(Y_n=-1)=\tfrac13\) at every time. Find the probability that \(S_1,S_2,S_3\) are all nonnegative.
Write \(U\) for an increment of \(1\) and \(D\) for an increment of \(-1\). For the path to be nonnegative at time \(1\), its first increment must be \(U\). After that, the length-three paths that stay nonnegative are \(UUU\), \(UUD\), and \(UDU\). Their partial-sum paths are respectively \((1,2,3)\), \((1,2,1)\), and \((1,0,1)\). The other path beginning with \(U\), namely \(UDD\), reaches \(-1\) at time \(3\), so it does not qualify. The probabilities of the three qualifying paths are \((\tfrac23)^3=\tfrac8{27}\), \((\tfrac23)^2(\tfrac13)=\tfrac4{27}\), and \((\tfrac23)(\tfrac13)(\tfrac23)=\tfrac4{27}\). Therefore the required probability is \(\tfrac8{27}+\tfrac4{27}+\tfrac4{27}=\tfrac{16}{27}\). The seven excluded paths have total probability \(1-\tfrac{16}{27}=\tfrac{11}{27}\), checking that the event probability is consistent with total probability \(1\).
Reading a Path Through Its Increments
A realized path is a sequence of values \(S_0,S_1,\ldots\). Once the starting value is fixed, its increments are uniquely determined by successive differences, and the increments determine the path by successive addition. In particular, a path constraint can be translated into constraints on partial sums of the increments. For example, the requirement \(S_k\ge0\) for \(1\le k\le n\) becomes \(x+\sum_{r=1}^{k}Y_r\ge0\) at each of those times. This translation is useful because the increment variables are independent, while the path values themselves generally are not.
For identically distributed increments, every block of a given length has the same distribution. This is the precise reason the walk has stationary increments. It does not say that the levels \(S_n\) have the same distribution at different times: the level at time \(n\) accumulates \(n\) summands, so its distribution usually changes with \(n\). For nonidentically distributed independent summands, the block distribution can also depend on where the block begins.
Common mistake. Suppose the increments are the symmetric \(\{-1,1\}\) variables in the first example. A tempting but incorrect calculation is to treat \(S_1\) and \(S_2\) as independent and write \(\mathbb{P}(S_1=1,S_2=2)=\mathbb{P}(S_1=1)\mathbb{P}(S_2=2)=\tfrac12\cdot\tfrac14=\tfrac18\). In fact, \(S_1=1\) forces \(Y_1=1\), and \(S_2=2\) then requires \(Y_2=1\). The actual probability is \(\mathbb{P}(Y_1=1,Y_2=1)=\tfrac12\cdot\tfrac12=\tfrac14\). The increments are independent; the partial-sum values are not.
Check Your Understanding
Use the partial-sum definition and independence of increments to answer these questions.
- If \(S_0=3\), \(Y_1=-2\), and \(Y_2=4\), calculate \(S_1\) and \(S_2\).
- For independent increments with \(\mathbb{P}(Y_1=1)=\tfrac14\) and \(\mathbb{P}(Y_2=1)=\tfrac12\), with each increment otherwise zero, find \(\mathbb{P}(S_2=1)\).
- Why do independent increments imply that \(S_1\) and \(S_2-S_1\) are independent, but not that \(S_1\) and \(S_2\) are independent?
- For independent summands, what condition on their distributions is equivalent to stationary increments of the partial-sum process?
- If the increments are identically distributed with finite variance \(v\), what is \(\operatorname{Var}(S_n)\), and which assumption is needed to add the variances?