empiricalJoint_rowMarginal
Row marginal of the empirical joint distribution. Fix $T \ge 1$ rounds of play in which the row player uses mixed strategies $p_1,\dots,p_T$ over $M$ actions and the column player uses mixed strategies $q_1,\dots,q_T$ over $N$ actions, and let $\sigma$ be the empirical joint distribution, which assigns to each profile $(i,j)$ the time-averaged probability $\frac{1}{T}\sum_{t=1}^{T} (p_t)_i (q_t)_j$. Then for every row action $i$, the row marginal $\sigma^{\mathrm{row}}_i = \sum_{j} \sigma_{ij}$ equals the time-average of the row player's weight on $i$: \[ \sigma^{\mathrm{row}}_i \;=\; \frac{1}{T}\sum_{t=1}^{T} (p_t)_i . \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Finset BigOperators in @[simp] lemma empiricalJoint_rowMarginal {M N T : ℕ} (hT : 0 < T) (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (i : Fin M) : (empiricalJoint hT p q).rowMarginal i = (∑ t : Fin T, (p t).weights i) / T
- Source
- TCSlib, `empiricalJoint_rowMarginal`
- 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_rowMarginal← empiricalJoint_rowMarginal (TCSlib/LearningTheory/Minimax/CCE.lean:270): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- JointDistribution.rowMarginalThe row marginal of $\sigma$ at row action $i$ is $\sigma^{\mathrm{row}}_i = \sum_{j} \sigma_{ij}$, i.e.\ the probability that the row…
- Used by 9
- empiricalJoint_isApproxCCENo-regret play yields an approximate coarse correlated equilibrium. Let $G$ be a finite two-player game with row utility $u_r$ and column…
- 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_row_deviation_leRow regret bound gives row deviation bound. Let $G$ be a finite two-player game with row utility $u_r$ over $M$ row actions and $N$ column…
- empiricalJoint_sum_prob_mulAveraging a payoff against the empirical joint distribution. Fix $T > 0$ rounds of play in which, in round $t$, the row player uses a…
- empiricalJoint_rowDeviationUtilityEmpirical row deviation utility as a time average. Let $G$ be a finite two-player game with $M$ row actions and $N$ column actions, and…
- 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…
- empiricalJoint_colDeviationUtilityColumn deviation utility of the empirical joint distribution. Let $G$ be a finite two-player game with $M$ row actions and $N$ column…
- empiricalJoint_col_deviation_leColumn regret bound gives column deviation bound. Let $G$ be a finite two-player game with column utility $u_c$ over $M$ row actions and…
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/-- The row marginal of the empirical joint distribution is the time-average of the row mixed strategies. -/@[simp] lemma empiricalJoint_rowMarginal {M N T : ℕ} (hT : 0 < T) (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (i : Fin M) : (empiricalJoint hT p q).rowMarginal i = (∑ t : Fin T, (p t).weights i) / T := by show ∑ j : Fin N, (∑ t : Fin T, (p t).weights i * (q t).weights j) / (T : ℝ) = (∑ t : Fin T, (p t).weights i) / (T : ℝ) rw [← Finset.sum_div, Finset.sum_comm] congr 1 apply Finset.sum_congr rfl; intro t _ rw [← Finset.mul_sum, (q t).sum_one, mul_one]