Gambling Systems

A gambler with initial capital $a$ plays until his fortune increases $b$ units or he is ruined. Suppose that $\rho >1$. The chance of success is multiplied by $1+\theta$ if his initial capital is infinite instead of $a$. Show that $0<\theta <\left(\rho^{a}-1\right)^{-1}< (a(\rho -1))^{-1}$; relate to Example 7.3.

As shown on p. 94, there is probability 1 that the gambler either achieves his goal of $c$ or is ruined. For $p \neq q$, deduce this directly from the strong law of large numbers. Deduce it (for all $p$ ) via the Borel-Cantelli lemma from the fact that if play never terminates, there can never occur $c$ successive +1 's.

$6.12 \uparrow$ If $V_{n}$ is the set of $n$-long sequences of $\pm 1$ 's, the function $b_{n}$ in (7.9) maps $V_{n-1}$ into $\left\{ 0,1\right\}$. A selection system is a sequence of such maps. Although there are uncountably many selection systems, how many have an effective

*This topic may be omitted ${ }^{\mathrm{t}}$ For each $\epsilon$, however, there exist optimal policies under which the bet never exceeds $\epsilon$; see Dubins Savage. description in the sense of an algorithm or finite set of instructions by means of which a deputy (perhaps a machine) could operate the system for the gambler? An analysis of the question is a matter for mathematical logic, but one can see that there can be only countably many algorithms or finite sets of rules expressed in finite alphabets.

Let $Y_{1}^{(\sigma )}, Y_{2}^{(\sigma )}, \ldots$ be the random variables of Theorem 7.1 for a particular system $\sigma$, and let $C_{\sigma }$ be the $\omega$-set where every $k$-tuple of $\pm 1$ 's ( $k$ arbitrary) occurs in $Y_{1}^{(\sigma )}(\omega ), Y_{2}^{(\sigma )}(\omega ), \ldots$ with the right asymptotic relative frequency (in the sense of Problem 6.12). Let $C$ be the intersection of $C_{\sigma }$ over all effective selection systems $\sigma$. Show that $C$ lies in $\mathscr {F}$ (the $\sigma$-field in the probability space $(\Omega , \mathscr {F}, P)$ on which the $X_{n}$ are defined) and that $\mathbb {P}\left(C\right)=1$. A sequence $\left(X_{1}(\omega ), X_{2}(\omega ), \ldots \right)$ for $\omega$ in $C$ is called a coliective: a subsequence chosen by any of the effective rules $\sigma$ contains all $k$-tuples in the correct proportions

Let $D_{n}$ be 1 or 0 according as $X_{2 n-1} \neq X_{2 n}$ or not, and let $M_{k}$ be the time of the $k$ th 1-the smallest $n$ such that $\sum_{i=1}^{n} D_{i}=k$. Let $Z_{k}=X_{2 M_{i}}$. In otner words, look at successive nonoverlapping pairs $(X_{2 n-1}, X_{2 n})$, discard accordant $\left(X_{2 n-1}=X_{2 n}\right)$ pairs, and keep the second element of discordant $(X_{2 n-1} \neq X_{2 n})$ pairs. Show that this process simulates a fair coin: $Z_{1}, Z_{2}, \ldots$ are independent and identically distributed and $\mathbb {P}\left(Z_{k}=+1\right)=\mathbb {P}\left(Z_{k}=-1\right)=\frac{1}{2}$, whatever $p$ may be. Follow the proof of Theorem 7.1.

Suppose that a gambler with initial fortune 1 stakes a proportion $\theta (0<\theta <1)$ of his current fortune: $F_{0}=1$ and $W_{n}=\theta F_{n-1}$. Show that $F_{n}=\Pi_{k=1}^{n}\left(1+\theta X_{k}\right)$ and hence that

Show that $F_{n} \rightarrow 0$ with probability 1 in the subfair case.

In "doubling," $W_{1}=1, W_{n}=2 W_{n-1}$, and the rule is to stop after the first win. For any positive $p$, play is certain to terminate. Here $F_{T}=F_{6}+1$, but of course infinite capital is required. If $F_{0}=2^{k}-1$ and $W_{n}$ cannot exceed $F_{n-1}$, the probability of $F_{\tau }=F_{0}+1$ in the fair case is $1-2^{-k}$. Prove this via Theorem 7.2 and also directly.

In "progress and pinch," the wager, initially some integer, is increased by 1 after a loss and decreased by 1 after a win, the stopping rule being to quit if the next bet is 0. Show that play is certain to terminate if and only if $p \geq \frac{1}{2}$. Show that $F_{\tau }=F_{0}+\frac{1}{2} W_{1}^{2}+\frac{1}{2}(\tau -1)$. Infinite capital is required.

Here is a common martingale. Just before the $n$th spin of the wheel, the gambler has before him a pattern $x_{1}, \ldots , x_{k}$ of positive numbers ( $k$ varies with $n)$. He bets $x_{1}+x_{k}$, or $x_{1}$ in case $k=1$. If he loses, at the next stage he uses the pattern $x_{1}, \ldots , x_{k}, x_{1}+x_{k}\left(x_{1}, x_{1}\right.$ in case $\left.k=1\right)$. If he wins, at the next stage he uses the pattern $x_{2}, \ldots , x_{k-1}$, unless $k$ is 1 or 2, in which case he quits. Show that play is certain to terminate if $p>\frac{1}{3}$ and that the ultimate gain is the sum of the numbers in the initial pattern. Infinite capital is again required.

Suppose that $W_{k}=1$, so that $F_{k}=F_{0}+S_{k}$. Suppose that $p \geq q$ and $\tau$ is a stopping time such that $1 \leq \tau \leq n$ with probability 1. Show that $\mathbb {E}\left[F_{\tau }\right] \leq \mathbb {E}\left[F_{n}\right]$, with equality in case $p=q$. Interpret this result in terms of a stock option that must be exercised by time $n$, where $F_{0}+S_{k}$ represents the price of the stock at time $k$.

For a given policy, let $A_{n}^{*}$ be the fortune of the gambler's adversary at time $n$. Consider these conditions on the policy. (i) $W_{n}^{*} \leq F_{n-1}^{*}$; (ii) $W_{n}^{*} \leq A_{n-1}^{*}$; (iii) $F_{n}^{*}+A_{n}^{*}$ is constant. Interpret each condition, and show that together they imply that the policy is bounded in the sense of (7.24).

Show that $F_{\tau }$ has infinite range if $F_{0}=1, W_{n}=2^{-n}$, and $\tau$ is the smallest $n$ for which $X_{n}=+1$.

Let $u$ be a real function on $[0,1], u(x)$ representing the utility of the fortune $x$. Consider policies bounded by 1 ; see (7.24). Let $Q_{\pi }\left(F_{0}\right)=\mathbb {E}\left[u\left(F_{\tau }\right)\right]$; this represents the expected utility under the policy $\pi$ of an initial fortune $F_{0}$. Suppose of a policy $\pi_{0}$ that

and that

Show that $Q_{\pi }(x) \leq Q_{\pi_{0}}(x)$ for all $x$ and all policies $\pi$. Such a $\pi_{0}$ is optimal. Theorem 7.3 is the special case of this result for $p \leq \frac{1}{2}$, bold play in the role of $\pi_{0}$, and $u(x)=1$ or $u(x)=0$ according as $x=1$ or $x<1$.

The condition (7.34) says that gambling with policy $\pi_{0}$ is at least as good as not gambling at all; (7.35) says that, although the prospects even under $\pi_{0}$ become on the average less sanguine as time passes, it is better to use $\pi_{0}$ now than to use some other policy for one step and then change to $\pi_{0}$.

The functional equation (7.30) and the assumption that $Q$ is bounded suffice to determine $Q$ completely. First, $Q(0)$ and $Q(1)$ must be 0 and 1, respectively, and so (7.31) holds. Let $T_{0} x=\frac{1}{2} x$ and $T_{1} x=\frac{1}{2} x+\frac{1}{2}$; let $f_{0} x=p x$ and $f_{1} x=p+q x$. Then $Q\left(T_{u_{1}} \cdots T_{u_{n}} x\right)=f_{u_{1}} \cdots f_{u_{n}} Q(x)$. If the binary expansions of $x$ and $y$ both begin with the digits $u_{1}, \ldots , u_{n}$, they have the form $x=T_{u_{1}} \ldots T_{u_{n}} x^{\prime }$ and $y=T_{u_{1}} \cdots T_{u_{n}} y^{\prime }$. If $K$ bounds $Q$ and if $m=\max \left\{ p, q\right\}$, it follows that $\left|Q(x)-Q(y)\right| \leq K m^{n}$. Therefore, $Q$ is continuous and satisfies (7.31) and (7.33).

$A$ and $B$ play the following game. They flip a coin, if the outcome is a head $A$ gets 1 dollar from $B$, otherwise $A$ pays 1 dollar to $B$. Initially, each of them has 3 dollars. The game terminates when either $A$ or $B$ loses all his money. What is the probability $p_{n}$ that $n$ flips are needed?

A compulsive gambler is never satisfied. At each stage he wins $£ 1$ with probability $p$ and loses $£ 1$ otherwise. Find the probability that he is ultimately bankrupted, having started with an initial fortune of $£ k$.

Two players $A$ and $B$, having capitals $a$ and $b$ respectively, play a game of chance consisting of individual rounds. Suppose that in each round player $A$ wins with probability $p$ and loses with probability $1-p$. After each round, the loser pays 1 ruble to the winner. The game continues until one of the players is ruined. Find the probability that the second player is ruined, if:

Suppose that, under the conditions of the previous problem (see 7.32), player $A$ wins with probability $p$ and loses with probability $q$; in addition, a draw is possible with probability $r = 1 - p - q$. Find the probability that the second player is ruined.

Consider this doubling-up betting system. You are able to make the following wager as many times as you want: choose heads or tails on a completely fair coin flip. If you wager $\$ \mathrm{X}$, you win $\$ \mathrm{X}$ if you are right and lose $\$ \mathrm{X}$ if you are wrong. Your doubling-up system is designed to win $\$ 1$ to buy a soda, no matter what happens. Your initial bet is $\$ 1$. If you win, you quit and buy your soda. If you lose, you now bet $\$ 2$. If you win your second bet, you win $\$ 2$, which covers the $\$ 1$ loss on your first bet and allows you to quit and buy your soda. If you lose your first two bets, your third bet is for $\$ 4$. If you lose that bet, your fourth bet is for $\$ 8$. This doubling of the bet after every loss ensures that when you do win (and, surely, you will win eventually), you will have a net profit of $\$ 1$ and can buy your soda. Now suppose that you only have a few thousand dollars, so that if you lose 11 bets in a row, you will have lost $\$ 2,047$ and cannot afford to double your 11th bet ($\$ 1,024$) in order to make a 12th bet ($\$ 2,048$)-you must stop betting and don't get your free soda. What is the expected value of this doubling-up system?

Two gamblers, Whale and Fish, are going to play a game of chance until one is bankrupt. Whale starts with $\$ 90,000$; Fish starts with $\$ 10,000$. The game they play is a fair game (e.g., calling coin flips) that each is equally likely to win. Either player can bet any amount that can be matched by the other player; for example, if Fish has $\$ 8,000$, they can wager up to $\$ 8,000$ on the next game. What is the probability that Whale will win?