The maximal variation of martingales of probabilities and repeated games with incomplete information

Abstract: The variation of a martingale

p_{0}^{k} = p_{0}, ..., p_{k}

of probabilities on a finite (or countable) set

X

is denoted

V (p_{0}^{k})

and defined by

V (p_{0}^{k}) = E (s u m_{t = 1}^{k} | p_{t} - p_{t - 1} |_{1})

. It is shown that

V (p_{0}^{k}) l e q s q r t 2 k H (p_{0})

, where

H (p)

is the entropy function

H (p) = - s u m_{x} p (x) l o g p (x)

and

l o g

stands for the natural logarithm. Therefore, if

d

is the number of elements of

X

, then

V (p_{0}^{k}) l e q s q r t 2 k l o g d

. It is shown that the order of magnitude of the bound

s q r t 2 k l o g d

is tight for

d l e q 2^{k}

: there is

C > 0

such that for every

k

and

d l e q 2^{k}

there is a martingale

p_{0}^{k} = p_{0}, ..., p_{k}

of probabilities on a set

X

with

d

elements, and with variation

V (p_{0}^{k}) g e q C s q r t 2 k l o g d

. An application of the first result to game theory is that the difference between

v_{k}

and

l i m_{k} v_{k}

, 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 | s q r t 2 k^{- 1} l o g 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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: The maximal variation of martingales of probabilities and repeated games with incomplete information