Finite uniform expectations #
Shared finite averages, trajectory expectations, independence (over any finite dependent
product, avg_pi_prod, avg_pi_eval, and of disjoint blocks of coordinates, avg_pi_split),
and reindexing.
The average on an empty type is zero.
Expectation under the uniform distribution on a fintype.
Equations
- Dynamics.avg f = (∑ a : α, f a) / ↑(Fintype.card α)
Instances For
The expectation of an indicator is a counting ratio.
Expectation of a functional of T i.i.d. uniform draws from α,
in transition-operator form: the head draw is averaged out first.
Equations
- Dynamics.expList α 0 x✝ = x✝ []
- Dynamics.expList α T.succ x✝ = Dynamics.avg fun (a : α) => Dynamics.expList α T fun (l : List α) => x✝ (a :: l)
Instances For
Lengths and prefixes: expList α T only evaluates lists of length T #
The comparison form expList_le_of_length is stated above, with the monotonicity lemmas.
Two phases. If, after any first phase l₁ of T₁ rounds, the expectation of Φ over
the second phase is at most a + Ψ l₁, then over both phases it is at most a + 𝔼 Ψ.
Independence: average of a product over a product space #
Independence for a pair of coordinates: the average of a product
g p.1 * h p.2 over a product Fintype β × δ (uniform measure) equals the
product of the individual averages. No Nonempty hypothesis is needed:
if either factor is empty, both sides are 0 by the 0/0 = 0 convention.
Independence over a dependent product: under the uniform distribution on a finite
product ∀ i, β i, the coordinates are independent, so the average of a product
∏ i, g i (x i) is the product of the averages avg (g i).
Marginal over a dependent product: the average of a function of one coordinate, over the whole product space, is its average over that coordinate alone.
Independence over a Fin n-indexed product: the average of a product
∏ i, f i (x i) over the product Fintype Fin n → γ (uniform measure)
equals the product of the individual averages avg (f i). This is the
discrete, measure-theory-free form of "coordinate projections on a product
space are independent", the non-dependent case of avg_pi_prod.
Marginal for Fin n-indexed Pi types: the average of a function of
a single fixed coordinate, over the whole product space, equals its average
over that one factor alone (the non-dependent case of avg_pi_eval).
Independence of disjoint blocks of coordinates: under the uniform distribution on
I → γ, the coordinates in {i // p i} and those in its complement are independent, so the
average of a function of the two restrictions is the iterated average.