.

.

An introduction to game-theoretic probability fromstatistical viewpoint
Akimichi Takemura(joint with M.Kumon, K.Takeuchi and K.Miyabe)
University of Tokyo

May 14, 2013
RPTC2013

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo1 / 26

Contents of this talk. List of Tokyo papers

1. Background on game-theoretic probability (GTP)2. Introduction to game-theoretic probability using a coin-tossing game3

. Bayesian Skeptic for the coin-tossing game4

. Non-negative martingales and likelihood ratios

5

Takemura (Univ. of Tokyo)

Game-theoretic probabilityMay 14, U.Tokyo2 / 26

Introduction

List of Tokyo papers(in http://www.probabilityandfinance.com/)1.

“On a simple strategy weakly forcing the strong law of large numbers in thebounded forecasting game”, Kumon and Takemura. Ann. Inst. Stat. Math., 60,801–812. 2008.

2.

“Game theoretic derivation of discrete distributions and discrete pricing formulas”,
Takemura and Taiji Suzuki. J. Japan Stat. Soc., 37, 87–104. 2007.

3.

“Capital process and optimality properties of Bayesian Skeptic in the fair andbiased coin games”, Kumon, Takemura and Takeuchi. Stochastic Analysis andApplications, 26, 1161–1180. 2008.

4.

“Game-theoretic versions of strong law of large numbers for unbounded variables”,
Kumon, Takemura and A.Takeuchi. Stochastics, 79, 449–468. 2007.

5.

“Implications of contrarian and one-sided strategies for the fair-coin game”,
Yasunori Horikoshi and Takemura. Stochastic Processes and their Applications,
118, 2125–2142. 2008.

6.

“A new formulation of asset trading games in continuous time with essential
forcing of variation exponent”, Takeuchi, Kumon and Takemura. Bernoulli, 15,1243–1258. 2009.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

3 / 26

Introduction

List of Tokyo papers
7.

“Multistep Bayesian strategy in coin-tossing games and its application to asset
trading games in continuous time”, Takeuchi, Kumon and Takemura. Stochastic
Analysis and Applications, 28, 842–861. 2010.

8.

“The generality of the zero-one laws”, by Takemura, V.Vovk and G.Shafer. Ann.
Inst. Stat. Math., 63, 873-886. 2011.

9.

“New procedures for testing whether stock price processes are martingales”,
Takeuchi, Takemura and Kumon. Computational Economics, 37, No.1, 67–88.
2010.

.
10

“Sequential optimizing strategy in multi-dimensional bounded forecasting games”,
Kumon, Takemura and Takeuchi. Stochastic Processes and their Applications,
121, 155–183. 2011.

.
11“Sequential optimizing investing strategy with neural networks”, Ryo Adachi andA.Takemura. Expert Systems With Applications. 38, 12991–12998. 2011.

.
12“Approximations and asymptotics of upper hedging prices in multinomial models”,
by Ryuichi Nakajima, Masayuki Kumon, A.Takemura and Kei Takeuchi. Japan
Journal of Industrial and Applied Mathematics, 25, 1–21. 2012.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

4 / 26

Introduction

List of Tokyo papers.
13“Convergence of random series and the rate of convergence of strong law of large
numbers in game-theoretic probability”, by Kenshi Miyabe and A.Takemura.
Stochastic Processes and their Applications, 122, 1–30. 2012.

.
14“Bayesian logistic betting strategy against probability forecasting”, Stochastic
Analysis and Applications, 31, 214–234. Masayuki Kumon, Jing Li, A.Takemura
and Kei Takeuchi. 2013.

.
15“The law of the iterated logarithm in game-theoretic probability with quadraticand stronger hedges”, Stochastic Processes and their Applications. Kenshi Miyabe
and A.Takemura. 2013.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

5 / 26

Introduction

Background on game-theoretic probability (GTP)
Kolmogorov’s Grundbegriffe (1933) established measure theoretic
probability. It justifies mathematical operations such as limitingoperations.
On this firm ground, probability theory found applications in many
fields.
Axiomatic construction: probability is not defined by itself, like“points” or “lines”. This actually broadened the applicability ofprobability theory.
“Probability is just the Lebesgue measure”, K.Ito, 1944.
On the other hand, foundational arguments, such as Richard vonMises’s collectives, have been almost forgotten by probabilists.
Kolmogorov himself was somewhat hesitant:→ proposal of Kolmogorov complexity
Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

6 / 26

Introduction

Shafer and Vovk (2001)
Shafer and Vovk (2001) “Probability and Finance, It’s Only a Game!”
appeared.
Vladimir Vovk (PhD, 1988, Moscow State U) is one of the last
students of Kolmogorov.
Around 2003, Takeuchi started to tell me that the book is very
interesting. I gave a course on GTP for studying the book.
In my opinion, at present it is the only alternative framework tomeasure-theoretic probability.
Important theorems, such as the strong law of large numbers (SLLN),
central limit theorem (CLT), the law of the iterated logarithm (LIL),
can be proved in game-theoretic probability without requiring measure
theory.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

7 / 26

Introduction

Strength and weakness of game-theoretic probability(GTP)
StrengthSome clever proofs are very short. For example, even high school
students can understand game-theoretic proof of SLLN.
Black-Scholes formula and CLT are equivalent. In Shafer and Vovk,
CLT and the Black-Scholes formula are proved “simultaneously”.
Their proof shows that these are equivalent. (They do not use
characteristic functions, but use the heat equation.)
In GTP, the set of measure-zero is often more explicitly treated, by an
explicit betting strategy with its capital diverging to +∞ on the set.
Probability is not assume a priori. A game is assumed. Under thegame, the players are forced to act probabilistically. (Why stock
prices look random?)
Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

8 / 26

Introduction

Strength and weakness of GTP
Weakness
Some proofs are, of course, almost the same in measure-theoretic
probability and GTP.
Some simple notions under usual probability, such as independence,
identical distribution, are not easy to formulate. (GTP inherently
assumes martingale.)In 2001 book, continuous stochastic processes were treated by
nonstandard analysis, which was probably not very convincing tomany people.
This difficulty was overcome based on the idea in “A new formulationof asset trading games in continuous time . . .” by Takeuchi, Kumon
and Takemura, Bernoulli, 2009, and completely generalized in“Continuous-time trading and the emergence of probability” by
Vladimir Vovk, Finance and Stochastics, 2012.
Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

9 / 26

Introduction

Introduction to GTP by a coin-tossing game
Complete information game between players (two players version)
Skeptic (statistician, investor) bets on some outcome.
Reality (nature, market) decides the outcome.

Skeptic → Reality → S → R → .
They play in turn.
One round: (Skeptic’s turn, Reality’s turn) in this ordern = 1, 2, . . . denote rounds.
Skeptic’s initial capital: K0 = 1

At each round, Skeptic first announces how much he bets: Mn ∈ R.
Mn can be any real number and can be arbitrarily small. Negative Mnallowed (short selling).

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

10 / 26

Introduction

Introduction to GTP by a coin-tossing game
After knowing Mn , Reality chooses the outcome xn = 0 or xn = 1.
Payoff to Skeptic : Mn (xn − p), where the “price” 0 < p < 1 of the“ticket” is given before the game. p is the success probability or the“risk neutral probability”.
Skeptic’s capital changes as

Kn = Kn−1 + Mn (xn − p).

In summary:
K0 = 1, 0 < p < 1: given
FOR n = 1, 2, . . .
Skeptic announces Mn ∈ R.
Reality announces xn ∈ {0, 1}.
Kn := Kn−1 + Mn (xn − p).
END FOR
Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

11 / 26

Introduction

Introduction to GTP by a coin-tossing game
Reality can choose the sign of xn − p as the opposite of the sign ofMn . Therefore Reality can always decrease Skeptic’s capital.
No-win situation for Skeptic?
But then Reality is forced to observe SLLN!
Theorem There exists Skeptic’s strategy P. (He can announce
P even before the start of the game.) If Skeptic uses P, then heis never bankrupt and whenever Reality violateslim

1n→∞ n(x1 + · · · + xn ) = p,thenlim Kn = ∞.

n→∞Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

12 / 26

Introduction

Introduction to GTP by a coin-tossing game“In the coin-tossing game there exists a non-negative martingale
which succeeds on the set”
{ x1 x2 . . . |x1 + · · · + xn%→ p} ⊂ {0, 1}∞n(1)We say that in the coin-tossing game “Skeptic can force SLLN”.
Reality can also have strategies (not fully explored yet).
Bounded forecasting game: (1) is still true even if Reality can choose
any real number in [0, 1], and {0, 1}∞ is replaced by [0, 1]∞ .

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

13 / 26

Introduction

Coin-tossing game with the third player
Complete information game between three players.
Forecaster decides the price of the ticket
Skeptic bets on the outcome.
Reality decides the outcome.
K0 = 1: given
FOR n = 1, 2, . . .
Forecaster announces pn ∈ [0, 1].
Skeptic announces Mn ∈ R.
Reality announces xn ∈ {0, 1}.
Kn := Kn−1 + Mn (xn − pn ).
END FORTakemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

14 / 26

Introduction

Coin-tossing game with the third player

In this game Skeptic can forcen1!
(xi − pi ) = 0n→∞ nlim

i=1

He can also force!
npn < ∞ ⇔!
nxn < ∞

Forecaster can also have strategies.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

15 / 26

Introduction

Bayesian Skeptic for a coin-tossing game (without
Forecaster)

Although the proof of SLLN in Shafer and Vovk (2001) is short, wegave an alternative proof (just for a coin-tossing game) based on
Bayesian Skeptic (in Stochastic Analysis and Applications, 2008).
We found that the strategy was already discussed in Jean Ville (1939ls ) “Étude critique de la notion de collectif” (English translation byG.Shafer).
Kullback-Leibler divergence very naturally comes out from ourstrategy. So Ville might have known KL-divergence.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

16 / 26

Introduction

Bayesian Skeptic for a coin-tossing game (withoutForecaster)
We suppose that Skeptic uses a strategy based on a beta priordistribution for pp ∼ p α−1 (1 − p)β−1 /B(α, β),where α, β are prior numbers of heads and tails.
Then his prediction of success probability for the n-th round isp̂n =“Number of heads up to n − 1” + α.
n−1+α+β

Consider Skeptics strategy

P : Mn = Kn−1p̂n − pp(1 − p)In the following we let 1 = α = β for notational simplicity (uniformprior).
Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

17 / 26

Introduction

Bayesian Skeptic for a coin-tossing gameIf Skeptic uses this P, then his capital at time n is explicitly given as"1 htnnhn !tn !
0 p (1 − p) dp
Kn ==,(2)(n + 1)!p hn (1 − p)tn
p hn (1 − p)tn
where hn = x1 + · · · + xn (# of heads), and tn = n − hn .
Proof is easy by induction
This is a likelihood ratio of Bayes marginal distribution and thebinomial distribution with the risk neutral probability p.
In general, a capital process Kn is “always” a likelihood ratio.
LR process is a non-negative martingale process.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

18 / 26

Introduction

KL divergence and capital process
Stirling’s formula for x!
#$1log x! = x +log x − x + O(1) = x log x − x + O(log x)
2
Asymptotic behavior of log Knlog Kn = log hn ! + log tn ! − log(n + 1)! − hn log p − tn log(1 − p)
= hn log hn + tn log tn − n log n − (hn + tn − n)− hn log p − tn log(1 − p) + O(log n)hntn= hn log+ tn log+ O(log n).
npn(1 − p)

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

19 / 26

Introduction

KL divergence and capital process

The sum of the first two terms is the KL divergence.
Hence% hn)p) + O(log n).
n
If hn /n deviates%from &p, then Skeptic’s capital Kn grows exponentiallywith the rate D hnn )p .
log Kn = nDThis is the “large deviation principle”.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

20 / 26

Introduction

Non-negative martingales and likelihood ratios
As a standard textbook material, it can be easily checked that in themeasure-theoretic framework the following two things are equivalent.
1. Non-negative martingales with expected value 1.
2. Likelihood ratios
Martingale ⇒ LR
Let Fn , n = 0, 1, 2, . . . be a filtration.
Let F = F∞ be the smallest σ-field containing them.
Fix a probability measure P on F and let Kn , n = 0, 1, 2, . . . be a
non-negative martingale under P with E (Kn ) = 1, ∀n.
Define Qn on Fn by'Qn (A) =Kn dP, A ∈ Fn .
ATakemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

21 / 26

Introduction

Non-negative martingales and likelihood ratios
Then it is an easy exercise to show that Qn ’s are a consistent (i.e.
Qn (A) = Qn+1 (A), ∀A ∈ Fn ) family of distributions and Kn is thelikelihood ratio: Kn = dQn /dPn .
LR ⇒ Martingale

Let Q1 , Q2 , . . . be a consistent family of probability distributions on
Fn , n = 0, 1, . . . , such that each Qn is absolutely continuous with P.
DefinedQn.
dP''dQnE (Kn ) =dP =dQn = Qn (Ω) = 1.
Ω dPΩ
Kn =Then

Furthermore it can be easily shown that E (Kn+1 |Fn ) = Kn and this isequivalent to the consistency condition.
Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

22 / 26

Introduction

Non-negative martingales and likelihood ratio (GTP)

From GTP, the capital process Kn ≥ 0 is a non-negative martingale
with expected value 1 under any risk neutral probability measure.
However not all non-negative measure-theoretic martingales withexpected value 1 can be realized as a capital process. It depends on
how rich is the move space of Skeptic, i.e., what kind of strategies areallowed to Skeptic.
If the game is “complete”, such as the coin-tossing game, then theconverse is true.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

23 / 26

Introduction

A sequential test can be constructed from betting
Let Kn be a non-negative martingale with E (Kn ) = 1.
By Markov inequality

P(sup Kn ≥ 1/α) ≤ α.
nHence a sequential testing procedure with the level of significance α
is constructed by rejecting the null hypothesis as soon as Kn ≥ 1/α.

Suppose that the data generating process for X1 , X2 , . . . , is given as anull hypothesis. If you are allowed to bet on X1 , X2 , . . . and if you
can multiply your capital 20-fold, then the null hypothesis is rejectedwith the significance level of 5%.
See for example, “New procedures for testing whether stock priceprocesses are martingales” in Computational Economics, 2010.
Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

24 / 26

Introduction

A sequential test can be constructed from betting

In this sequential setting, betting strategies need not be formal or
fully specified. Any betting is OK as long as the future observations
are never used (of course).
On the other hand, when we obtain a batch sample of size n, weoften have to be careful that we should have decided to use aparticular procedure before seeing the actual data.
This “hindsight” effect even exists in the maximized likelihood. Thenvarious information criteria are needed to take the hindsight effectinto consideration.
Compared to the standard batch sample setting, use of betting in asequential test can be more informal.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

25 / 26

Introduction

Summary of the talkI have discussed background for game-theoretic probability.
I did some mathematics of Bayesian betting strategy for coin-tossing
games.
I tried to explain why likelihood ratio appears as the capital process.
I indicated that capital process (i.e. LR) can be used as a measure ofdeparture from the null hypothesis, leading to a simple sequential test.

Takemura (Univ. of Tokyo)

Game-theoretic probability

May 14, U.Tokyo

26 / 26