The variation of a martingale m[k] of k+1 probability measures p(0),...,p(k) on a finite (or countable) set X is the expectation of the sum of ||p(t)-p(t-1)|| (the L one norm of the martingale differences p(t)-p(t-1)), and is denoted V(m[k]). It is shown that V(m[k]) is less than or equal to the square root of 2kH(p(0)), where H(p) is the entropy function (the some over x in X of p(x)log p(x) and log stands for the natural logarithm). Therefore, if d is the number of elements of X, then V(m[k]) is less than or equal to the square root of 2k(log d). It is shown that the order of magnitude of this bound is tight for d less than or equal to 2 to the power k: there is C>0 such that for every k and d less than or equal to 2 to the power k there is a martingale m[k]=p(0),...,p(k) of probability measures on a set X with d elements, and with variation V(m[k]) that is greater or equal the square root of Ck(log d). It follows that the difference between the value of the k-stage repeated game with incomplete information on one side and with d states, denoted v(k), and the limit of v(k), as k goes to infinity, is bounded by the maximal absolute value of a stage payoff times the square root of 2(log d)/k, and it is shown that the order of magnitude of this bound is tight.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Center for Rationality and Interactive Decision Theory, Hebrew University, Jerusalem in its series Discussion Paper Series with number
dp510.
Cited by: (explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)