Ewens Permutation Cycle Law
Weight permutation cycles and connect enumeration to a rising-factorial probability law.
By Riano · Published · Updated · Report a correction
Ewens Permutation Cycle Law
The Ewens sampling formula assigns probabilities to partitions of a finite set, particularly arising in population genetics and the study of random permutations. When viewed as a distribution over the symmetric group of permutations of length n, it assigns a weight proportional to θ raised to the number of cycles in the permutation's disjoint cycle decomposition.
theory
Let Π be a random permutation of n elements. Under the Ewens distribution with parameter θ > 0, the probability of drawing a specific permutation π having k cycles is given by:
P(Π = π) = θk / (θ)n
where (θ)n = θ(θ+1)···(θ+n-1) is the rising factorial. The number of permutations of length n with exactly k cycles is the unsigned Stirling number of the first kind, denoted |s(n, k)| or c(n, k). Therefore, the probability that a random permutation has exactly k cycles is:
P(K = k) = c(n, k) θk / (θ)n
The case θ = 1 corresponds to the uniform distribution over all n! permutations. The expected number of cycles is E(K) = ∑i=0n-1 θ / (θ + i) and the variance is Var(K) = ∑i=0n-1 θ i / (θ + i)2.
worked-example
Consider n = 4, θ = 1, and investigating the probability of having exactly k = 2 cycles.
- Calculate the rising factorial normalization:
(θ)n = 1 × 2 × 3 × 4 = 24. - Find the unsigned Stirling number of the first kind
c(4, 2). The recurrence relation givesc(4, 2) = c(3, 1) + 3 × c(3, 2) = 2 + 3 × 3 = 11. - Calculate the probability:
P(K=2) = 11 × 12 / 24 ≈ 0.4583333333333333.
experiment
Open the module and observe how the probability distribution over cycle counts shifts as you change the parameter θ.
- Set Permutation size to 4 and Theta to 1. Notice the expected cycles is about 2.083.
- Increase Theta to 4. Observe that the distribution shifts towards a higher number of cycles.
- Set Permutation size to 0. Verify that the boundary case yields 0 expected cycles and variance.
limitations
This implementation explicitly computes the unsigned Stirling numbers using their recurrence relation and limits n to a small finite domain (up to 5) to ensure exact representation without floating-point overflow or precision loss, which becomes a factor for larger values of n.
references
For more rigorous mathematical treatment and applications of this law, consult the primary literature on the subject.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Ewens Permutation Cycle Law module.
Try Ewens Permutation Cycle Law on Riano →