The Maximal Variation of Martingales of Probabilities and Repeated Games with Incomplete Information

The variation of a martingale $p_{0}^{k}=p_{0},\ldots,p_{k}$ of probabilities on a finite (or countable) set X is denoted $V(p_{0}^{k})$ and defined by $$ V\bigl(p_0^k\bigr)=E\Biggl(\sum_{t=1}^k\|p_t-p_{t-1}\|_1\Biggr). $$ It is shown that $V(p_{0}^{k})\leq\sqrt{2kH(p_{0})}$ , where H(p) is the entropy function H(p)=?∑ _x p(x)logp(x), and log stands for the natural logarithm. Therefore, if d is the number of elements of X, then $V(p_{0}^{k})\leq\sqrt{2k\log d}$ . It is shown that the order of magnitude of the bound $\sqrt{2k\log d}$ is tight for d≤2 ^k : there is C>0 such that for all k and d≤2 ^k , there is a martingale $p_{0}^{k}=p_{0},\ldots,p_{k}$ of probabilities on a set X with d elements, and with variation $V(p_{0}^{k})\geq C\sqrt{2k\log d}$ . An application of the first result to game theory is that the difference between v _k and lim _j v _j , where v _k is the value of the k-stage repeated game with incomplete information on one side with d states, is bounded by $\|G\|\sqrt{2k^{-1}\log d}$ (where ∥G∥ is the maximal absolute value of a stage payoff). Furthermore, it is shown that the order of magnitude of this game theory bound is tight.