Exact variance of all cycles of a uniform permutation
ProvedAnalyticCombinatorics.Ch9.LimitLaws.RCyclesPoissonNS.totalCycleCount_variance_eq_harmonic_sub_harmonic2analytic-combinatoricslean4limit-laws
For a uniform permutation of labels, let count all cycles including fixed points. For every , including zero,
Expectations are the source finite uniform sums; the theorem carries no asymptotic or distribution premise.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch9_LimitLaws_FixedPointsPoisson
import Definitions.Def_AnalyticCombinatorics_Ch9_LimitLaws_TotalCycleVariance
import Definitions.Def_AnalyticCombinatorics_Ch9_LimitLaws_PMFToDistribution
import Definitions.Def_AnalyticCombinatorics_Ch9_LimitLaws_RCyclesPoisson
import Definitions.Def_AnalyticCombinatorics_Ch9_LimitLaws_ExpectedCycles
import Mathlib
import Mathlib.MeasureTheory.Function.ConvergenceInDistribution
import Mathlib.Combinatorics.Derangements.Exponential
import Mathlib.Analysis.Asymptotics.AsymptoticEquivalent
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Exact variance of the total number of cycles in a uniform random permutation
The Goncharov–Kolchin companion to the cycle-count CLT: for `K_n` the total number of cycles of a
uniform random permutation of `[n]`,
`E[K_n] = H_n`, `Var(K_n) = H_n − H_n^{(2)}`,
where `H_n = ∑_{r=1}^n 1/r` and `H_n^{(2)} = ∑_{r=1}^n 1/r²`.
`TotalCycleSecondMoment` already reduces the variance to `H_n + cycleFitPairSum n − H_n²`. This file
supplies the one remaining finite identity `cycleFitPairSum n = H_n² − H_n^{(2)}` (antidiagonal split
`1/(r(n+1−r)) = (1/r + 1/(n+1−r))/(n+1)` plus the reflection `r ↦ n+1−r`), giving the exact variance.
-/
open Filter Asymptotics
open scoped BigOperators Topology
open AnalyticCombinatorics
open AnalyticCombinatorics.Ch9
open AnalyticCombinatorics.Ch9.LimitLaws
open AnalyticCombinatorics.Ch9.LimitLaws.RCyclesPoissonNS
Formal statement
theorem AnalyticCombinatorics.Ch9.LimitLaws.RCyclesPoissonNS.totalCycleCount_variance_eq_harmonic_sub_harmonic2 (n : ℕ) :
FixedPointsPoissonNS.uniformPermExpectation n
(fun σ => (totalCycleCount n σ : ℝ) ^ 2) -
(FixedPointsPoissonNS.uniformPermExpectation n
(fun σ => (totalCycleCount n σ : ℝ))) ^ 2
= cycleH1 n - cycleH2 n := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).