/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilThe Courtade–Kumar (most informative Boolean function) conjecture
Let $X$ be uniform on the Boolean cube ${0,1}^n$. Independently of $X$, let the coordinates of $Z$ be i.i.d. Bernoulli random variables with parameter $p \in [0, 1]$, and put $Y = X \oplus Z$, so that $Y$ is the output of $n$ independent binary symmetric channels with crossover probability $p$ on input $X$. The Courtade–Kumar conjecture asserts that for every Boolean function $f : {0,1}^n \to {0,1}$,
$I(f(X); Y) \le 1 - h(p)$,
where mutual information and binary entropy are measured in bits.
The usual restriction to $p \in [0, 1/2]$ is equivalent to the range used here. For $p > 1/2$, complementing every output bit replaces $Z$ by its bitwise complement, which is i.i.d. Bernoulli($1 - p$) noise still independent of $X$; this bijective relabelling of the output preserves $I(f(X); Y)$, and $h(1 - p) = h(p)$.
This file contains two formulations:
CourtadeKumar.courtade_kumar is the elementary finite-sum statement used by the external
Lean proof and its comparator check. Its definitions and statement are retained unchanged.
CourtadeKumar.variants.courtade_kumar_random_variable is the random-variable formulation.
Its product-law hypothesis specifies a uniform input and independent i.i.d. Bernoulli channel
noise, and its conclusion is about the mutual information of the actual random variables.
CourtadeKumar.courtade_kumar_iff_random_variable proves that the two formulations are
equivalent, without using either research statement. Shannon entropy and mutual information of
finite-valued random variables are defined in
FormalConjecturesForMathlib.InformationTheory.FiniteEntropy.
For $n \ge 1$, coordinate dictators attain the bound: $I(X_i; Y) = I(X_i; Y_i) = 1 - h(p)$, since
the other output coordinates are independent of $(X_i, Y_i)$. The test mutualInfo_dictator
checks $n = 1$.
References:
[CK14] T. A. Courtade and G. R. Kumar, Which Boolean functions maximize mutual information on noisy inputs?, IEEE Trans. Inf. Theory 60 (2014), no. 8, 4515–4525.
Independent work on the conjecture from September 2026, in alphabetical order:
[CGJLMNW26] Z. Chen, A. Gohari, A. Javanmard, H. Lin, V. Mirrokni, C. Nair, D. P. Woodruff, A Proof of the Most Informative Boolean Function Conjecture, arXiv:2609.24931. A Lean 4 formalisation of the proof is at https://github.com/dpwoodru/general-courtade-kumar-lean.
[KS26] D. Kramer and M. Saglam, On the most informative Boolean function under noise, manuscript, https://github.com/deepinfra/courtade-kumar.
[KT26] Vu Khac Ky and Tuan Tran, Dictators are most informative, arXiv:2609.24184. See also their follow-up Stability of the Courtade–Kumar inequality, arXiv:2609.31797.
[MB26] H. Mahdavifar and A. Beirami, The Most Informative Bit and Beyond: A Proof of the Courtade–Kumar Conjecture and Multibit Extensions, arXiv:2609.26444.
@[expose] public sectionnamespace CourtadeKumaropen scoped BigOperators ENNRealopen MeasureTheoryThe elementary formulation
The probability interpretations of bsc, jointProb and mutualInfo assume $0 \le p \le 1$, and
entropy q is Shannon entropy when the masses $q$ are nonnegative and sum to one; otherwise these
definitions are just total real-valued expressions.
The Boolean cube ${0,1}^n$, with bits represented by Bool.
abbrev Cube (n : ℕ) := Fin n → BoolBinary entropy in bits, $h(p) = -p \log_2 p - (1 - p) \log_2 (1 - p)$, with $h(0) = h(1) = 0$.
noncomputable def binEntropyBits (p : ℝ) : ℝ := Real.binEntropy p / Real.log 2Transition probability of $n$ independent binary symmetric channels with crossover probability $p$: $P(Y = y \mid X = x) = \prod_i q_i$, where $q_i = 1 - p$ if $x_i = y_i$ and $q_i = p$ otherwise.
noncomputable def bsc {n : ℕ} (p : ℝ) (x y : Cube n) : ℝ :=
∏ i, if x i = y i then 1 - p else pThe joint probability $P(f(X) = b, Y = y)$ for $X$ uniform on the cube and $Y$ the channel output on input $X$.
noncomputable def jointProb {n : ℕ} (f : Cube n → Bool) (p : ℝ) (b : Bool) (y : Cube n) : ℝ :=
(2 : ℝ) ^ (-(n : ℤ)) * ∑ x, if f x = b then bsc p x y else 0Shannon entropy in bits of a probability mass function $q$ on a finite type.
noncomputable def entropy {α : Type*} [Fintype α] (q : α → ℝ) : ℝ :=
(∑ a, Real.negMulLog (q a)) / Real.log 2The mutual information $I(f(X); Y) = H(f(X)) + H(Y) - H(f(X), Y)$, in bits.
noncomputable def mutualInfo {n : ℕ} (f : Cube n → Bool) (p : ℝ) : ℝ :=
entropy (fun b => ∑ y, jointProb f p b y) + entropy (fun y => ∑ b, jointProb f p b y) -
entropy (fun z : Bool × Cube n => jointProb f p z.1 z.2)The Courtade–Kumar conjecture. For every $n$, every Boolean function $f$ on ${0,1}^n$ and every crossover probability $p \in [0, 1]$, $I(f(X); Y) \le 1 - h(p)$.
@[category research solved, AMS 94,
formal_proof using lean4 at "https://github.com/dpwoodru/general-courtade-kumar-lean/blob/c3599c05181ad357331b701edf8fd8ec75c88305/verification/comparator/CKChallenge/Solution.lean#L6"]
theorem courtade_kumar (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) :
mutualInfo f p ≤ 1 - binEntropyBits p := n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ mutualInfo f p ≤ 1 - binEntropyBits p
All goals completed! 🐙The random-variable formulation
Coordinatewise xor on the Boolean cube.
def cubeXor {n : ℕ} (x z : Cube n) : Cube n :=
fun i => Bool.xor (x i) (z i)The joint law of a uniform input and independent i.i.d. Bernoulli channel noise.
On this probability space the input and noise are the two coordinate projections.
noncomputable def inputNoiseLaw (n : ℕ) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) :
Measure (Cube n × Cube n) :=
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun _ : Fin n =>
ProbabilityTheory.bernoulliMeasure true false (⟨p, hp₀, hp₁⟩ : unitInterval))@[category API, AMS 94]
instance (n : ℕ) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) :
IsProbabilityMeasure (inputNoiseLaw n p hp₀ hp₁) := n:ℕp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ IsProbabilityMeasure (inputNoiseLaw n p hp₀ hp₁)
n:ℕp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ IsProbabilityMeasure
((PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩))
All goals completed! 🐙namespace variantsThe Courtade–Kumar conjecture, in random-variable form.
The pushforward in the hypothesis is the joint distribution of $(X, Z)$. The uniform measure on
Cube n is the law of $n$ i.i.d. Bernoulli($1/2$) bits. The product law makes the coordinates of
$Z$ i.i.d. Bernoulli($p$) and makes the whole noise vector independent of $X$. In
bernoulliMeasure true false p, true has probability $p$ and denotes a flip.
Conditional on $X$, $Y = X \oplus Z$ flips each input coordinate independently with probability $p$: this is the memoryless binary symmetric channel with crossover probability $p$ from $X$ to $Y$. Every Boolean function is allowed, including constants. All maps between these finite discrete types are measurable, so $f \circ X$ and $Y$ are measurable. The conclusion is $I(f(X); Y) \le 1 - h(p)$ in bits, for the entire output vector $Y$.
The linked proof proves the elementary statement CourtadeKumar.courtade_kumar, and
CourtadeKumar.courtade_kumar_iff_random_variable transfers it to this formulation.
@[category research solved, AMS 94,
formal_proof using lean4 at "https://github.com/dpwoodru/general-courtade-kumar-lean/blob/c3599c05181ad357331b701edf8fd8ec75c88305/verification/comparator/CKChallenge/Solution.lean#L6"]
theorem courtade_kumar_random_variable :
∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1)
(Ω : Type) [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(X Z : Ω → Cube n),
Measurable X →
Measurable Z →
μ.map (fun ω => (X ω, Z ω)) =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun _ : Fin n =>
ProbabilityTheory.bernoulliMeasure true false
(⟨p, hp₀, hp₁⟩ : unitInterval)) →
let Y : Ω → Cube n := fun ω => cubeXor (X ω) (Z ω)
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p := ⊢ ∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
let Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p
All goals completed! 🐙end variantsAPI: equivalence of the formulations
@[category API, AMS 94]
private theorem cubeXor_eq_iff {n : ℕ} (x z y : Cube n) :
cubeXor x z = y ↔ z = cubeXor x y := n:ℕx:Cube nz:Cube ny:Cube n⊢ cubeXor x z = y ↔ z = cubeXor x y
n:ℕx:Cube nz:Cube ny:Cube n⊢ (∀ (x_1 : Fin n), (x x_1 ^^ z x_1) = y x_1) ↔ ∀ (x_1 : Fin n), z x_1 = (x x_1 ^^ y x_1)
exact forall_congr' fun i => n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (x i ^^ z i) = y i ↔ z i = (x i ^^ y i)
n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ z i) = y i ↔ z i = (false ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ z i) = y i ↔ z i = (true ^^ y i) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ z i) = y i ↔ z i = (false ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ z i) = y i ↔ z i = (true ^^ y i) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ false) = y i ↔ false = (true ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = y i ↔ true = (true ^^ y i) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ false) = y i ↔ false = (false ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ true) = y i ↔ true = (false ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ false) = y i ↔ false = (true ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = y i ↔ true = (true ^^ y i) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = false ↔ true = (true ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = true ↔ true = (true ^^ true) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ false) = false ↔ false = (false ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ false) = true ↔ false = (false ^^ true)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ true) = false ↔ true = (false ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ true) = true ↔ true = (false ^^ true)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ false) = false ↔ false = (true ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ false) = true ↔ false = (true ^^ true)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = false ↔ true = (true ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = true ↔ true = (true ^^ true) All goals completed! 🐙@[category API, AMS 94]
private theorem noiseProduct_cubeXor {n : ℕ} (p : ℝ) (x y : Cube n) :
(∏ i, if cubeXor x y i then p else 1 - p) = bsc p x y := n:ℕp:ℝx:Cube ny:Cube n⊢ (∏ i, if cubeXor x y i = true then p else 1 - p) = bsc p x y
n:ℕp:ℝx:Cube ny:Cube n⊢ (∏ i, if cubeXor x y i = true then p else 1 - p) = ∏ i, if x i = y i then 1 - p else p
n:ℕp:ℝx:Cube ny:Cube n⊢ ∀ x_1 ∈ Finset.univ, (if cubeXor x y x_1 = true then p else 1 - p) = if x x_1 = y x_1 then 1 - p else p
n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univ⊢ (if cubeXor x y i = true then p else 1 - p) = if x i = y i then 1 - p else p
n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if false = y i then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if true = y i then 1 - p else p n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if false = y i then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if true = y i then 1 - p else p n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = truehy:y i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if true = false then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = truehy:y i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if true = true then 1 - p else p n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = falsehy:y i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if false = false then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = falsehy:y i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if false = true then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = truehy:y i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if true = false then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = truehy:y i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if true = true then 1 - p else p All goals completed! 🐙The singleton masses of the input/noise product probability space.
n:ℕp:ℝhp₀:0 ≤ php₁:p ≤ 1x:Cube nz:Cube nhB:∀ (b : Bool), ((ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) {b}).toReal = if b = true then p else 1 - phs:{(x, z)} = {x} ×ˢ Set.univ.pi fun i ↦ {z i}⊢ ((PMF.uniformOfFintype (Cube n)).toMeasure {x}).toReal *
∏ i, ((ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) {z i}).toReal =
2 ^ (-↑n) * ∏ i, if z i = true then p else 1 - p
simp [hB, Cube, zpow_neg] All goals completed! 🐙
The joint probability of $(f(X), X \oplus Z)$ on the product probability space is
the elementary jointProb.
@[category API, AMS 94]
private theorem inputNoiseLaw_jointProb (n : ℕ) (f : Cube n → Bool) (p : ℝ)
(hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (b : Bool) (y : Cube n) :
(inputNoiseLaw n p hp₀ hp₁).real
((fun ω : Cube n × Cube n => (f ω.1, cubeXor ω.1 ω.2)) ⁻¹' {(b, y)}) =
jointProb f p b y := by n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube n⊢ (inputNoiseLaw n p hp₀ hp₁).real ((fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)) ⁻¹' {(b, y)}) = jointProb f p b y
classical
have hsum (s : Set (Cube n × Cube n)) :
(inputNoiseLaw n p hp₀ hp₁).real s =
∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0 := by n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube n⊢ (inputNoiseLaw n p hp₀ hp₁).real ((fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)) ⁻¹' {(b, y)}) = jointProb f p b y n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (inputNoiseLaw n p hp₀ hp₁).real ((fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)) ⁻¹' {(b, y)}) = jointProb f p b y
simpa [Finset.sum_filter] using
(sum_measureReal_singleton (μ := inputNoiseLaw n p hp₀ hp₁)
(Finset.univ.filter (fun w => w ∈ s))).symm n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (inputNoiseLaw n p hp₀ hp₁).real ((fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)) ⁻¹' {(b, y)}) = jointProb f p b y n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (inputNoiseLaw n p hp₀ hp₁).real ((fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)) ⁻¹' {(b, y)}) = jointProb f p b y
rw [hsum n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (∑ w, if w ∈ (fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)) ⁻¹' {(b, y)} then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0) =
jointProb f p b y n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (∑ w, if w ∈ (fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)) ⁻¹' {(b, y)} then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0) =
jointProb f p b y] n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (∑ w, if w ∈ (fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)) ⁻¹' {(b, y)} then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0) =
jointProb f p b y
simp only [Fintype.sum_prod_type, Set.mem_preimage, Set.mem_singleton_iff,
Prod.mk.injEq, inputNoiseLaw_real_singleton] n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (∑ x, ∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
jointProb f p b y
unfold jointProb n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (∑ x, ∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
2 ^ (-↑n) * ∑ x, if f x = b then bsc p x y else 0
rw [Finset.mul_sum n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (∑ x, ∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
∑ i, 2 ^ (-↑n) * if f i = b then bsc p i y else 0 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (∑ x, ∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
∑ i, 2 ^ (-↑n) * if f i = b then bsc p i y else 0] n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (∑ x, ∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
∑ i, 2 ^ (-↑n) * if f i = b then bsc p i y else 0
apply Finset.sum_congr rfl n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ ∀ x ∈ Finset.univ,
(∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
2 ^ (-↑n) * if f x = b then bsc p x y else 0
intro x _ n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univ⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
2 ^ (-↑n) * if f x = b then bsc p x y else 0
by_cases h : f x = b pos n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univh:f x = b⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
2 ^ (-↑n) * if f x = b then bsc p x y else 0neg n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univh:¬f x = b⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
2 ^ (-↑n) * if f x = b then bsc p x y else 0
· pos n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univh:f x = b⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
2 ^ (-↑n) * if f x = b then bsc p x y else 0 simp [h, cubeXor_eq_iff, noiseProduct_cubeXor] All goals completed! 🐙
· neg n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)),
(inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univh:¬f x = b⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) =
2 ^ (-↑n) * if f x = b then bsc p x y else 0 simp [h] All goals completed! 🐙Mutual information on the explicit input/noise probability space equals the elementary finite-sum expression.
@[category API, AMS 94]
theorem mutualInformationBits_model_eq (n : ℕ) (f : Cube n → Bool) (p : ℝ)
(hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) :
InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁)
(fun ω : Cube n × Cube n => f ω.1) (fun ω => cubeXor ω.1 ω.2) =
mutualInfo f p := by n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p
let μ := inputNoiseLaw n p hp₀ hp₁ n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p
let T : Cube n × Cube n → Bool × Cube n := fun ω => (f ω.1, cubeXor ω.1 ω.2) n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p
have hT : Measurable T := measurable_of_countable T n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable T⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p
have hν (w : Bool × Cube n) : (μ.map T).real {w} = jointProb f p w.1 w.2 := by
rw [measureReal_def, n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Tw:Bool × Cube n⊢ ((Measure.map T μ) {w}).toReal = jointProb f p w.1 w.2 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Tw:Bool × Cube n⊢ (μ (T ⁻¹' {w})).toReal = jointProb f p w.1 w.2 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p Measure.map_apply hT (measurableSet_singleton w) n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Tw:Bool × Cube n⊢ (μ (T ⁻¹' {w})).toReal = jointProb f p w.1 w.2 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Tw:Bool × Cube n⊢ (μ (T ⁻¹' {w})).toReal = jointProb f p w.1 w.2 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p] n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Tw:Bool × Cube n⊢ (μ (T ⁻¹' {w})).toReal = jointProb f p w.1 w.2 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p
exact inputNoiseLaw_jointProb n f p hp₀ hp₁ w.1 w.2 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p
have hMI : InformationTheory.mutualInformationBits (μ.map T) Prod.fst Prod.snd =
InformationTheory.mutualInformationBits μ (fun ω => f ω.1) (fun ω => cubeXor ω.1 ω.2) :=
InformationTheory.mutualInformationBits_map μ hT measurable_fst measurable_snd n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2hMI:InformationTheory.mutualInformationBits (Measure.map T μ) Prod.fst Prod.snd =
InformationTheory.mutualInformationBits μ (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) =
mutualInfo f p
rw [← hMI, n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2hMI:InformationTheory.mutualInformationBits (Measure.map T μ) Prod.fst Prod.snd =
InformationTheory.mutualInformationBits μ (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2⊢ InformationTheory.mutualInformationBits (Measure.map T μ) Prod.fst Prod.snd = mutualInfo f p n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2hMI:InformationTheory.mutualInformationBits (Measure.map T μ) Prod.fst Prod.snd =
InformationTheory.mutualInformationBits μ (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2⊢ (∑ a, (∑ b, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 +
(∑ b, (∑ a, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 -
(∑ ab, ((Measure.map T μ).real {ab}).negMulLog) / Real.log 2 =
mutualInfo f p InformationTheory.mutualInformationBits_fst_snd n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2hMI:InformationTheory.mutualInformationBits (Measure.map T μ) Prod.fst Prod.snd =
InformationTheory.mutualInformationBits μ (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2⊢ (∑ a, (∑ b, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 +
(∑ b, (∑ a, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 -
(∑ ab, ((Measure.map T μ).real {ab}).negMulLog) / Real.log 2 =
mutualInfo f p n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2hMI:InformationTheory.mutualInformationBits (Measure.map T μ) Prod.fst Prod.snd =
InformationTheory.mutualInformationBits μ (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2⊢ (∑ a, (∑ b, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 +
(∑ b, (∑ a, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 -
(∑ ab, ((Measure.map T μ).real {ab}).negMulLog) / Real.log 2 =
mutualInfo f p] n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2hMI:InformationTheory.mutualInformationBits (Measure.map T μ) Prod.fst Prod.snd =
InformationTheory.mutualInformationBits μ (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2⊢ (∑ a, (∑ b, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 +
(∑ b, (∑ a, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 -
(∑ ab, ((Measure.map T μ).real {ab}).negMulLog) / Real.log 2 =
mutualInfo f p
simp only [hν, mutualInfo, entropy] All goals completed! 🐙The same identity on any measurable space carrying the specified joint input/noise law.
@[category API, AMS 94]
theorem mutualInformationBits_of_inputNoiseLaw (n : ℕ) (f : Cube n → Bool) (p : ℝ)
(hp₀ : 0 ≤ p) (hp₁ : p ≤ 1)
{Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) (X Z : Ω → Cube n)
(hX : Measurable X) (hZ : Measurable Z)
(hlaw : μ.map (fun ω => (X ω, Z ω)) = inputNoiseLaw n p hp₀ hp₁) :
InformationTheory.mutualInformationBits μ (f ∘ X) (fun ω => cubeXor (X ω) (Z ω)) =
mutualInfo f p := by n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) = mutualInfo f p
have hXZ : Measurable (fun ω => (X ω, Z ω)) := by fun_prop n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) = mutualInfo f p n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) = mutualInfo f p
rw [← mutualInformationBits_model_eq n f p hp₀ hp₁, n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) =
InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) =
InformationTheory.mutualInformationBits μ ((fun ω ↦ f ω.1) ∘ fun ω ↦ (X ω, Z ω))
((fun ω ↦ cubeXor ω.1 ω.2) ∘ fun ω ↦ (X ω, Z ω)) ← hlaw, n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) =
InformationTheory.mutualInformationBits (Measure.map (fun ω ↦ (X ω, Z ω)) μ) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) =
InformationTheory.mutualInformationBits μ ((fun ω ↦ f ω.1) ∘ fun ω ↦ (X ω, Z ω))
((fun ω ↦ cubeXor ω.1 ω.2) ∘ fun ω ↦ (X ω, Z ω))
InformationTheory.mutualInformationBits_map μ hXZ
(measurable_of_countable (fun ω : Cube n × Cube n => f ω.1))
(measurable_of_countable (fun ω : Cube n × Cube n => cubeXor ω.1 ω.2)) n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) =
InformationTheory.mutualInformationBits μ ((fun ω ↦ f ω.1) ∘ fun ω ↦ (X ω, Z ω))
((fun ω ↦ cubeXor ω.1 ω.2) ∘ fun ω ↦ (X ω, Z ω)) n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) =
InformationTheory.mutualInformationBits μ ((fun ω ↦ f ω.1) ∘ fun ω ↦ (X ω, Z ω))
((fun ω ↦ cubeXor ω.1 ω.2) ∘ fun ω ↦ (X ω, Z ω))] n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) =
InformationTheory.mutualInformationBits μ ((fun ω ↦ f ω.1) ∘ fun ω ↦ (X ω, Z ω))
((fun ω ↦ cubeXor ω.1 ω.2) ∘ fun ω ↦ (X ω, Z ω))
rfl All goals completed! 🐙The elementary formulation and the random-variable formulation are equivalent.
Neither direction uses either research declaration.
@[category API, AMS 94]
theorem courtade_kumar_iff_random_variable :
type_of% @courtade_kumar ↔ type_of% @variants.courtade_kumar_random_variable := by ⊢ (∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits p) ↔
∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p
constructor mp ⊢ (∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits p) →
∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pmpr ⊢ (∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p) →
∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits p
· mp ⊢ (∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits p) →
∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p intro h n f p hp₀ hp₁ Ω mΩ μ hμ X Z hX hZ hlaw mp h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:TypemΩ:MeasurableSpace Ωμ:Measure Ωhμ:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩)⊢ have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p
change InformationTheory.mutualInformationBits μ (f ∘ X)
(fun ω => cubeXor (X ω) (Z ω)) ≤ 1 - binEntropyBits p mp h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:TypemΩ:MeasurableSpace Ωμ:Measure Ωhμ:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) ≤ 1 - binEntropyBits p
rw [mutualInformationBits_of_inputNoiseLaw n f p hp₀ hp₁ μ X Z hX hZ hlaw mp h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:TypemΩ:MeasurableSpace Ωμ:Measure Ωhμ:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩)⊢ mutualInfo f p ≤ 1 - binEntropyBits p mp h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:TypemΩ:MeasurableSpace Ωμ:Measure Ωhμ:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩)⊢ mutualInfo f p ≤ 1 - binEntropyBits p] mp h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:TypemΩ:MeasurableSpace Ωμ:Measure Ωhμ:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩)⊢ mutualInfo f p ≤ 1 - binEntropyBits p
exact h n f p hp₀ hp₁ All goals completed! 🐙
· mpr ⊢ (∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p) →
∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ), 0 ≤ p → p ≤ 1 → mutualInfo f p ≤ 1 - binEntropyBits p intro h n f p hp₀ hp₁ mpr h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ mutualInfo f p ≤ 1 - binEntropyBits p
rw [← mutualInformationBits_model_eq n f p hp₀ hp₁ mpr h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) ≤
1 - binEntropyBits p mpr h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) ≤
1 - binEntropyBits p]mpr h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) ≤
1 - binEntropyBits p
exact h n f p hp₀ hp₁ (Cube n × Cube n) (inputNoiseLaw n p hp₀ hp₁) Prod.fst Prod.snd
measurable_fst measurable_snd (by h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ Measure.map (fun ω ↦ (ω.1, ω.2)) (inputNoiseLaw n p hp₀ hp₁) =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩)
change (inputNoiseLaw n p hp₀ hp₁).map id = inputNoiseLaw n p hp₀ hp₁ h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ Measure.map id (inputNoiseLaw n p hp₀ hp₁) = inputNoiseLaw n p hp₀ hp₁
simp All goals completed! 🐙)The random-variable formulation, stated over probability spaces in universe zero, implies the same bound on probability spaces in any universe. This does not use either research declaration.
@[category API, AMS 94]
theorem courtade_kumar_random_variable_bound
(hCK : type_of% @variants.courtade_kumar_random_variable)
(n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1)
{Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(X Z : Ω → Cube n) (hX : Measurable X) (hZ : Measurable Z)
(hlaw : μ.map (fun ω => (X ω, Z ω)) = inputNoiseLaw n p hp₀ hp₁) :
let Y : Ω → Cube n := fun ω => cubeXor (X ω) (Z ω)
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p := by hCK:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝¹:MeasurableSpace Ωμ:Measure Ωinst✝:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁⊢ let Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p
change InformationTheory.mutualInformationBits μ (f ∘ X)
(fun ω => cubeXor (X ω) (Z ω)) ≤ 1 - binEntropyBits p hCK:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝¹:MeasurableSpace Ωμ:Measure Ωinst✝:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) ≤ 1 - binEntropyBits p
rw [mutualInformationBits_of_inputNoiseLaw n f p hp₀ hp₁ μ X Z hX hZ hlaw hCK:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝¹:MeasurableSpace Ωμ:Measure Ωinst✝:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁⊢ mutualInfo f p ≤ 1 - binEntropyBits p hCK:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝¹:MeasurableSpace Ωμ:Measure Ωinst✝:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁⊢ mutualInfo f p ≤ 1 - binEntropyBits p] hCK:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X Z : Ω → Cube n),
Measurable X →
Measurable Z →
Measure.map (fun ω ↦ (X ω, Z ω)) μ =
(PMF.uniformOfFintype (Cube n)).toMeasure.prod
(Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) →
have Y := fun ω ↦ cubeXor (X ω) (Z ω);
InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝¹:MeasurableSpace Ωμ:Measure Ωinst✝:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁⊢ mutualInfo f p ≤ 1 - binEntropyBits p
exact (courtade_kumar_iff_random_variable.mpr hCK) n f p hp₀ hp₁ All goals completed! 🐙Tests of the definitions
@[category test, AMS 94]
theorem binEntropyBits_half : binEntropyBits (1 / 2) = 1 := by ⊢ binEntropyBits (1 / 2) = 1
have h : Real.log 2 ≠ 0 := ne_of_gt (Real.log_pos (by ⊢ 1 < 2 h:Real.log 2 ≠ 0⊢ binEntropyBits (1 / 2) = 1 norm_num All goals completed! 🐙 h:Real.log 2 ≠ 0⊢ binEntropyBits (1 / 2) = 1)) h:Real.log 2 ≠ 0⊢ binEntropyBits (1 / 2) = 1
simpa [binEntropyBits, one_div] using div_self h All goals completed! 🐙
@[category API, AMS 94]
private theorem sum_cube_one (F : Cube 1 → ℝ) :
∑ x, F x = F (fun _ => true) + F (fun _ => false) := by F:Cube 1 → ℝ⊢ ∑ x, F x = (F fun x ↦ true) + F fun x ↦ false
rw [Fintype.sum_equiv (Equiv.funUnique (Fin 1) Bool) F (fun b => F (fun _ => b)) F:Cube 1 → ℝ⊢ (∑ x, F fun x_1 ↦ x) = (F fun x ↦ true) + F fun x ↦ falseF:Cube 1 → ℝ⊢ ∀ (x : Fin 1 → Bool), F x = F fun x_1 ↦ (Equiv.funUnique (Fin 1) Bool) x F:Cube 1 → ℝ⊢ (∑ x, F fun x_1 ↦ x) = (F fun x ↦ true) + F fun x ↦ falseF:Cube 1 → ℝ⊢ ∀ (x : Fin 1 → Bool), F x = F fun x_1 ↦ (Equiv.funUnique (Fin 1) Bool) x] F:Cube 1 → ℝ⊢ (∑ x, F fun x_1 ↦ x) = (F fun x ↦ true) + F fun x ↦ falseF:Cube 1 → ℝ⊢ ∀ (x : Fin 1 → Bool), F x = F fun x_1 ↦ (Equiv.funUnique (Fin 1) Bool) x
· F:Cube 1 → ℝ⊢ (∑ x, F fun x_1 ↦ x) = (F fun x ↦ true) + F fun x ↦ false exact Fintype.sum_bool _ All goals completed! 🐙
· F:Cube 1 → ℝ⊢ ∀ (x : Fin 1 → Bool), F x = F fun x_1 ↦ (Equiv.funUnique (Fin 1) Bool) x intro x F:Cube 1 → ℝx:Fin 1 → Bool⊢ F x = F fun x_1 ↦ (Equiv.funUnique (Fin 1) Bool) x
simp only [Equiv.funUnique_apply] F:Cube 1 → ℝx:Fin 1 → Bool⊢ F x = F fun x_1 ↦ x default
congr 1 F:Cube 1 → ℝx:Fin 1 → Bool⊢ x = fun x_1 ↦ x default
funext i F:Cube 1 → ℝx:Fin 1 → Booli:Fin 1⊢ x i = x default
rw [Subsingleton.elim i default F:Cube 1 → ℝx:Fin 1 → Booli:Fin 1⊢ x default = x default All goals completed! 🐙] All goals completed! 🐙
@[category API, AMS 94]
private theorem jointProb_dictator (p : ℝ) (b : Bool) (y : Cube 1) :
jointProb (n := 1) (fun x => x 0) p b y = (if b = y 0 then 1 - p else p) / 2 := by p:ℝb:Booly:Cube 1⊢ jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2
unfold jointProb bsc p:ℝb:Booly:Cube 1⊢ (2 ^ (-↑1) * ∑ x, if (fun x ↦ x 0) x = b then ∏ i, if x i = y i then 1 - p else p else 0) =
(if b = y 0 then 1 - p else p) / 2
rw [sum_cube_one p:ℝb:Booly:Cube 1⊢ 2 ^ (-↑1) *
((if ((fun x ↦ x 0) fun x ↦ true) = b then ∏ i, if (fun x ↦ true) i = y i then 1 - p else p else 0) +
if ((fun x ↦ x 0) fun x ↦ false) = b then ∏ i, if (fun x ↦ false) i = y i then 1 - p else p else 0) =
(if b = y 0 then 1 - p else p) / 2 p:ℝb:Booly:Cube 1⊢ 2 ^ (-↑1) *
((if ((fun x ↦ x 0) fun x ↦ true) = b then ∏ i, if (fun x ↦ true) i = y i then 1 - p else p else 0) +
if ((fun x ↦ x 0) fun x ↦ false) = b then ∏ i, if (fun x ↦ false) i = y i then 1 - p else p else 0) =
(if b = y 0 then 1 - p else p) / 2] p:ℝb:Booly:Cube 1⊢ 2 ^ (-↑1) *
((if ((fun x ↦ x 0) fun x ↦ true) = b then ∏ i, if (fun x ↦ true) i = y i then 1 - p else p else 0) +
if ((fun x ↦ x 0) fun x ↦ false) = b then ∏ i, if (fun x ↦ false) i = y i then 1 - p else p else 0) =
(if b = y 0 then 1 - p else p) / 2
simp only [Fin.prod_univ_one] p:ℝb:Booly:Cube 1⊢ 2 ^ (-↑1) *
((if true = b then if true = y 0 then 1 - p else p else 0) +
if false = b then if false = y 0 then 1 - p else p else 0) =
(if b = y 0 then 1 - p else p) / 2
cases b false p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = false then if true = y 0 then 1 - p else p else 0) +
if false = false then if false = y 0 then 1 - p else p else 0) =
(if false = y 0 then 1 - p else p) / 2true p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = true then if true = y 0 then 1 - p else p else 0) +
if false = true then if false = y 0 then 1 - p else p else 0) =
(if true = y 0 then 1 - p else p) / 2 <;> false p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = false then if true = y 0 then 1 - p else p else 0) +
if false = false then if false = y 0 then 1 - p else p else 0) =
(if false = y 0 then 1 - p else p) / 2true p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = true then if true = y 0 then 1 - p else p else 0) +
if false = true then if false = y 0 then 1 - p else p else 0) =
(if true = y 0 then 1 - p else p) / 2 cases y 0 true.false p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = true then if true = false then 1 - p else p else 0) +
if false = true then if false = false then 1 - p else p else 0) =
(if true = false then 1 - p else p) / 2true.true p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = true then if true = true then 1 - p else p else 0) +
if false = true then if false = true then 1 - p else p else 0) =
(if true = true then 1 - p else p) / 2 <;> false.false p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = false then if true = false then 1 - p else p else 0) +
if false = false then if false = false then 1 - p else p else 0) =
(if false = false then 1 - p else p) / 2false.true p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = false then if true = true then 1 - p else p else 0) +
if false = false then if false = true then 1 - p else p else 0) =
(if false = true then 1 - p else p) / 2true.false p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = true then if true = false then 1 - p else p else 0) +
if false = true then if false = false then 1 - p else p else 0) =
(if true = false then 1 - p else p) / 2true.true p:ℝy:Cube 1⊢ 2 ^ (-↑1) *
((if true = true then if true = true then 1 - p else p else 0) +
if false = true then if false = true then 1 - p else p else 0) =
(if true = true then 1 - p else p) / 2 simp true.true p:ℝy:Cube 1⊢ 2⁻¹ * (1 - p) = (1 - p) / 2 <;> false.false p:ℝy:Cube 1⊢ 2⁻¹ * (1 - p) = (1 - p) / 2false.true p:ℝy:Cube 1⊢ 2⁻¹ * p = p / 2true.false p:ℝy:Cube 1⊢ 2⁻¹ * p = p / 2true.true p:ℝy:Cube 1⊢ 2⁻¹ * (1 - p) = (1 - p) / 2 ring All goals completed! 🐙
@[category API, AMS 94]
private theorem negMulLog_div_two (x : ℝ) :
Real.negMulLog (x / 2) = Real.negMulLog x / 2 + x * Real.log 2 / 2 := by x:ℝ⊢ (x / 2).negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2
rw [div_eq_mul_inv, x:ℝ⊢ (x * 2⁻¹).negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2 x:ℝ⊢ 2⁻¹ * x.negMulLog + x * 2⁻¹.negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2 Real.negMulLog_mul x:ℝ⊢ 2⁻¹ * x.negMulLog + x * 2⁻¹.negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2 x:ℝ⊢ 2⁻¹ * x.negMulLog + x * 2⁻¹.negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2] x:ℝ⊢ 2⁻¹ * x.negMulLog + x * 2⁻¹.negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2
have h : Real.negMulLog (2 : ℝ)⁻¹ = Real.log 2 / 2 := by x:ℝ⊢ (x / 2).negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2 x:ℝh:2⁻¹.negMulLog = Real.log 2 / 2⊢ 2⁻¹ * x.negMulLog + x * 2⁻¹.negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2
simp only [Real.negMulLog, Real.log_inv] x:ℝ⊢ -2⁻¹ * -Real.log 2 = Real.log 2 / 2 x:ℝh:2⁻¹.negMulLog = Real.log 2 / 2⊢ 2⁻¹ * x.negMulLog + x * 2⁻¹.negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2
ring x:ℝh:2⁻¹.negMulLog = Real.log 2 / 2⊢ 2⁻¹ * x.negMulLog + x * 2⁻¹.negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2 x:ℝh:2⁻¹.negMulLog = Real.log 2 / 2⊢ 2⁻¹ * x.negMulLog + x * 2⁻¹.negMulLog = x.negMulLog / 2 + x * Real.log 2 / 2
rw [h x:ℝh:2⁻¹.negMulLog = Real.log 2 / 2⊢ 2⁻¹ * x.negMulLog + x * (Real.log 2 / 2) = x.negMulLog / 2 + x * Real.log 2 / 2 x:ℝh:2⁻¹.negMulLog = Real.log 2 / 2⊢ 2⁻¹ * x.negMulLog + x * (Real.log 2 / 2) = x.negMulLog / 2 + x * Real.log 2 / 2] x:ℝh:2⁻¹.negMulLog = Real.log 2 / 2⊢ 2⁻¹ * x.negMulLog + x * (Real.log 2 / 2) = x.negMulLog / 2 + x * Real.log 2 / 2
ring All goals completed! 🐙Algebraic identity for the one-coordinate dictator $f(x) = x_0$. For $p \in [0, 1]$, it shows that the bound is attained, so the conjecture is sharp and the statement is not vacuous.
@[category test, AMS 94]
theorem mutualInfo_dictator (p : ℝ) :
mutualInfo (n := 1) (fun x => x 0) p = 1 - binEntropyBits p := by p:ℝ⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
have hlog : Real.log 2 ≠ 0 := ne_of_gt (Real.log_pos (by p:ℝ⊢ 1 < 2 p:ℝhlog:Real.log 2 ≠ 0⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p norm_num All goals completed! 🐙 p:ℝhlog:Real.log 2 ≠ 0⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p)) p:ℝhlog:Real.log 2 ≠ 0⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
have jm : ∀ b y, jointProb (n := 1) (fun x => x 0) p b y =
(if b = y 0 then 1 - p else p) / 2 := jointProb_dictator p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
have half : Real.negMulLog (1 / 2) = Real.log 2 / 2 := by
rw [negMulLog_div_two, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2⊢ Real.negMulLog 1 / 2 + 1 * Real.log 2 / 2 = Real.log 2 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2⊢ 0 / 2 + 1 * Real.log 2 / 2 = Real.log 2 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p Real.negMulLog_one p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2⊢ 0 / 2 + 1 * Real.log 2 / 2 = Real.log 2 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2⊢ 0 / 2 + 1 * Real.log 2 / 2 = Real.log 2 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2⊢ 0 / 2 + 1 * Real.log 2 / 2 = Real.log 2 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
ring p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
have mf : ∀ b : Bool, ∑ y, jointProb (n := 1) (fun x => x 0) p b y = 1 / 2 := by
intro b p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2b:Bool⊢ ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
rw [sum_cube_one, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2b:Bool⊢ ((jointProb (fun x ↦ x 0) p b fun x ↦ true) + jointProb (fun x ↦ x 0) p b fun x ↦ false) = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2b:Bool⊢ (if b = true then 1 - p else p) / 2 + (if b = false then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p jm, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2b:Bool⊢ ((if b = true then 1 - p else p) / 2 + jointProb (fun x ↦ x 0) p b fun x ↦ false) = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2b:Bool⊢ (if b = true then 1 - p else p) / 2 + (if b = false then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p jm p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2b:Bool⊢ (if b = true then 1 - p else p) / 2 + (if b = false then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2b:Bool⊢ (if b = true then 1 - p else p) / 2 + (if b = false then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2b:Bool⊢ (if b = true then 1 - p else p) / 2 + (if b = false then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
cases b false p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ (if false = true then 1 - p else p) / 2 + (if false = false then 1 - p else p) / 2 = 1 / 2true p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ (if true = true then 1 - p else p) / 2 + (if true = false then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p <;> false p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ (if false = true then 1 - p else p) / 2 + (if false = false then 1 - p else p) / 2 = 1 / 2true p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ (if true = true then 1 - p else p) / 2 + (if true = false then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p simp true p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ (1 - p) / 2 + p / 2 = 2⁻¹ p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p <;> false p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ p / 2 + (1 - p) / 2 = 2⁻¹true p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2⊢ (1 - p) / 2 + p / 2 = 2⁻¹ p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p ring p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
have my : ∀ y : Cube 1, ∑ b, jointProb (n := 1) (fun x => x 0) p b y = 1 / 2 := by
intro y p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
rw [Fintype.sum_bool, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ jointProb (fun x ↦ x 0) p true y + jointProb (fun x ↦ x 0) p false y = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = y 0 then 1 - p else p) / 2 + (if false = y 0 then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p jm, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = y 0 then 1 - p else p) / 2 + jointProb (fun x ↦ x 0) p false y = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = y 0 then 1 - p else p) / 2 + (if false = y 0 then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p jm p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = y 0 then 1 - p else p) / 2 + (if false = y 0 then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = y 0 then 1 - p else p) / 2 + (if false = y 0 then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = y 0 then 1 - p else p) / 2 + (if false = y 0 then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
cases y 0 false p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = false then 1 - p else p) / 2 + (if false = false then 1 - p else p) / 2 = 1 / 2true p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = true then 1 - p else p) / 2 + (if false = true then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p <;> false p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = false then 1 - p else p) / 2 + (if false = false then 1 - p else p) / 2 = 1 / 2true p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (if true = true then 1 - p else p) / 2 + (if false = true then 1 - p else p) / 2 = 1 / 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p simp true p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (1 - p) / 2 + p / 2 = 2⁻¹ p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p <;> false p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ p / 2 + (1 - p) / 2 = 2⁻¹true p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2y:Cube 1⊢ (1 - p) / 2 + p / 2 = 2⁻¹ p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p ring p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
have e1 : entropy (fun b => ∑ y, jointProb (n := 1) (fun x => x 0) p b y) = 1 := by
unfold entropy p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ (∑ a, ((fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) a).negMulLog) / Real.log 2 = 1 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
simp only [mf, Fintype.sum_bool, half] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ (Real.log 2 / 2 + Real.log 2 / 2) / Real.log 2 = 1 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
field_simp p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2⊢ 1 + 1 = 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
ring p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
have e2 : entropy (fun y => ∑ b, jointProb (n := 1) (fun x => x 0) p b y) = 1 := by
unfold entropy p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ (∑ a, ((fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) a).negMulLog) / Real.log 2 = 1 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
simp only [my] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ (∑ x, (1 / 2).negMulLog) / Real.log 2 = 1 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
rw [sum_cube_one p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ ((1 / 2).negMulLog + (1 / 2).negMulLog) / Real.log 2 = 1 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ ((1 / 2).negMulLog + (1 / 2).negMulLog) / Real.log 2 = 1 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ ((1 / 2).negMulLog + (1 / 2).negMulLog) / Real.log 2 = 1 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
simp only [half] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ (Real.log 2 / 2 + Real.log 2 / 2) / Real.log 2 = 1 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
field_simp p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1⊢ 1 + 1 = 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
ring p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
have e3 : entropy (fun z : Bool × Cube 1 => jointProb (n := 1) (fun x => x 0) p z.1 z.2) =
1 + binEntropyBits p := by
unfold entropy binEntropyBits p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (∑ a, ((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) a).negMulLog) / Real.log 2 = 1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
rw [Fintype.sum_prod_type, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (∑ x, ∑ y, ((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (x, y)).negMulLog) / Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ false)).negMulLog +
(((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ false)).negMulLog)) /
Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p Fintype.sum_bool, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (∑ y, ((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, y)).negMulLog +
∑ y, ((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, y)).negMulLog) /
Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ false)).negMulLog +
(((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ false)).negMulLog)) /
Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p sum_cube_one, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ false)).negMulLog +
∑ y, ((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, y)).negMulLog) /
Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ false)).negMulLog +
(((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ false)).negMulLog)) /
Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p sum_cube_one p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ false)).negMulLog +
(((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ false)).negMulLog)) /
Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ false)).negMulLog +
(((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ false)).negMulLog)) /
Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (true, fun x ↦ false)).negMulLog +
(((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ true)).negMulLog +
((fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) (false, fun x ↦ false)).negMulLog)) /
Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
simp only [jm] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((if True then 1 - p else p) / 2).negMulLog + ((if true = false then 1 - p else p) / 2).negMulLog +
(((if false = true then 1 - p else p) / 2).negMulLog + ((if True then 1 - p else p) / 2).negMulLog)) /
Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
simp only [if_true, if_false, Bool.true_eq_false, Bool.false_eq_true] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((1 - p) / 2).negMulLog + (p / 2).negMulLog + ((p / 2).negMulLog + ((1 - p) / 2).negMulLog)) / Real.log 2 =
1 + Real.binEntropy p / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
rw [Real.binEntropy_eq_negMulLog_add_negMulLog_one_sub, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (((1 - p) / 2).negMulLog + (p / 2).negMulLog + ((p / 2).negMulLog + ((1 - p) / 2).negMulLog)) / Real.log 2 =
1 + (p.negMulLog + (1 - p).negMulLog) / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2 + (p.negMulLog / 2 + p * Real.log 2 / 2) +
(p.negMulLog / 2 + p * Real.log 2 / 2 + ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2))) /
Real.log 2 =
1 + (p.negMulLog + (1 - p).negMulLog) / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p negMulLog_div_two, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2 + (p / 2).negMulLog +
((p / 2).negMulLog + ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2))) /
Real.log 2 =
1 + (p.negMulLog + (1 - p).negMulLog) / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2 + (p.negMulLog / 2 + p * Real.log 2 / 2) +
(p.negMulLog / 2 + p * Real.log 2 / 2 + ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2))) /
Real.log 2 =
1 + (p.negMulLog + (1 - p).negMulLog) / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p negMulLog_div_two p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2 + (p.negMulLog / 2 + p * Real.log 2 / 2) +
(p.negMulLog / 2 + p * Real.log 2 / 2 + ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2))) /
Real.log 2 =
1 + (p.negMulLog + (1 - p).negMulLog) / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2 + (p.negMulLog / 2 + p * Real.log 2 / 2) +
(p.negMulLog / 2 + p * Real.log 2 / 2 + ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2))) /
Real.log 2 =
1 + (p.negMulLog + (1 - p).negMulLog) / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2 + (p.negMulLog / 2 + p * Real.log 2 / 2) +
(p.negMulLog / 2 + p * Real.log 2 / 2 + ((1 - p).negMulLog / 2 + (1 - p) * Real.log 2 / 2))) /
Real.log 2 =
1 + (p.negMulLog + (1 - p).negMulLog) / Real.log 2 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
field_simp p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1⊢ (1 - p).negMulLog + (1 - p) * Real.log 2 + (p.negMulLog + p * Real.log 2) +
(p.negMulLog + p * Real.log 2 + ((1 - p).negMulLog + (1 - p) * Real.log 2)) =
2 * (Real.log 2 + (p.negMulLog + (1 - p).negMulLog)) p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
ring p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ mutualInfo (fun x ↦ x 0) p = 1 - binEntropyBits p
unfold mutualInfo p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ (((entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) + entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) -
entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) =
1 - binEntropyBits p
rw [e1, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ ((1 + entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) - entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) =
1 - binEntropyBits p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ 1 + 1 - (1 + binEntropyBits p) = 1 - binEntropyBits p e2, p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ (1 + 1 - entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 - binEntropyBits p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ 1 + 1 - (1 + binEntropyBits p) = 1 - binEntropyBits p e3 p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ 1 + 1 - (1 + binEntropyBits p) = 1 - binEntropyBits p p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ 1 + 1 - (1 + binEntropyBits p) = 1 - binEntropyBits p] p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ 1 + 1 - (1 + binEntropyBits p) = 1 - binEntropyBits p
ring All goals completed! 🐙end CourtadeKumar