Documentation

Dynamics.Distribution

Normalized finite distributions #

Real weights make expectations finite sums. Unlike avg, a normalized distribution cannot exist on an empty type. Uniform expectations retain their old empty-type convention.

structure Dynamics.Distribution (α : Type u_1) [Fintype α] :
Type u_1

Nonnegative real weights with total mass one.

  • weight : α → ℝ
  • nonneg (a : α) : 0 ≤ self.weight a
  • sum_one : ∑ a : α, self.weight a = 1
Instances For
    noncomputable def Dynamics.Distribution.expect {α : Type u_1} [Fintype α] (p : Distribution α) (f : α → ℝ) :

    Expectation of a real observable.

    Equations
    Instances For
      noncomputable def Dynamics.Distribution.prob {α : Type u_1} [Fintype α] (p : Distribution α) (s : α → Prop) :

      Probability of an event.

      Equations
      Instances For
        @[simp]
        theorem Dynamics.Distribution.expect_const {α : Type u_1} [Fintype α] (p : Distribution α) (c : ℝ) :
        (p.expect fun (x : α) => c) = c
        theorem Dynamics.Distribution.expect_nonneg {α : Type u_1} [Fintype α] (p : Distribution α) {f : α → ℝ} (h : ∀ (a : α), 0 ≤ f a) :
        0 ≤ p.expect f
        theorem Dynamics.Distribution.expect_mono {α : Type u_1} [Fintype α] (p : Distribution α) {f g : α → ℝ} (h : ∀ (a : α), f a ≤ g a) :
        p.expect f ≤ p.expect g
        theorem Dynamics.Distribution.expect_lt_one {α : Type u_1} [Fintype α] (p : Distribution α) (f : α → ℝ) (hf : ∀ (a : α), f a ≤ 1) (b : α) (hb : 0 < p.weight b) (hfb : f b < 1) :
        p.expect f < 1

        An observable bounded by 1 that is strictly below 1 at a point of positive weight has expectation strictly below 1 (it replaces Moran.expect_lt_one and Voter.expect_lt_one).

        theorem Dynamics.Distribution.expect_add {α : Type u_1} [Fintype α] (p : Distribution α) (f g : α → ℝ) :
        (p.expect fun (a : α) => f a + g a) = p.expect f + p.expect g
        theorem Dynamics.Distribution.expect_sub {α : Type u_1} [Fintype α] (p : Distribution α) (f g : α → ℝ) :
        (p.expect fun (a : α) => f a - g a) = p.expect f - p.expect g
        theorem Dynamics.Distribution.expect_mul {α : Type u_1} [Fintype α] (p : Distribution α) (c : ℝ) (f : α → ℝ) :
        (p.expect fun (a : α) => c * f a) = c * p.expect f
        theorem Dynamics.Distribution.expect_sum {α : Type u_1} {ι : Type u_3} [Fintype α] [Fintype ι] (p : Distribution α) (f : ι → α → ℝ) :
        (p.expect fun (a : α) => ∑ i : ι, f i a) = ∑ i : ι, p.expect (f i)
        theorem Dynamics.Distribution.prob_nonneg {α : Type u_1} [Fintype α] (p : Distribution α) (s : α → Prop) :
        0 ≤ p.prob s
        theorem Dynamics.Distribution.prob_le_one {α : Type u_1} [Fintype α] (p : Distribution α) (s : α → Prop) :
        p.prob s ≤ 1
        theorem Dynamics.Distribution.prob_mono {α : Type u_1} [Fintype α] (p : Distribution α) {s t : α → Prop} (h : ∀ ⦃a : α⦄, s a → t a) :
        p.prob s ≤ p.prob t

        Monotonicity of probability: a larger event has a larger probability. A set inclusion h : A ⊆ B can be passed directly for the events (· ∈ A) and (· ∈ B).

        theorem Dynamics.Distribution.prob_eq_expect {α : Type u_1} [Fintype α] (p : Distribution α) (s : α → Prop) [DecidablePred s] :
        p.prob s = p.expect fun (a : α) => if s a then 1 else 0

        prob computed with any decidability instance for the event.

        Events #

        theorem Dynamics.Distribution.prob_congr {α : Type u_1} [Fintype α] (p : Distribution α) {s t : α → Prop} (h : ∀ (a : α), s a ↔ t a) :
        p.prob s = p.prob t

        Events that agree pointwise have the same probability.

        theorem Dynamics.Distribution.prob_eq_one {α : Type u_1} [Fintype α] (p : Distribution α) {s : α → Prop} (h : ∀ (a : α), s a) :
        p.prob s = 1

        A sure event has probability one.

        theorem Dynamics.Distribution.prob_eq_zero {α : Type u_1} [Fintype α] (p : Distribution α) {s : α → Prop} (h : ∀ (a : α), ¬s a) :
        p.prob s = 0

        An impossible event has probability zero.

        theorem Dynamics.Distribution.prob_not {α : Type u_1} [Fintype α] (p : Distribution α) (s : α → Prop) :
        (p.prob fun (a : α) => ¬s a) = 1 - p.prob s

        Complement rule: P(¬s) = 1 - P(s).

        theorem Dynamics.Distribution.one_sub_prob_le_prob {α : Type u_1} [Fintype α] (p : Distribution α) {s t : α → Prop} (h : ∀ (a : α), ¬s a → t a) :
        1 - p.prob s ≤ p.prob t

        If t holds wherever s fails, then 1 - P(s) ≤ P(t).

        theorem Dynamics.Distribution.prob_or_le {α : Type u_1} [Fintype α] (p : Distribution α) (s t : α → Prop) :
        (p.prob fun (a : α) => s a ∨ t a) ≤ p.prob s + p.prob t

        Union bound for two events.

        theorem Dynamics.Distribution.prob_exists_le_sum {α : Type u_1} [Fintype α] {κ : Type u_4} (p : Distribution α) (I : Finset κ) (s : κ → α → Prop) :
        (p.prob fun (a : α) => ∃ i ∈ I, s i a) ≤ ∑ i ∈ I, p.prob (s i)

        Union bound over a finite family of events.

        theorem Dynamics.Distribution.prob_and_eq {α : Type u_1} [Fintype α] (p : Distribution α) (s t : α → Prop) :
        (p.prob fun (a : α) => s a ∧ t a) = ((1 - p.prob fun (a : α) => ¬s a) - p.prob fun (a : α) => ¬t a) + p.prob fun (a : α) => ¬s a ∧ ¬t a

        Inclusion–exclusion for two events, through their complements.

        theorem Dynamics.Distribution.prob_le_expect_div {α : Type u_1} [Fintype α] (p : Distribution α) (X : α → ℝ) (hX : ∀ (a : α), 0 ≤ X a) {c : ℝ} (hc : 0 < c) :
        (p.prob fun (a : α) => c ≤ X a) ≤ p.expect X / c

        Markov's inequality: P(c ≤ X) ≤ 𝔼X / c for X ≥ 0 and c > 0. The uniform case is avg_markov.

        theorem Dynamics.Distribution.markov_sq {α : Type u_1} [Fintype α] (p : Distribution α) (Z : α → ℝ) {c : ℝ} (hc : 0 < c) :
        (p.prob fun (a : α) => c ≤ |Z a|) ≤ (p.expect fun (a : α) => Z a ^ 2) / c ^ 2

        Markov's inequality on the square (the core of Chebyshev's inequality): P(c ≤ |Z|) ≤ 𝔼[Z²] / c² for c > 0.

        noncomputable def Dynamics.Distribution.uniform (α : Type u_4) [Fintype α] [Nonempty α] :

        Uniform distribution, available precisely when the sample type is nonempty.

        Equations
        Instances For
          theorem Dynamics.Distribution.uniform_expect {α : Type u_1} [Fintype α] [Nonempty α] (f : α → ℝ) :
          (uniform α).expect f = avg f
          noncomputable def Dynamics.Distribution.point {α : Type u_1} [Fintype α] (a : α) :

          Point mass.

          Equations
          Instances For
            @[simp]
            theorem Dynamics.Distribution.point_expect {α : Type u_1} [Fintype α] (a : α) (f : α → ℝ) :
            (point a).expect f = f a
            noncomputable def Dynamics.Distribution.bernoulli (p : ℝ) (h0 : 0 ≤ p) (h1 : p ≤ 1) :

            A biased coin: true with probability p.

            Equations
            Instances For
              noncomputable def Dynamics.Distribution.map {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] (p : Distribution α) (f : α → β) :

              Transport a distribution along a function, summing over its fibers.

              Equations
              • p.map f = { weight := fun (b : β) => ∑ a : α, if f a = b then p.weight a else 0, nonneg := ⋯, sum_one := ⋯ }
              Instances For
                theorem Dynamics.Distribution.map_expect {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] (p : Distribution α) (f : α → β) (g : β → ℝ) :
                (p.map f).expect g = p.expect fun (a : α) => g (f a)
                theorem Dynamics.Distribution.prob_map {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] (p : Distribution α) (f : α → β) (s : β → Prop) :
                (p.map f).prob s = p.prob fun (a : α) => s (f a)

                The probability of an event under p.map f is that of its preimage under p.

                theorem Dynamics.Distribution.map_weight_pos {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] (p : Distribution α) (f : α → β) (a : α) (ha : 0 < p.weight a) :
                0 < (p.map f).weight (f a)

                A point of positive weight is carried to its image with positive weight (it replaces Moran.map_weight_pos).

                noncomputable def Dynamics.Distribution.independent {α : Type u_1} {ι : Type u_3} [Fintype α] [Fintype ι] [DecidableEq ι] (p : ι → Distribution α) :
                Distribution (ι → α)

                Independent product of a finite family of distributions.

                Equations
                Instances For
                  theorem Dynamics.Distribution.independent_expect_prod {α : Type u_1} {ι : Type u_3} [Fintype α] [Fintype ι] [DecidableEq ι] (p : ι → Distribution α) (f : ι → α → ℝ) :
                  ((independent p).expect fun (x : ι → α) => ∏ i : ι, f i (x i)) = ∏ i : ι, (p i).expect (f i)
                  theorem Dynamics.Distribution.independent_expect_eval {α : Type u_1} {ι : Type u_3} [Fintype α] [Fintype ι] [DecidableEq ι] (p : ι → Distribution α) (i : ι) (f : α → ℝ) :
                  ((independent p).expect fun (x : ι → α) => f (x i)) = (p i).expect f