Exact variance of all cycles of a uniform permutation
DefinitionAnalyticCombinatorics_Ch9_LimitLaws_TotalCycleVarianceanalytic-combinatoricslean4limit-laws
The mathematical objects and operations are specified by the following source definitions.
noncomputable def cycleH1 (n : ℕ) : ℝ :=
∑ r ∈ Finset.Icc 1 n, (r : ℝ)⁻¹
noncomputable def cycleH2 (n : ℕ) : ℝ :=
∑ r ∈ Finset.Icc 1 n, ((r : ℝ)⁻¹) ^ 2
Definition code
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.
-/
noncomputable section
open Filter Asymptotics
open scoped BigOperators Topology
namespace AnalyticCombinatorics
namespace Ch9
namespace LimitLaws
namespace RCyclesPoissonNS
/-- First harmonic sum `H_n = ∑_{r=1}^n 1/r`. -/
noncomputable def cycleH1 (n : ℕ) : ℝ :=
∑ r ∈ Finset.Icc 1 n, (r : ℝ)⁻¹
/-- Second harmonic sum `H_n^{(2)} = ∑_{r=1}^n 1/r²`. -/
noncomputable def cycleH2 (n : ℕ) : ℝ :=
∑ r ∈ Finset.Icc 1 n, ((r : ℝ)⁻¹) ^ 2
end RCyclesPoissonNS
end LimitLaws
end Ch9
end AnalyticCombinatorics
Source