Documentation

Linglib.Core.Probability.Combinatorics.PolyaUrn

The Pólya urn #

This file defines the Pólya urn and the law of its draws. The urn holds balls of the colours in α with positive weights θ. After draws in which colour c came up x c times, the next draw is c with probability proportional to θ c + x c, and the law of the first n draws is the sequence law of this prediction rule. The probability of a sequence depends only on its counts, so the sequence is exchangeable. It is a ratio of rising factorials, and in Gamma functions the Dirichlet-multinomial formula.

Main definitions #

Main statements #

Implementation notes #

The weights are a plain function θ : α → ℝ, and results that need them positive assume it. One draw of c adds Pi.single c 1 to the counts, so each step of a sequence is conjugacy there.

TODO #

References #

Count vectors #

def ProbabilityTheory.countVec {α : Type u_1} [DecidableEq α] {n : ℕ} (s : Fin n → α) (c : α) :
ℕ

The count vector of a sequence records how often each colour occurs in it.

Equations
Instances For
    @[simp]
    theorem ProbabilityTheory.countVec_zero {α : Type u_1} [DecidableEq α] (s : Fin 0 → α) :
    countVec s = 0
    theorem ProbabilityTheory.countVec_cons {α : Type u_1} [DecidableEq α] {n : ℕ} (c : α) (s : Fin n → α) :
    countVec (Fin.cons c s) = countVec s + Pi.single c 1
    theorem ProbabilityTheory.countVec_snoc {α : Type u_1} [DecidableEq α] {n : ℕ} (c : α) (s : Fin n → α) :
    countVec (Fin.snoc s c) = countVec s + Pi.single c 1
    theorem ProbabilityTheory.countVec_comp_perm {α : Type u_1} [DecidableEq α] {n : ℕ} (s : Fin n → α) (σ : Equiv.Perm (Fin n)) :
    countVec (s ∘ ⇑σ) = countVec s
    theorem ProbabilityTheory.sum_countVec {α : Type u_1} [DecidableEq α] {n : ℕ} [Fintype α] (s : Fin n → α) :
    ∑ c : α, countVec s c = n

    The prediction rule and the probability of a sequence #

    noncomputable def ProbabilityTheory.polyaUrnPredictive {α : Type u_1} [Fintype α] (θ : α → ℝ) (x : α → ℕ) (c : α) :
    ℝ

    The probability that the urn with weights θ draws colour c after draws with counts x, (θ c + x c) / (∑ θ + ∑ x) ([Pit06] Exercise 2.2.2).

    Equations
    Instances For
      noncomputable def ProbabilityTheory.polyaUrnProb {α : Type u_1} [Fintype α] (θ : α → ℝ) (x : α → ℕ) :
      ℝ

      The probability that the urn with weights θ draws a given sequence with counts x.

      Equations
      • ProbabilityTheory.polyaUrnProb θ x = (∏ c : α, Polynomial.eval (θ c) (ascPochhammer ℝ (x c))) / Polynomial.eval (∑ c : α, θ c) (ascPochhammer ℝ (∑ c : α, x c))
      Instances For
        @[simp]
        theorem ProbabilityTheory.polyaUrnProb_zero {α : Type u_1} [Fintype α] (θ : α → ℝ) :
        polyaUrnProb θ 0 = 1
        theorem ProbabilityTheory.polyaUrnPredictive_zero {α : Type u_1} [Fintype α] (θ : α → ℝ) (c : α) :
        polyaUrnPredictive θ 0 c = θ c / ∑ i : α, θ i
        theorem ProbabilityTheory.polyaUrnProb_single {α : Type u_1} [Fintype α] (θ : α → ℝ) [DecidableEq α] (c : α) :
        polyaUrnProb θ (Pi.single c 1) = polyaUrnPredictive θ 0 c
        theorem ProbabilityTheory.polyaUrnProb_add {α : Type u_1} [Fintype α] (θ : α → ℝ) (x y : α → ℕ) :
        polyaUrnProb θ (x + y) = polyaUrnProb θ x * polyaUrnProb (θ + fun (c : α) => ↑(x c)) y

        The probability of the counts x + y is the probability of x times the probability of y under the urn whose weights are raised by x.

        theorem ProbabilityTheory.polyaUrnPredictive_add {α : Type u_1} [Fintype α] (θ : α → ℝ) (x y : α → ℕ) :
        polyaUrnPredictive (θ + fun (c : α) => ↑(x c)) y = polyaUrnPredictive θ (x + y)

        After the counts x, the urn with weights θ + x predicts as the original urn does after the counts x + y.

        theorem ProbabilityTheory.polyaUrnProb_add_single {α : Type u_1} [Fintype α] (θ : α → ℝ) [DecidableEq α] (x : α → ℕ) (c : α) :
        polyaUrnProb θ (x + Pi.single c 1) = polyaUrnProb θ x * polyaUrnPredictive θ x c

        Drawing colour c multiplies the probability of the counts by the probability of drawing c.

        theorem ProbabilityTheory.polyaUrnProb_countVec_snoc {α : Type u_1} [Fintype α] (θ : α → ℝ) [DecidableEq α] (c : α) {n : ℕ} (s : Fin n → α) :
        polyaUrnProb θ (countVec (Fin.snoc s c)) = polyaUrnProb θ (countVec s) * polyaUrnPredictive θ (countVec s) c
        theorem ProbabilityTheory.polyaUrnProb_countVec_cons {α : Type u_1} [Fintype α] (θ : α → ℝ) [DecidableEq α] (c : α) {n : ℕ} (s : Fin n → α) :
        polyaUrnProb θ (countVec (Fin.cons c s)) = polyaUrnProb θ (countVec s) * polyaUrnPredictive θ (countVec s) c
        theorem ProbabilityTheory.polyaUrnProb_comp_equiv {α : Type u_1} [Fintype α] (θ : α → ℝ) {β : Type u_2} [Fintype β] (e : β ≃ α) (x : α → ℕ) :
        polyaUrnProb (θ ∘ ⇑e) (x ∘ ⇑e) = polyaUrnProb θ x
        theorem ProbabilityTheory.polyaUrnProb_eq_prod_pow_of_sum_le_one {α : Type u_1} [Fintype α] (θ : α → ℝ) {x : α → ℕ} (hx : ∑ c : α, x c ≤ 1) :
        polyaUrnProb θ x = ∏ c : α, polyaUrnPredictive θ 0 c ^ x c
        theorem ProbabilityTheory.polyaUrnPredictive_nonneg {α : Type u_1} [Fintype α] {θ : α → ℝ} (hθ : ∀ (i : α), 0 ≤ θ i) (x : α → ℕ) (c : α) :
        0 ≤ polyaUrnPredictive θ x c
        theorem ProbabilityTheory.polyaUrnPredictive_pos {α : Type u_1} [Fintype α] {θ : α → ℝ} (hθ : ∀ (i : α), 0 < θ i) (x : α → ℕ) (c : α) :
        theorem ProbabilityTheory.sum_polyaUrnPredictive {α : Type u_1} [Fintype α] {θ : α → ℝ} [Nonempty α] (hθ : ∀ (i : α), 0 < θ i) (x : α → ℕ) :
        ∑ c : α, polyaUrnPredictive θ x c = 1

        The prediction rule is a probability on the colours.

        theorem ProbabilityTheory.polyaUrnProb_pos {α : Type u_1} [Fintype α] {θ : α → ℝ} (hθ : ∀ (i : α), 0 < θ i) (x : α → ℕ) :
        0 < polyaUrnProb θ x
        theorem ProbabilityTheory.polyaUrnProb_eq_mul_tail {n : ℕ} {θ : Fin (n + 2) → ℝ} (hθ : ∀ (i : Fin (n + 2)), 0 < θ i) (x : Fin (n + 2) → ℕ) :
        polyaUrnProb θ x = Polynomial.eval (θ 0) (ascPochhammer ℝ (x 0)) * Polynomial.eval (∑ i : Fin (n + 1), θ i.succ) (ascPochhammer ℝ (∑ i : Fin (n + 1), x i.succ)) / Polynomial.eval (θ 0 + ∑ i : Fin (n + 1), θ i.succ) (ascPochhammer ℝ (x 0 + ∑ i : Fin (n + 1), x i.succ)) * polyaUrnProb (Fin.tail θ) (Fin.tail x)

        Merging all colours but the first gives a two-colour urn, and given its counts the remaining colours are drawn from their own urn.

        theorem ProbabilityTheory.polyaUrnProb_eq_prod_Gamma_div {α : Type u_1} [Fintype α] {θ : α → ℝ} [Nonempty α] (hθ : ∀ (c : α), 0 < θ c) (x : α → ℕ) :
        polyaUrnProb θ x = (∏ c : α, Real.Gamma (θ c + ↑(x c)) / Real.Gamma (θ c)) / (Real.Gamma (∑ c : α, θ c + ↑(∑ c : α, x c)) / Real.Gamma (∑ c : α, θ c))

        The probability of a sequence with counts x in Gamma functions: each rising factorial (a)_m of polyaUrnProb is the ratio Γ(a + m) / Γ(a).

        The law of the draws #

        noncomputable def ProbabilityTheory.polyaUrnRule {α : Type u_1} [DecidableEq α] [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] (θ : α → ℝ) (n : ℕ) :
        Kernel (Fin n → α) α

        The Pólya urn prediction rule as a kernel: after the draws s, colour c is drawn with probability polyaUrnPredictive θ (countVec s) c.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          noncomputable def ProbabilityTheory.polyaUrn {α : Type u_1} [DecidableEq α] [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] (θ : α → ℝ) (n : ℕ) :
          MeasureTheory.Measure (Fin n → α)

          The Pólya urn: the law of the first n draws from the urn with weights θ.

          Equations
          Instances For
            theorem ProbabilityTheory.polyaUrnRule_apply_singleton {α : Type u_1} [DecidableEq α] [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] (θ : α → ℝ) {n : ℕ} (s : Fin n → α) (c : α) :
            ((polyaUrnRule θ n) s) {c} = ENNReal.ofReal (polyaUrnPredictive θ (countVec s) c)
            theorem ProbabilityTheory.isMarkovKernel_polyaUrnRule {α : Type u_1} [DecidableEq α] [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] {θ : α → ℝ} [Nonempty α] (hθ : ∀ (i : α), 0 < θ i) (n : ℕ) :
            IsMarkovKernel (polyaUrnRule θ n)
            theorem ProbabilityTheory.isProbabilityMeasure_polyaUrn {α : Type u_1} [DecidableEq α] [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] {θ : α → ℝ} [Nonempty α] (hθ : ∀ (i : α), 0 < θ i) (n : ℕ) :
            MeasureTheory.IsProbabilityMeasure (polyaUrn θ n)
            theorem ProbabilityTheory.polyaUrn_singleton {α : Type u_1} [DecidableEq α] [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] {θ : α → ℝ} [Nonempty α] (hθ : ∀ (i : α), 0 < θ i) {n : ℕ} (s : Fin n → α) :
            (polyaUrn θ n) {s} = ENNReal.ofReal (polyaUrnProb θ (countVec s))
            theorem ProbabilityTheory.polyaUrn_real_singleton {α : Type u_1} [DecidableEq α] [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] {θ : α → ℝ} [Nonempty α] (hθ : ∀ (i : α), 0 < θ i) {n : ℕ} (s : Fin n → α) :
            (polyaUrn θ n).real {s} = polyaUrnProb θ (countVec s)
            theorem ProbabilityTheory.exchangeable_polyaUrn {α : Type u_1} [DecidableEq α] [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] {θ : α → ℝ} [Nonempty α] (hθ : ∀ (i : α), 0 < θ i) (n : ℕ) :

            The sequence drawn from a Pólya urn is exchangeable ([Pit06] Exercise 2.2.2).

            theorem ProbabilityTheory.argmax_polyaUrn_const {α : Type u_1} [DecidableEq α] [Fintype α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] {a : ℝ} (ha : 0 < a) (n : ℕ) :
            (Finset.univ.argmax fun (s : Fin n → α) => (polyaUrn (fun (x : α) => a) n) {s}) = Finset.image (fun (c : α) (x : Fin n) => c) Finset.univ

            Under the same positive weight on every colour, the most probable sequences of n draws from the Pólya urn are the constant ones.