empiricalJoint_sum_prob_mul
Averaging a payoff against the empirical joint distribution. Fix $T > 0$ rounds of play in which, in round $t$, the row player uses a mixed strategy $p_t$ over $\mathrm{Fin}\,M$ and the column player a mixed strategy $q_t$ over $\mathrm{Fin}\,N$; write $(p_t)_i$ and $(q_t)_j$ for the weights placed on actions $i$ and $j$. Let $\sigma$ be the empirical joint distribution, whose value at each profile $(i,j)$ is the time average $\sigma_{ij} = \frac{1}{T}\sum_{t=1}^{T} (p_t)_i\,(q_t)_j$. Then for every function $f : \mathrm{Fin}\,M \times \mathrm{Fin}\,N \to \bbr$, \[ \sum_{i}\sum_{j} \sigma_{ij}\, f(i,j) \;=\; \frac{1}{T}\sum_{t=1}^{T}\sum_{i}\sum_{j} (p_t)_i\,(q_t)_j\, f(i,j). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Finset BigOperators in lemma empiricalJoint_sum_prob_mul {M N T : ℕ} (hT : 0 < T) (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (f : Fin M → Fin N → ℝ) : (∑ i : Fin M, ∑ j : Fin N, (empiricalJoint hT p q).prob i j * f i j) = (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N, (p t).weights i * (q t).weights j * f i j) / T
- Source
- TCSlib, `empiricalJoint_sum_prob_mul`
- Lean proof
- By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.empiricalJoint_sum_prob_mul← empiricalJoint_sum_prob_mul (TCSlib/LearningTheory/Minimax/CCE.lean:305): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- empiricalJointGiven $T > 0$ rounds of play in which the row player uses mixed strategy $p_t$ and the column player uses $q_t$, the empirical joint…
- MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
- empiricalJoint_colMarginalColumn marginal of the empirical joint distribution. Consider $T > 0$ rounds of play between a row player with $M$ actions and a column…
- empiricalJoint_rowMarginalRow marginal of the empirical joint distribution. Fix $T \ge 1$ rounds of play in which the row player uses mixed strategies…
- JointDistributionA joint distribution $\sigma$ on $\mathrm{Fin}\,M \times \mathrm{Fin}\,N$ is a nonnegative function $\sigma_{ij} \ge 0$ satisfying…
- Used by 2
- empiricalJoint_rowExpectedUtilityRow expected utility of the empirical joint distribution. Fix a finite two-player game with $M$ row actions and $N$ column actions, and…
- empiricalJoint_colExpectedUtilityColumn utility of the empirical joint distribution. Consider a finite two-player game with $M$ row actions and $N$ column actions, whose…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Finset BigOperators in/-- Any utility-style sum `Σ_i Σ_j σ(i, j) · f(i, j)` over the empirical joint distribution `σ = empiricalJoint hT p q` equals the time average `(1/T) Σ_t Σ_i Σ_j p_t(i) q_t(j) f(i, j)` of the per-round expected values of `f`. **Proof sketch.** Bookkeeping only: for each profile, move the factor `f i j` inside the time sum (`hStep`); pull the division by `T` out of the double sum over profiles; then swap the order of summation so time is outermost (two applications of `Finset.sum_comm`). -/lemma empiricalJoint_sum_prob_mul {M N T : ℕ} (hT : 0 < T) (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (f : Fin M → Fin N → ℝ) : (∑ i : Fin M, ∑ j : Fin N, (empiricalJoint hT p q).prob i j * f i j) = (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N, (p t).weights i * (q t).weights j * f i j) / T := by -- This lemma is only bookkeeping: pull the division by `T` out of the finite -- sums, then swap the order of the time/action sums. show ∑ i : Fin M, ∑ j : Fin N, (∑ t : Fin T, (p t).weights i * (q t).weights j) / (T : ℝ) * f i j = (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N, (p t).weights i * (q t).weights j * f i j) / (T : ℝ) have hStep : ∀ i : Fin M, ∀ j : Fin N, (∑ t : Fin T, (p t).weights i * (q t).weights j) / (T : ℝ) * f i j = (∑ t : Fin T, (p t).weights i * (q t).weights j * f i j) / (T : ℝ) := by intro i j rw [div_mul_eq_mul_div, ← Finset.sum_mul] simp_rw [hStep] rw [show (∑ i : Fin M, ∑ j : Fin N, (∑ t : Fin T, (p t).weights i * (q t).weights j * f i j) / (T : ℝ)) = (∑ i : Fin M, ∑ j : Fin N, ∑ t : Fin T, (p t).weights i * (q t).weights j * f i j) / (T : ℝ) from ?_] · congr 1 rw [show (∑ i : Fin M, ∑ j : Fin N, ∑ t : Fin T, (p t).weights i * (q t).weights j * f i j) = (∑ i : Fin M, ∑ t : Fin T, ∑ j : Fin N, (p t).weights i * (q t).weights j * f i j) from Finset.sum_congr rfl fun _ _ => Finset.sum_comm] exact Finset.sum_comm · rw [Finset.sum_div] apply Finset.sum_congr rfl; intro i _ rw [Finset.sum_div]