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 #
ProbabilityTheory.countVec: how often each colour occurs in a sequence.ProbabilityTheory.polyaUrnPredictive: the probability of each colour on the next draw.ProbabilityTheory.polyaUrnProb: the probability of a sequence with given counts.ProbabilityTheory.polyaUrn θ n: the law of the firstndraws.
Main statements #
ProbabilityTheory.polyaUrnProb_add: conjugacy, the urn after the countsxis the urn with weightsθ + x.ProbabilityTheory.polyaUrn_real_singleton: the probability of a sequence.ProbabilityTheory.polyaUrnProb_eq_prod_Gamma_div: that probability in Gamma functions.ProbabilityTheory.exchangeable_polyaUrn: the drawn sequence is exchangeable.
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 #
- The frequencies of the colours among the draws converge almost surely to a limit with the
Dirichlet law; the urn as a Dirichlet mixture of independent draws is in
Linglib.Core.Probability.Distributions.Dirichlet. - With
mcolours of weightκ, the partition of the draws by colour is the Pitman–Yor partition with discount-κand concentrationm κ.
References #
Count vectors #
The count vector of a sequence records how often each colour occurs in it.
Equations
- ProbabilityTheory.countVec s c = {i : Fin n | s i = c}.card
Instances For
The prediction rule and the probability of a sequence #
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
- ProbabilityTheory.polyaUrnPredictive θ x c = (θ c + ↑(x c)) / (∑ i : α, θ i + ∑ i : α, ↑(x i))
Instances For
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
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.
After the counts x, the urn with weights θ + x predicts as the original urn does after the
counts x + y.
Drawing colour c multiplies the probability of the counts by the probability of drawing
c.
The prediction rule is a probability on the colours.
Merging all colours but the first gives a two-colour urn, and given its counts the remaining colours are drawn from their own urn.
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 #
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
The Pólya urn: the law of the first n draws from the urn with weights θ.
Equations
Instances For
The sequence drawn from a Pólya urn is exchangeable ([Pit06] Exercise 2.2.2).
Under the same positive weight on every colour, the most probable sequences of n draws from
the Pólya urn are the constant ones.