Documentation

PolyFun.Control.Monad.Measure.Uniform

Uniform output measures #

EvalDist.IsUniformOn mx s states that the computation mx is a uniform draw from the set s: in every measurable structure on its outputs with measurable singletons, its output measure is Mathlib's ProbabilityTheory.uniformOn s. EvalDist.IsUniform mx is the case s = Set.univ. The predicate names no sampler, so it applies to a computation in any monad with a measure semantics. On a finite type the measurable structure is irrelevant, and one output measure suffices to establish the predicate (EvalDist.IsUniformOn.of_evalDist_eq).

Main statements #

Under lawful semantics:

Event probabilities and equality in distribution are stated for outputs in Type.

structure EvalDist.IsUniformOn {m : Type u → Type v} [EvalDistSemantics m] {α : Type u} (mx : m α) (s : Set α) :

The computation mx is a uniform draw from s: in every measurable structure on its outputs with measurable singletons, its output measure is the uniform measure on s. The uniform measure on an infinite set is zero, so a uniform draw from an infinite set always fails.

Instances For
    @[reducible, inline]
    abbrev EvalDist.IsUniform {m : Type u → Type v} [EvalDistSemantics m] {α : Type u} (mx : m α) :

    The computation mx is a uniform draw from all of its output type.

    Equations
    Instances For
      theorem EvalDist.IsUniformOn.of_evalDist_eq {m : Type u → Type v} [EvalDistSemantics m] {α : Type u} {mx : m α} {s : Set α} [Finite α] [hα : MeasurableSpace α] [hs : MeasurableSingletonClass α] (h : evalDist mx = ProbabilityTheory.uniformOn s) :

      On a finite type, the output measure in one structure with measurable singletons determines uniformity, because every such structure is discrete.

      On a finite type, uniformity is the uniform output measure in any one structure with measurable singletons.

      theorem EvalDist.IsUniformOn.map_of_injOn {m : Type u → Type v} [EvalDistSemantics m] {α β : Type u} {mx : m α} {s : Set α} [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] (h : IsUniformOn mx s) {f : α → β} (hf : Set.InjOn f s) :
      IsUniformOn (f <$> mx) (f '' s)

      A map injective on s turns a uniform draw from s into a uniform draw from the image of s.

      theorem EvalDist.IsUniformOn.prFail_eq_zero {m : Type u → Type v} [EvalDistSemantics m] {α : Type u} {mx : m α} {s : Set α} [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] (h : IsUniformOn mx s) (hs : s.Finite) (hne : s.Nonempty) :
      prFail mx = 0

      A uniform draw from a finite nonempty set never fails.

      theorem EvalDist.IsUniformOn.prFail_eq_one {m : Type u → Type v} [EvalDistSemantics m] {α : Type u} {mx : m α} {s : Set α} [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] (h : IsUniformOn mx s) (hs : s.Infinite ∨ s = ∅) :
      prFail mx = 1

      A uniform draw from an infinite or empty set always fails.

      theorem EvalDist.IsUniform.map_of_bijective {m : Type u → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α β : Type u} {mx : m α} (h : IsUniform mx) {f : α → β} (hf : Function.Bijective f) :
      IsUniform (f <$> mx)

      A bijection keeps a uniform draw uniform.

      theorem EvalDist.IsUniform.map_of_injective {m : Type u → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α β : Type u} {mx : m α} (h : IsUniform mx) {f : α → β} (hf : Function.Injective f) :

      An injection turns a uniform draw into a uniform draw from its range.

      theorem EvalDist.IsUniform.map_equiv {m : Type u → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α β : Type u} {mx : m α} (h : IsUniform mx) (e : α ≃ β) :
      IsUniform (⇑e <$> mx)

      An equivalence keeps a uniform draw uniform.

      theorem EvalDist.IsUniform.prFail_eq_zero {m : Type u → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type u} {mx : m α} [Finite α] [Nonempty α] (h : IsUniform mx) :
      prFail mx = 0

      A uniform draw from a finite nonempty type never fails.

      theorem EvalDist.IsUniform.pair {m : Type u → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α β : Type u} {mx : m α} [Finite α] [Finite β] {my : m β} (hx : IsUniform mx) (hy : IsUniform my) :
      IsUniform do let x ← mx let y ← my pure (x, y)

      Two independent uniform draws from finite types are a uniform draw from their product.

      Events and equality in distribution #

      theorem EvalDist.IsUniformOn.evalDistEq {m : Type → Type v} {m' : Type → Type v'} [EvalDistSemantics m] [EvalDistSemantics m'] [Monad m] [Monad m'] [LawfulMonad m] [LawfulMonad m'] [LawfulEvalDistSemantics m] [LawfulEvalDistSemantics m'] {α : Type} {mx : m α} {s : Set α} {my : m' α} (hx : IsUniformOn mx s) (hy : IsUniformOn my s) :

      Two uniform draws from the same set are equal in distribution.

      theorem EvalDist.IsUniformOn.prEvent_eq {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} {s : Finset α} (h : IsUniformOn mx ↑s) (p : α → Prop) [DecidablePred p] :
      prEvent (p <$> mx) = ↑(Finset.filter p s).card / ↑s.card

      An event of a uniform draw from a finite set has the probability of the fraction of the set that satisfies it.

      theorem EvalDist.IsUniformOn.prEvent_eq_singleton {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} [DecidableEq α] {s : Finset α} (h : IsUniformOn mx ↑s) (a : α) :
      prEvent ((fun (x : α) => x = a) <$> mx) = if a ∈ s then (↑s.card)⁻¹ else 0

      A uniform draw from a finite set returns a given element of the set with probability 1 / #s, and an element outside the set with probability zero.

      theorem EvalDist.IsUniformOn.prEvent_eq_zero_iff {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} {s : Set α} (h : IsUniformOn mx s) (hs : s.Finite) (p : α → Prop) :
      prEvent (p <$> mx) = 0 ↔ ∀ x ∈ s, ¬p x

      An event of a uniform draw from a finite set has probability zero exactly when no element of the set satisfies it.

      theorem EvalDist.IsUniformOn.prEvent_pos_iff {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} {s : Set α} (h : IsUniformOn mx s) (hs : s.Finite) (p : α → Prop) :
      0 < prEvent (p <$> mx) ↔ ∃ x ∈ s, p x

      An event of a uniform draw from a finite set has positive probability exactly when some element of the set satisfies it.

      theorem EvalDist.IsUniformOn.prEvent_eq_one_iff {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} {s : Set α} (h : IsUniformOn mx s) (hs : s.Finite) (hne : s.Nonempty) (p : α → Prop) :
      prEvent (p <$> mx) = 1 ↔ ∀ x ∈ s, p x

      An event of a uniform draw from a finite nonempty set has probability one exactly when every element of the set satisfies it.

      theorem EvalDistEq.isUniformOn_iff {m : Type → Type v} {m' : Type → Type v'} [EvalDistSemantics m] [EvalDistSemantics m'] [Monad m] [Monad m'] [LawfulMonad m] [LawfulMonad m'] [LawfulEvalDistSemantics m] [LawfulEvalDistSemantics m'] {α : Type} {mx : m α} {s : Set α} {my : m' α} (h : EvalDistEq mx my) :

      Equality in distribution preserves uniformity.

      theorem EvalDist.IsUniform.prEvent_eq {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} [Fintype α] (h : IsUniform mx) (p : α → Prop) [DecidablePred p] :

      An event of a uniform draw from a finite type has the probability of the fraction of outputs that satisfy it.

      theorem EvalDist.IsUniform.prEvent_eq_singleton {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} [Fintype α] (h : IsUniform mx) (a : α) :
      prEvent ((fun (x : α) => x = a) <$> mx) = (↑(Fintype.card α))⁻¹

      A uniform draw from a finite type returns any given output with probability 1 / |α|.

      theorem EvalDist.IsUniform.prEvent_eq_zero_iff {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} [Finite α] (h : IsUniform mx) (p : α → Prop) :
      prEvent (p <$> mx) = 0 ↔ ∀ (x : α), ¬p x

      An event of a uniform draw from a finite type has probability zero exactly when no output satisfies it.

      theorem EvalDist.IsUniform.prEvent_pos_iff {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} [Finite α] (h : IsUniform mx) (p : α → Prop) :
      0 < prEvent (p <$> mx) ↔ ∃ (x : α), p x

      An event of a uniform draw from a finite type has positive probability exactly when some output satisfies it.

      theorem EvalDist.IsUniform.prEvent_eq_one_iff {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α : Type} {mx : m α} [Finite α] [Nonempty α] (h : IsUniform mx) (p : α → Prop) :
      prEvent (p <$> mx) = 1 ↔ ∀ (x : α), p x

      An event of a uniform draw from a finite nonempty type has probability one exactly when every output satisfies it.

      theorem EvalDist.IsUniform.prEvent_comp_of_bijective {m : Type → Type v} {m' : Type → Type v'} [EvalDistSemantics m] [EvalDistSemantics m'] [Monad m] [Monad m'] [LawfulMonad m] [LawfulMonad m'] [LawfulEvalDistSemantics m] [LawfulEvalDistSemantics m'] {α β : Type} {mx : m α} {my : m' β} (hx : IsUniform mx) (hy : IsUniform my) {f : α → β} (hf : Function.Bijective f) (p : β → Prop) :
      prEvent ((fun (x : α) => p (f x)) <$> mx) = prEvent (p <$> my)

      A bijection between the outputs of two uniform draws transports their events.

      theorem EvalDist.IsUniform.evalDistEq_bind_comp {m : Type → Type v} [EvalDistSemantics m] [Monad m] [LawfulMonad m] [LawfulEvalDistSemantics m] {α β γ : Type} {mx : m α} {my : m β} (hx : IsUniform mx) (hy : IsUniform my) {e : α → β} (he : Function.Bijective e) (f : β → m γ) :
      EvalDistEq (do let x ← mx f (e x)) (my >>= f)

      Reindexing a uniform draw by a bijection onto the outputs of another uniform draw does not change the distribution of a continuation.