1. Introduction

The St. Petersburg game, paradox, or lottery is more than \(300\) years old, and has never ceased to surprise mathematicians, statisticians, philosophers, economists, and others. It is a situation where a naive decision criterion, which takes only the expected value into account, predicts a course of action that presumably no actual person would be willing to take.

In its original form, a single trial of the St. Petersburg game consists in tossing a fair coin until it first lands heads and the player wins \(2^k\) dollars if this happens on the \(k\)th toss. Hence, if \(X\) is the gain at a single trial, we have

$$ P(X=2^k)=2^{-k},\quad P(X>c)=2^{-\lfloor{\log_2 c}\rfloor} \qquad \text{for}\quad k=1,2,\dots,\quad c\ge 1,$$
(1)

where \(\log_2\) stands for the logarithm to the base \(2\), \(\lfloor{x}\rfloor\) denotes the floor of \(x\) (i.e., the largest integer not exceeding \(x\)), and \(P(\,\cdot\,)\) denotes the probability of the event between brackets.

Let \((X_n)_{n\ge 1}\) be i.i.d. (independent and identically distributed) random variables, all distributed like \(X\), and representing the player’s gains in a sequence of independent repetitions of the St. Petersburg game. There is strong motivation in describing the distribution of

$$S_n:=X_1+\cdots+X_n \text{ -- the player's total winnings in } n \text{ games}.$$

More precisely, the striking point is that the expectation \(E(S_n)\) is infinite; in spite of this, Feller [1] proved that \(S_n/(n\log_2 n)\to 1\) in probability as \(n\to \infty\). It was subsequently shown that, with probability one, the set of limit points of the sequence \(\{S_n/(n\log_2 n)\}_{n\ge 2}\) is the interval \([1,\infty)\) (see Chow and Robbins [2] and Adler [3]).

Moreover, Csörgő and Simons [4] showed that, with probability one, \(S_n\) is asymptotic to \(n\log_2 n\) if the largest gains are ignored (i.e., the entry fee is fair except for the largest gains). As shown by Vardi [5], this asymptotic equality is very rarely interrupted by a large gain that puts the player ahead for a relatively short period. Moreover, Martin-Löf [6] proved that the premium per game \(2^m +n\) has only a small probability \(\approx 1.8 \times 2^{-m}\)) of being insufficient to cover the accumulated gains \(S_{2^n}\).

2. Main Results

And now we come back to the probabilities of the accumulated gain \(S_n\) in the St. Petersburg game. Hu and Nyrhinen [7] and Gantert [8] proved independently the following result for the moderate (or polynomial) size gains \(n^b\), for some \(b>1\) fixed. Namely,

$$\lim_{n\to \infty}\frac{\log_2 P(S_n > n^b)}{\log_2 n}=1-b. $$
(2)

When the gains have large (or exponential) size \(b^n\), for some \(b>1\) fixed, it is expected that the corresponding probabilities have much smaller values than those in the polynomial case. Indeed, Vardi [5] and Stoica [9] suggested that the normalization in formula (2) needs to be changed in the case of large gains, and in the sequel we will fulfill the task. More precisely, we will prove the following theorem.

Theorem.

Let \((X_n)_{n\ge 1}\) be the player’s gains in independent St. Petersburg games, and let \(S_n=X_1+X_2+\cdots+X_n\) be the player’s total winnings in \(n\) games. Then, for every \(b >1\) fixed, we have

$$\lim_{n\to \infty}\frac{\log_2 P(S_n > b^n)}{n}=-\log_2b. $$
(3)

Proof.

Let’s get to work, then. We will prove below that:

$$\limsup_{n\to \infty}\frac{\log_2 P(S_n > b^n)}{n} \le -\log_2 b \le \liminf_{n\to \infty} \frac{\log_2 P(S_n > b^n)}{n}\,, $$
(4)

from which formula (3) follows immediately, i.e., the lim of the left-hand side of (3) exists and equals the right-hand side of (3). The right-hand side inequality in (4) requires two rather short and easy ingredients (Lemmas 1 and 2 below), whereas the left-hand side inequality in (4) requires a longer and more laborious argument (Lemma 3 below) à la Hu and Nyrhinen [1].

Lemma 1.

With the above notation and assumptions,

$$\limsup_{n\to \infty}\frac{\log_2 P(X > b^n)}{n}=-\log_2 b.$$

Proof.

The second formula in (1) implies that:

$$\frac{1}{c} \le P(X>c)<\frac{2}{c}\qquad \text{for}\quad c\ge 1.$$

Take \(c:=b^n\) in the above inequalities (recall that \(b>1\) by hypothesis); then apply \(\log_2\) throughout, divide by \(n\), and finally let \(n \to \infty\).

Lemma 2.

Let \(\delta >0\) be fixed. Then

$$1-[1-(b^n)^{-1-\delta}]^n \ge \frac{n}{2} \cdot (b^n)^{-1-\delta}\quad \textit{for large}\quad n.$$

Proof.

As \(b>1\), we have that \(n\cdot (b^n)^{-1-\delta} \to 0\). Choose \(n\) sufficiently large that \(n\cdot (b^n)^{-1-\delta}<1/2\). Then

$$\begin{aligned} \, [1-(b^n)^{-1-\delta} \bigr]^n &\le \exp[-n \cdot (b^n)^{-1-\delta}] \\& \le 1-n\cdot (b^n)^{-1-\delta}+[ n\cdot (b^n)^{-1-\delta}]^2 \le 1-\frac{1}{2}\cdot n \cdot (b^n)^{-1-\delta}; \end{aligned}$$

here the first inequality follows from

$$(1-x)^n \le \exp(-nx)\qquad\text{for all}\quad x\in (0,1),\quad n\ge 1,$$

the second inequality, from

$$\exp(-x)\le 1-x+x^2\qquad\text{for}\quad x\in (0,1),$$

and the third, from our choice for large \(n\).

Proof of the second inequality in (4).

Let \(\delta>0\) be fixed. By Lemma 1, we have

$$\log_2 P[X>b^n] \ge -(1+\delta) \cdot n \cdot \log_2 b \quad \text{for large}\quad n. $$
(5)

Therefore,

$$\begin{aligned} \, P(S_n > b^n)& \ge P[\max(X_1,\dots,X_n) > b^n] = 1-[1-P(X>b^n)]^n \nonumber \\& \ge 1- [1- (b^n)^{-1-\delta}]^n \ge \frac{1}{2} \cdot n \cdot (b^n)^{-1-\delta}; \end{aligned}$$
(6)

here the first inequality follows from that all \(X_1,\dots,X_n\) are nonnegative, and hence

$$\text{if}\quad \max(X_1,\dots,X_n) > b^n,\qquad \text{then}\quad S_n > b^n,$$

and \(P\) is a monotonically increasing function with respect to the set inclusion; the second inequality follows from that \(X_1, \ldots, X_n\) are independent and all distributed like \(X\), hence

$$\begin{aligned} \, & P[\max(X_1,\dots,X_n) \le b^n]= P(X_1,\dots,X_n \le b^n)= \prod_{i=1}^n P(X_i \le b^n) \\&\qquad =\prod_{i=1}^n [1-P(X_i > b^n)]= \prod_{i=1}^n [1- P(X > b^n)]=[1-P(X>b^n)]^n; \end{aligned}$$

the third inequality follows from (5) for large \(n\); finally, the last inequality holds for large \(n\) by Lemma 2.

Apply \(\log_2\) in (6) and obtain

$$\log_2 P(S_n > b^n) \ge -1+\log_2 n-(1+\delta) \cdot n \cdot \log_2 b\qquad\text{for large}\quad n.$$

as \(\delta>0\) is arbitrary, the latter inequality gives

$$\log_2 P(S_n > b^n) \ge -1+\log_2 n- n \cdot \log_2 b\qquad\text{for large}\quad n;$$

divide by \(n\) and obtain

$$\liminf_{n\to \infty}\frac{\log_2 P(S_n > b^n)}{n} \ge -\log_2 b.\square$$

Lemma 3.

Let \(t>0\) . With the above notation and assumptions, for any \(n\ge 1\) ,

$$P(S_n>b^n)\le n\cdot P\biggl[X>\biggl(\frac{b^n}{t^b}\biggr)\biggr]+ (n\cdot {b^{-n/b}})^{t^b} \cdot \exp(t) \cdot E^{t^b}(X^{1/b}). $$
(7)

Proof.

We will adapt to our set-up several arguments from Hu and Nyrhinen [7]. Write

$$\widetilde{X}_n:=X_n\cdot\boldsymbol{1}_{[X_n\le(b^n/t^b)]}, \quad \widetilde{S}_n:=\widetilde{X}_1+\cdots+\widetilde{X}_n \qquad\text{for}\quad n\ge 1.$$

The independence of \((X_n)_{n \ge 1}\) implies that \((\widetilde{X}_n)_{n\ge 1}\) are also independent random variables. We then have the set-inclusion equation

$$\{S_n > b^n\} \subseteq \biggl(\,\bigcup_{i=1}^n\{X_i \ne \widetilde{X}_i\}\biggr) \cup \{\widetilde{S}_n > b^n\},$$

which is apparent from the (almost) obvious equation

$$\{\widetilde{S}_n \le b^n\} \cap \biggl(\,\bigcap_{i=1}^n\{X_i=\widetilde{X}_i\}\biggr)\subseteq \{S_n \le b^n\}.$$

We thus obtain, for all \(n\ge 1\),

$$P(S_n>b^n) \le n\cdot P\biggl[X>\biggl(\frac{b^n}{t^b}\biggr)\biggr]+ P(\widetilde{S}_n>b^n), $$
(8)

as

$$P\biggl(\,\bigcup_{i=1}^n\{X_i \ne \widetilde{X}_i\}\biggr) \le n\cdot P(\{X_i \ne \widetilde{X}_i\}) =n\cdot P\biggl(X_i > \biggl(\frac{b^n}{t^b}\biggr)= n\cdot P(X> \biggl(\frac{b^n}{t^b}\biggr)\biggr)$$

(recall that \(X_1,\dots,X_n\) are (all) distributed like \(X\))

Next, we estimate the second term on the right hand side of (8). Note that, for any \(x>0\) and \(i=1,\ldots,n\),

$$\begin{aligned} \, \nonumber E[\exp(x \widetilde{X}_i)]&= E[\boldsymbol{1}_{(\widetilde{X}_i >0)} \cdot \exp(x \widetilde{X}_i)]+P(\widetilde{X}_i=0) \\ \nonumber &=E\biggl[\frac{\exp(x \widetilde{X}_i)-1}{{\widetilde{X}_i}^{1/b}} \cdot \widetilde{X}_i^{1/b}\cdot \boldsymbol{1}_{(\widetilde{X}_i >0)}\biggr]+1 \\ \nonumber & \le \biggl(\frac{t}{b^{n/b}}\biggr) \cdot \biggl\{\exp\biggl[\frac{(x\cdot b^n)}{t^b}\biggr]-1\biggr\} \cdot E(X_i^{1/b})+1 \\& \le \exp\biggl\{\biggl(\frac{t}{b^{n/b}}\biggr) \cdot \biggl\{\exp\biggl[\frac{(x\cdot b^n)}{t^b}\biggr]-1\biggr\} \cdot E(X_i^{1/b})\biggr\}. \end{aligned}$$
(9)

In the first and second equalities, we used that \(X_i\) is nonnegative and some little algebraic tricks. In the first inequality, we used that

$$\text{the function } y\to y^{-1/b} \cdot [\exp(xy)-1] \text{ is monotonically increasing for } y>0,$$

together with the fact and that \(\widetilde{X}_i \le {b^n}/{t^b}\); and the second inequality follows from the inequality

$$e^y \ge y+1\qquad\text{for}\quad y>0.$$

Hence, for any \(x>0\) and \(i=1,\dots,n\), we have

$$\begin{aligned} \, P(\widetilde{S}_n > b^n)&= P[\exp(x\cdot \widetilde{S}_n) > \exp(x\cdot b^n)] \le \exp(-x\cdot b^n)\cdot\prod_{i=1}^n E [\exp(x\cdot \widetilde{X}_i)] \nonumber \\& \le \exp(-x\cdot b^n) \cdot \exp\biggl\{\biggl(\frac{t}{b^{n/b}}\biggr) \cdot \biggl\{\exp\biggl[\frac{(x\cdot b^n)}{t^b}\biggr]-1\biggr\} \cdot \sum_{i=1}^n E(X_i^{1/b})\biggr\} \nonumber \\& =\exp\biggl\{n\cdot E(X^{1/b})\cdot\biggl(\frac{t}{b^{n/b}}\biggr) \cdot\biggl\{\exp\biggl[\frac{(x\cdot b^n)}{t^b}\biggr]-1\biggr\} - x\cdot b^n\biggr\}. \end{aligned}$$
(10)

To obtain the first inequality in (10), we applied Markov’s inequality

$$P(Y>a)\le \frac{E(Y)}{a}\,,\quad\text{if } Y \text{ is a nonnegative random variable and } a > 0,$$

to \(Y=x\cdot \widetilde{S}_n\) and \(a= x\cdot b^n\) and used that \(\exp(x\cdot \widetilde{X}_1),\dots,\exp(x\cdot \widetilde{X}_n)\) are independent random variables for all \(x>0\) (because \(\widetilde{X}_1,\dots,\widetilde{X}_n\) are independent), hence

$$E[\exp(x\cdot \widetilde{S}_n)]= E\prod_{i=1}^n \exp(x\cdot \widetilde{X}_i)= \prod_{i=1}^n E[\exp(x\cdot \widetilde{X}_i)];$$

the second inequality follows from (9); finally, the last equality follows from that \(X_1,\dots,X_n\) are identically distributed, hence they have the same expectation as \(X\).

Choose

$$x:=\biggl(\frac{t^b}{b^n}\biggr) \cdot \log\biggl\{\frac{b^{n/b}}{[n \cdot E(X^{1/b})]}+1\biggr\}$$

in (10) and obtain

$$P(\widetilde{S}_n > b^n)\le\exp\biggl\{t-t^b \cdot \log\biggl\{\frac{b^{n/b}}{[n \cdot E(X^{1/b})]}+1\biggr\}\biggr\} \le \exp(t) \cdot \biggl[\frac{n\cdot E (X^{1/b})}{b^{n/b}}\biggr]^{t^b}.$$

We finally obtain (7) by (8).

Proof of the first inequality in (4).

From inequality (6) in Lemma 3, for any \(t>0\) and any natural \(n\ge 1\), we obtain

$$\begin{aligned} \, P(S_n > b^n)&\le n\cdot P\biggl[X>\biggl(\frac{b^n}{t^b}\biggr)\biggr]+ (n\cdot b^{-n/b})^{t^b} \cdot \exp(t) \cdot E^{t^b}(X^{1/b}) \\& \le \frac{(n\cdot t^b)}{b^n}+ (n\cdot {b^{-n/b}})^{t^b} \cdot \exp(t) \cdot E^{t^b}(X^{1/b}) \end{aligned}$$

(the last inequality follows from Markov’s inequality and the equality \(E(X)=1\)).

Next, apply \(\log_2\) in the latter inequality, use that

$$\log_2(x+y) \le 1+\max\{\log_2 x,\log_2 y\} \qquad\text{for all}\quad x,y>0,$$

and deduce that, for any \(t>0\) and \(n\geq 1\), we have:

$$\begin{aligned} \, &\log_2 P(S_n > b^n) \\&\ \ \le 1+\max\bigl\{b\cdot \log_2 t+\log_2 (n\cdot b^{-n}), t\cdot \log_2 e+t^b \cdot \log_2 E(X^{1/b})+ t^b \cdot \log_2 (n\cdot b^{-n/b})\bigr\}. \end{aligned}$$

Further divide by \(n\) and obtain

$$\begin{aligned} \, & \limsup_{n\to \infty}\frac{\log_2 P(S_n > b^n)}{n} \\&\qquad \le \limsup_{n\to \infty}\frac{1}{n} \cdot \max\biggl\{\log_2 n-n\cdot \log_2 b, t^b\cdot\biggl[\log_2 n-\biggl(\frac{n}{b}\biggr) \cdot \log_2 b\biggr]\biggr\} \\&\qquad =\max\biggl\{-\log_2 b,-t^b \cdot \frac{(\log_2 b)}{b}\biggr\}=-\log_2 b \end{aligned}$$

(the last equality follows by letting \(t\) increase until the second term in the latter maximum becomes smaller than \(-\log_2 b\)).