`ProbDist`

definition

show as: view math explainer →

module: IndisputableMonolith.Information.ShannonEntropy
domain: Information
line: 48 · github
papers citing: none yet

open explainer

Generate a durable explainer page for this declaration.

open lean source

IndisputableMonolith.Information.ShannonEntropy on GitHub at line 48.

browse module

All declarations in this module, on Recognition.

explainer page

Tracked in the explainer inventory; generation is lazy so crawlers do not trigger LLM jobs.

open explainer

depends on

used by

formal source

  45/-! ## Probability Distributions -/
  46
  47/-- A discrete probability distribution over n outcomes. -/
  48structure ProbDist (n : ℕ) where
  49  /-- Probabilities for each outcome. -/
  50  probs : Fin n → ℝ
  51  /-- All probabilities are non-negative. -/
  52  nonneg : ∀ i, probs i ≥ 0
  53  /-- Probabilities sum to 1. -/
  54  normalized : (Finset.univ.sum probs) = 1
  55
  56/-- The uniform distribution. -/
  57noncomputable def uniform (n : ℕ) (hn : n > 0) : ProbDist n := {
  58  probs := fun _ => 1 / n,
  59  nonneg := fun _ => by positivity,
  60  normalized := by simp [Finset.sum_const, Finset.card_fin]; field_simp
  61}
  62
  63/-! ## Shannon Entropy -/
  64
  65/-- Shannon entropy: H = -Σ p_i log(p_i).
  66    We use natural logarithm; for bits, divide by log(2). -/
  67noncomputable def shannonEntropy {n : ℕ} (d : ProbDist n) : ℝ :=
  68  -(Finset.univ.sum fun i =>
  69    if d.probs i > 0 then d.probs i * Real.log (d.probs i)
  70    else 0)
  71
  72/-- **THEOREM**: Entropy is non-negative. -/
  73theorem entropy_nonneg {n : ℕ} (d : ProbDist n) :
  74    shannonEntropy d ≥ 0 := by
  75  unfold shannonEntropy
  76  simp only [neg_nonneg]
  77  apply Finset.sum_nonpos
  78  intro i _

papers checked against this theorem

No papers in the current corpus map onto this theorem yet.