AFTD Auto-Formalizing Theoretical Domains

empiricalJoint_colMarginal

theoremverifiedimported Lean

Column marginal of the empirical joint distribution. Consider $T > 0$ rounds of play between a row player with $M$ actions and a column player with $N$ actions, where in round $t$ the row player uses the mixed strategy $p_t$ over the row actions and the column player uses the mixed strategy $q_t$ over the column actions. Form the empirical joint distribution $\sigma$ assigning to each profile $(i,j)$ the time-averaged probability $\frac{1}{T}\sum_{t=1}^{T} (p_t)_i (q_t)_j$. Then for each column action $j$, the column marginal $\sigma^{\mathrm{col}}_j = \sum_i \sigma_{ij}$ equals the time-average of the column player's weights on $j$, \[ \sigma^{\mathrm{col}}_j = \frac{1}{T}\sum_{t=1}^{T} (q_t)_j. \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Finset BigOperators in
@[simp] lemma empiricalJoint_colMarginal {M N T : ℕ} (hT : 0 < T)
    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (j : Fin N) :
    (empiricalJoint hT p q).colMarginal j =
      (∑ t : Fin T, (q t).weights j) / T
Source
TCSlib, `empiricalJoint_colMarginal`
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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_rowMarginalRow marginal of the empirical joint distribution. Fix $T \ge 1$ rounds of play in which the row player uses mixed strategies…
  • JointDistribution.colMarginalThe column marginal of $\sigma$ at column action $j$ is $\sigma^{\mathrm{col}}_j = \sum_{i} \sigma_{ij}$, i.e.\ the probability that the…
Used by 8
  • 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_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

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Finset BigOperators in/-- The column marginal of the empirical joint distribution is the time-average of the column mixed strategies. -/@[simp] lemma empiricalJoint_colMarginal {M N T : ℕ} (hT : 0 < T)    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (j : Fin N) :    (empiricalJoint hT p q).colMarginal j =      (∑ t : Fin T, (q t).weights j) / T := by  show ∑ i : Fin M,      (∑ t : Fin T, (p t).weights i * (q t).weights j) / (T : ℝ) =    (∑ t : Fin T, (q t).weights j) / (T : ℝ)  rw [← Finset.sum_div, Finset.sum_comm]  congr 1  apply Finset.sum_congr rfl; intro t _  rw [← Finset.sum_mul, (p t).sum_one, one_mul]
See it in the graphDiscuss this resultChallenge it