Tutorials › Stochastic Processes › Dwass’s Formula and the Cyclic Lemma

Home  /  Tutorials  /  Branching Processes: Extensions

Branching Processes: Extensions · Tutorial 367 of 994

Dwass's Formula and the Cyclic Lemma

Learn why a cyclic rotation counts finite branching trees and how Dwass’s formula gives exact probabilities for two common offspring distributions.

Advanced 12 min read

What You'll Learn

  • Express the event of exactly \(n\) total individuals using an offspring sequence.
  • Prove the cyclic lemma for integer increments summing to minus one.
  • Derive Dwass’s formula, including the case \(n=1\).
  • Calculate binomial-offspring total-progeny probabilities exactly.
  • Calculate Poisson-offspring total-progeny probabilities exactly.
  • Identify the error caused by using the wrong offspring-sum target.

From an Offspring Sequence to Total Progeny

In a Galton–Watson process, the event that the family has exactly \(n\) individuals is governed by the offspring counts of those \(n\) individuals. The key is to order individuals so that their offspring counts can be read one at a time, keeping track of how many individuals are still waiting to be processed. A cyclic counting argument then turns a constraint on the entire sequence into a factor of \(1/n\).

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((Z_k)_{k\ge0}\) be a discrete-time Galton–Watson process with state space \(S=\{0,1,2,\ldots\}\), initial population \(Z_0=1\), and offspring variable \(\xi\), which takes values in \(S\). Each individual independently has a number of children distributed as \(\xi\). Write \(T=\sum_{k\ge0}Z_k\) for total progeny, allowing \(T=\infty\). No assumption that \(\xi\) has a finite mean is needed below.

Order the individuals breadth-first: process the ancestor first, then its children, then the next individuals waiting in the queue. Let \(X_i\) be the number of children of the \(i\)th individual in this order. The offspring counts can be represented by an independent sequence \((X_i)_{i\ge1}\), each with the distribution of \(\xi\). If the queue starts with one individual, processing individual \(i\) removes one from the queue and adds \(X_i\). Thus, after processing \(k\) individuals, the queue size is \(1+\sum_{i=1}^k(X_i-1)\), as long as the exploration has not ended.

Definition: For a fixed \(n\ge1\), call an offspring sequence \(x_1,\ldots,x_n\) a valid exploration sequence if \(\sum_{i=1}^k(x_i-1)\ge0\) for every \(1\le k<n\), and \(\sum_{i=1}^n(x_i-1)=-1\). The first condition says the queue remains nonempty before the last individual is processed; the second says it is empty immediately afterward.

Consequently, \(T=n\) exactly when \(X_1,\ldots,X_n\) form a valid exploration sequence. In particular, the total number of children in such a sequence must be \(n-1\): every individual except the ancestor is the child of one of the \(n\) individuals.

The Cyclic Lemma

For a sequence \(y_1,\ldots,y_n\) of integers with \(y_i\ge-1\) and total sum \(-1\), a cyclic rotation starting after position \(r\), where \(0\le r<n\), is \(y_{r+1},\ldots,y_n,y_1,\ldots,y_r\). The cyclic lemma says exactly one of these \(n\) indexed rotations has all its partial sums of lengths \(1,\ldots,n-1\) nonnegative.

Theorem (Cyclic lemma): If \(y_1,\ldots,y_n\) are integers with \(y_i\ge-1\) and \(\sum_{i=1}^n y_i=-1\), exactly one cyclic rotation satisfies \(\sum_{i=1}^k y_i\ge0\) for every \(1\le k<n\), where the sums in this condition are taken in the rotated order.

Proof. Define \(s_0=0\) and \(s_k=\sum_{i=1}^k y_i\) for \(1\le k\le n\), so \(s_n=-1\). First consider a rotation starting after \(r>0\). Its partial sums that end in the original sequence at \(j\), for \(r<j\le n\), are \(s_j-s_r\). These endpoints are all intermediate in the rotated sequence, so they must all be nonnegative, including the endpoint \(j=n\). Thus the nonwrapped conditions are \(s_j\ge s_r\) for \(r<j\le n\). A wrapped partial sum ending at an original index \(l\), with \(1\le l<r\), is \(-1-s_r+s_l\); it is nonnegative exactly when \(s_l>s_r\), since the values are integers. These are all the intermediate partial sums: the endpoint \(l=0\) is not a partial sum in the wrapped segment, and the full rotated sum, which is \(-1\), is not required to be nonnegative. The stated conditions therefore hold exactly when \(r\) is the first index at which the minimum of \(s_0,\ldots,s_n\) is attained. If the first minimum is at \(n\), then \(s_k>-1\) for every \(k<n\), so the rotation \(r=0\) is valid. Conversely, that rotation is valid exactly when \(s_k\ge0\) for \(1\le k<n\), which, because the \(s_k\) are integers and \(s_n=-1\), means the first minimum is at \(n\). There is one first index of a minimum in the finite list \(s_0,\ldots,s_n\), and it selects exactly one rotation by these cases. This proves the claim. \(\square\)

Dwass’s Formula

The cyclic lemma applies to offspring counts by setting \(y_i=x_i-1\). The condition \(x_i\ge0\) gives \(y_i\ge-1\), and \(\sum_i x_i=n-1\) gives \(\sum_i y_i=-1\). Among the \(n\) rotations of any such sequence, exactly one is a valid exploration sequence.

Theorem (Dwass’s formula): For any Galton–Watson process started from one ancestor, with nonnegative integer-valued offspring variable \(\xi\), and every integer \(n\ge1\), $$ \mathbb{P}(T=n)=\frac{1}{n}\mathbb{P}\!\left(\sum_{i=1}^{n}X_i=n-1\right), $$ where \(X_1,\ldots,X_n\) are independent copies of \(\xi\).

Proof. Fix \(n\). Let \(\mathcal{A}_n\) be the set of ordered \(n\)-tuples of nonnegative integers whose sum is \(n-1\). This set is finite. For \(x=(x_1,\ldots,x_n)\in\mathcal{A}_n\), its probability as a sequence of offspring counts is \(w(x)=\prod_{i=1}^n\mathbb{P}(\xi=x_i)\). Cyclic rotations preserve this product, because they only reorder its factors. Let \(I_r(x)\) be \(1\) if the rotation of \(x\) starting after position \(r\) is a valid exploration sequence, and \(0\) otherwise. Applying the cyclic lemma to \(y_i=x_i-1\) gives \(\sum_{r=0}^{n-1} I_r(x)=1\). Also, rotation permutes \(\mathcal{A}_n\) and preserves \(w(x)\), so the weighted sums \(\sum_{x\in\mathcal{A}_n}w(x)I_r(x)\) are equal for every \(r\). Summing them over all \(r\) therefore gives $$ n\sum_{x\in\mathcal{A}_n}w(x)I_0(x) =\sum_{x\in\mathcal{A}_n}w(x) =\mathbb{P}\!\left(\sum_{i=1}^nX_i=n-1\right). $$ The left-hand sum without the factor \(n\) is \(\mathbb{P}(T=n)\), by the queue characterization of a valid exploration sequence. Dividing by \(n\) proves the formula. The argument also covers \(n=1\): the sum condition is \(X_1=0\), which is exactly the event that the ancestor has no children. \(\square\)

The formula concerns each finite value \(n\); it does not require that total progeny be finite with probability one. It expresses a tree-size probability in terms of a sum of independent offspring counts, which is often easier to compute directly.

Worked Example: Finding the Valid Rotation

Consider the offspring counts \((1,0,2,0)\), whose sum is \(3=4-1\). Check which cyclic rotation describes a family of exactly four individuals.

The increments \(x_i-1\) are \((0,-1,1,-1)\), with partial sums \(s_0=0,s_1=0,s_2=-1,s_3=0,s_4=-1\). The first index where the minimum is attained is \(r=2\), so the unique valid rotation starts after the second entry. The four rotations and their partial sums before the final step are:

  • \((1,0,2,0)\): increments \((0,-1,1,-1)\), with partial sums \(0,-1,0\); this fails at the second partial sum.
  • \((0,2,0,1)\): increments \((-1,1,-1,0)\), with partial sums \(-1,0,-1\); this fails at the first partial sum.
  • \((2,0,1,0)\): increments \((1,-1,0,-1)\), with partial sums \(1,0,0\); this is valid.
  • \((0,1,0,2)\): increments \((-1,0,-1,1)\), with partial sums \(-1,-1,0\); this fails at the first partial sum.

For the valid rotation, the queue sizes after processing one, two, three, and four individuals are \(1+1=2\), \(2-1=1\), \(1+0=1\), and \(1-1=0\), respectively. The queue stays positive until the last step and then empties, as required. The total increment is \(1-1+0-1=-1\), which checks the total-offspring condition.

Binomial Offspring

If \(\xi\) has a binomial distribution with parameters \(m\) and \(p\), the sum of \(n\) independent copies has a binomial distribution with parameters \(mn\) and \(p\): it counts successes across \(mn\) independent Bernoulli trials. Dwass’s formula then gives, for \(0\le p\le1\),

$$ \mathbb{P}(T=n)=\frac{1}{n}\binom{mn}{n-1}p^{n-1}(1-p)^{mn-n+1}, $$

when \(0\le n-1\le mn\). If that count condition fails, the probability is zero. At \(p=0\) or \(p=1\), the formula is interpreted using the corresponding degenerate binomial law, rather than an ambiguous expression involving a zero power.

Worked Example: Binomial Offspring with \(m=2\)

Let each individual have a binomial \(\operatorname{Binomial}(2,\tfrac13)\) number of children. Its probabilities of \(0,1,2\) children are \(\tfrac49,\tfrac49,\tfrac19\), and they sum to \(\tfrac49+\tfrac49+\tfrac19=1\). Find \(\mathbb{P}(T=3)\).

The required total offspring count is \(3-1=2\). The six independent Bernoulli trials across the three individuals have success probability \(\tfrac13\), so

$$ \begin{aligned} \mathbb{P}(T=3) &=\frac13\binom{6}{2}\left(\frac13\right)^2\left(\frac23\right)^4\\ &=\frac13\cdot15\cdot\frac19\cdot\frac{16}{81} =\frac{240}{2187} =\frac{80}{729}. \end{aligned} $$

Check by enumerating offspring sequences: among triples summing to \(2\), there are three permutations of \((2,0,0)\), each with probability \(\tfrac19(\tfrac49)^2=\tfrac{16}{729}\), and three permutations of \((1,1,0)\), each with probability \((\tfrac49)^3=\tfrac{64}{729}\). Thus the probability that the total is \(2\) is \(3\cdot\tfrac{16}{729}+3\cdot\tfrac{64}{729}=\tfrac{240}{729}\). Dividing by \(3\) gives \(\tfrac{80}{729}\), as above.

Poisson Offspring

If \(\xi\) is Poisson with parameter \(\lambda>0\), the sum of \(n\) independent copies is Poisson with parameter \(n\lambda\). For example, this follows by multiplying their probability generating functions: each is \(\exp(\lambda(s-1))\), so the product is \(\exp(n\lambda(s-1))\). Applying Dwass’s formula gives

$$ \mathbb{P}(T=n) =\frac{1}{n}e^{-n\lambda}\frac{(n\lambda)^{n-1}}{(n-1)!} =e^{-n\lambda}\frac{(n\lambda)^{n-1}}{n!}. $$

For \(n=1\), this reduces to \(\mathbb{P}(T=1)=e^{-\lambda}\), the probability that the ancestor has no children. If \(\lambda=0\), every individual has zero children and \(T=1\) with probability one; this degenerate case is handled directly.

Worked Example: Poisson Offspring with \(\lambda=\tfrac12\)

Let each individual have a Poisson \((\tfrac12)\) number of children. Find the probability of exactly three individuals in total.

The sum \(X_1+X_2+X_3\) has a Poisson \((\tfrac32)\) distribution. The event \(T=3\) requires that sum to equal \(2\), so

$$ \begin{aligned} \mathbb{P}(T=3) &=\frac13\mathbb{P}\!\left(\operatorname{Poisson}\!\left(\frac32\right)=2\right)\\ &=\frac13 e^{-3/2}\frac{(3/2)^2}{2!} =\frac13 e^{-3/2}\frac{9}{8} =\frac38e^{-3/2}. \end{aligned} $$

Check: the Poisson probability for a total of \(2\) is \(\tfrac98e^{-3/2}\); multiplying by the cyclic factor \(\tfrac13\) gives \(\tfrac38e^{-3/2}\). For \(n=1\), the same formula gives \(e^{-1/2}(1/2)^0/1!=e^{-1/2}\), which is precisely the probability the ancestor has no children.

A Common Error and What the Formula Does Not Say

A frequent mistake is to use \(n\), rather than \(n-1\), as the target for the total number of offspring. For exactly \(n\) individuals, there are \(n-1\) children in the family: the ancestor is not anyone’s child within that family. In the binomial example with \(n=3\), the incorrect target \(3\) would give \(\tfrac13\mathbb{P}(\operatorname{Binomial}(6,\tfrac13)=3)=\tfrac13\cdot\tfrac{160}{729}=\tfrac{160}{2187}\). The correct target is \(2\), giving \(\tfrac13\cdot\tfrac{240}{729}=\tfrac{80}{729}\). The incorrect calculation fails because it counts one extra child.

Another point of care is the factor \(1/n\): it applies to the probability of the specific sum event, not to the probability of any one offspring sequence chosen in advance. Across all sequences with total \(n-1\), each sequence has exactly one valid cyclic rotation, and the independent offspring law assigns equal probability to a sequence and each of its rotations. The proof uses that symmetry; it does not assert that all sequences themselves have equal probability.

Dwass’s formula gives exact probabilities for finite total progeny, whether or not extinction is certain. It does not by itself say that these probabilities sum to one: if the process can survive forever, some probability may belong to \(T=\infty\). Nor does the formula require a finite offspring mean. Its ingredients are the breadth-first queue condition, independence and identical distribution of offspring counts, and the cyclic lemma.

Check Your Understanding

Use the queue condition and the formula to justify your answers.

  1. Why must the total offspring count equal \(n-1\) when total progeny is \(n\)?
  2. For increments \((-1,1,0)\), identify the unique rotation whose partial sums before the final step are nonnegative.
  3. If \(\xi\) is \(\operatorname{Binomial}(1,\tfrac12)\), compute \(\mathbb{P}(T=2)\) using Dwass’s formula.
  4. For Poisson offspring with parameter \(\lambda>0\), write the formula for \(\mathbb{P}(T=2)\) and simplify it.
  5. Explain why the cyclic-rotation argument requires the offspring counts to be independent and identically distributed.

Previous

Next

Back to Tutorials