Flipping coins on a budget

Question

A coin is flipped $n$ times and you win if it comes up heads at least $k$ times. The coin is unusual in that you're allowed to pick the probability $p_i$ that it comes up heads on the $i$th flip, subject only to the constraint that $\sum_i p_i \le b$, where $b$ is some predetermined "budget" that you have. Moreover, you are allowed to wait until you've seen the results of the first $i-1$ flips before choosing the value of $p_i$. Given $n$, $k$, and $b$, what is your optimal strategy, and what is your probability of winning?

One colorful way to state the problem is that if you're a sports team tasked with winning a best-of-$n$ series and you have limited resources (e.g., a limited bullpen for the World Series of major league baseball), how should you budget them?

---

Naturally, if $b\ge k$, you can simply pick $p_i=1$ for $k$ of the $n$ flips, and win with probability 1. So the question is interesting only if $b\lt k$.

I've circulated this problem informally among colleagues, who have obtained miscellaneous partial results but not a full solution. It would take too much space to summarize all the partial results, but let me mention some of the highlights.

1. Even the "non-adaptive case," where you're not allowed to see the results of your flips before choosing $p_i$, is not trivial. The best strategy is to divide the budget evenly over $r$ flips for some $r$, but the exact value of $r$ is more complicated than you might think. For a given $r$, the probability of $k$ successes is $$\sum_{m=k}^r {r \choose m} \left({b\over r}\right)^m\left(1-{b\over r}\right)^{r-m}.$$ From this it appears that if $b\lt k-1$ then we should choose $r=n$, and if $k-1 \le b \lt k$ then $r\approx (k-1)/3(b-k+1)$, but we have a proof only in special cases.

2. In the actual stated problem, let's let $d=k-b$, the deficit. Then, at least in the small-deficit case, the best general strategy we have so far is to make an initial coin flip with probability $1-\lbrace d\rbrace$ (where $\lbrace d\rbrace$ denotes the fractional part of $d$), and then take $p_i=1/2$ until we find ourselves in a situation where we can "clinch" the win by taking the remaining $p_i=1$. (It's possible to analyze this strategy quantitatively but I'll omit the details here.) In particular, one can show that adaptive strategies significantly outperform non-adaptive strategies.

3. If $b$ is small then one can show that the best non-adaptive strategy is within a constant factor of optimum. For example if $b\le 1$, then one can show that the overall winning probability $p$ satisfies $${1\over 4}{n\choose k}\left({b\over n}\right)^k \le p \le {n\choose k}\left({b\over n}\right)^k.$$ The upper bound is actually true for all $b$ and the lower bound can be derived from the best non-adaptive strategy.

Answer 1

I want to propose a strategy in the limiting case $n=\infty$. Maybe this is better described as a limit of strategies, since I will allow a sequence of coin flips that are each assigned probability $\epsilon$ of success (where $\epsilon$ is infinitessimal). The total amount of probability we will "spend" before the next head appears will then be exponentially distributed, with mean 1.

I will denote by $f_k(x)$ the probability that my strategy results in success if we still need $k$ heads, and have $x$ probability remaining in our "budget." Here is how the strategy works: If $x\geq k$, we assign probability 1 to the next $k$ flips. This results in $f_k(x)=1$.

If $x\in (k-1,k)$, then we assign the next flip probability $x-(k-1)$. If this flip lands heads, we will win with probabilty 1. If the flip lands tails, we will win with probabilty $f_k(k-1)$. It follows that $$ f_k(x)=(x-(k-1))+(k-x)f_k(k-1) $$

Finally, if $x\leq k-1$, then we will assign probability $\epsilon$ to each subsequent flip, until we see a heads. This gives $$ f_k(x)=\int_0^x e^{-t}f_{k-1}(x-t)\,dt $$

We can recursively compute $f_k(x)$ for any $k$. Each $f_k$ is a continuous, piecewise-analytic function. The first few values (computed with the help of Mathematica; I hope they're correct) are: $$ f_1(x)=\begin{cases} x&\text{ if }0\leq x\leq 1\newline 1&\text{ if }x>1 \end{cases} $$

$$ f_2(x)=\begin{cases} -1+x+e^{-x}&\text{ if }0\leq x\leq1\newline -1+\frac{2}{e}+(1-\frac{1}{e})t&\text{ if }1\leq x\leq 2\newline 1&\text{ if }x>2 \end{cases} $$

$$ f_3(x)=\begin{cases} -2+x+(x+2)e^{-x}&\text{ if }0\leq x\leq 1\newline e^{-x}+\frac{3}{e}-2-\frac{x}{e}+x&\text{ if }1\leq x\leq 2\newline -2+x+\frac{(1+e)(3-x)}{e^2}&\text{ if }2\leq x\leq 3\newline 1&\text{ if }x\geq 3 \end{cases} $$

While I don't have a proof this strategy is optimal, I've got a heuristic argument that assigning probability $\epsilon$ to each flip is a good idea. If our budget is $x$, then whatever our strategy, the expected number of heads we will have seen when we exhaust our budget is $x$. If the desired number of heads is much larger than $x$, we will need to make the variance in the number of heads large. If we assign probabilities $p_1,p_2,\ldots$ to the coin flips (with $p_1+p_2+\ldots=x$), then the variance in the number of heads is $\sum p_i(1-p_i)$, which is bounded above by $x$. We can make the variance arbitrarily close to $x$ by taking each $p_i$ as small as possible.

The argument is a little different if the next head that appears could cause our remaining budget to be larger than the number of additional heads we need to win.

Answer 2

This problem is ripe for a recursive approach. The method below allows one to compute the maximum probability of winning over all strategies for any $n,k$ recursively, as a function of $b$. These solutions are thus all optimal.

However, the maximum winning-probability function varies over the interval $0 \le b < k$, and given the example computations below, it seems that a general formula may not be so easy to find.

Let $S_{n,k}(b)$ be the maximum probability of winning the game for the given inputs. Assume $S_{n',k'}(b)$ is known for all $n' < n$ and $k' \le k$. Since at any stage there is only one choice to be made - namely how much of the budget $b$ to assign to $p$, the probability of obtaining a head - all possible strategies are parameterised by $0 \le p \le \text{min}(1,b)$. Hence by the inductive assumption we have the following recurrence relation:

$$ S_{n,k}(b) = \text{max}_{0 \le p \le \text{min}(1,b)} \ \{p \cdot S\_{n-1,k-1}(b-p) + (1-p) \cdot S\_{n-1,k}(b-p) \}, $$

since a head (occurring with probability $p$) decrements both $n$ and $k$, while a tail decrements $n$ only.

We define $S_{n,k}(b) = 0$ if $n < k$ and $S_{n,0}(b) = 1$ for $n \ge 1$ and any $b$. Using the recurrence and these base cases it is easy to obtain $S_{n,1}(b) = \text{min}(1,b)$ for $n \ge 1$. It is also easy to show that $S_{2,2}(b) = \text{min}(1,b^2/4)$, setting $p=b/2$ for each toss.

The first non-trivial case is $$ S_{3,2}(b) = \begin{cases} \frac{b^2}{3} - \frac{b^3}{27} & \text{if} \ 0 \le b \le 3/2 & (\text{set} \ p = b/3)\\ \newline \frac{3b-2}{4} & \text{if} \ 3/2 \le b \le 2 & (\text{set} \ p = b-1)\\ \newline 1 & \text{if} \ b \ge 2, \end{cases} $$ which is obtained by substitution and differentiating w.r.t. $p$.

$S_{3,3}(b) = \text{min}(1,b^3/27)$, by setting $p = b/3$, while the next interesting case is $$ S_{4,2}(b) = \begin{cases} \frac{b^4}{256} - \frac{b^3}{16} + \frac{3b^2}{8}& \text{if} \ 0 \le b \le 4/3 & (\text{set} \ p = b/4)\\ \newline \frac{19b-11}{27} & \text{if} \ 4/3 \le b \le 2 & (\text{set} \ p = b-1)\\ \newline 1 & \text{if} \ b \ge 2. \end{cases} $$

It should be possible to prove a (recursive) formula for $S_{n,2}(b)$ based on the above. However, for $k=3$, $n \ge 4$ this may be somewhat harder. In particular for $0 \le b \le 2$ we have $S_{4,3}(b) = b^3/16 - b^4/128$, setting $p = b/4$.

For $2 \le b \le \alpha \approx 2.84$ we have $S_{4,3}(b) = r(b) \cdot \frac{3(b-r(b))-2}{4} + (1-r(b))\cdot\frac{(b-r(b))^3}{27}$, where $r(b)$ is the root in $[0,1]$ satisfying $$ 16r^3 - (36b+12)r^2 +(24b^2 +24b - 162)r -4b^3 -12b^2 + 81b -54 = 0, $$ and $p = r(b)$. For $\alpha \le b \le 3$, setting $p = b-2$ is optimal and gives $S_{4,3}(b) = 19b/27 - 10/9$.

It would seem that for larger $k$ (and $n$) these computations become increasingly cumbersome (or interesting, depending on one's perspective).

---

EDIT: In contrast to the difficulty of finding an analytic solution, one can alternatively solve for $S_{n,k}(b)$ numerically, by subdividing the relevant $p$-intervals to any desired precision and maximising over $p$.

For example, dividing the intervals by $1000$, we find that for the world series example with $n=7$, $k=4$ and assuming a budget of $3.5$, we have $S_{7,4}(3.5) \approx 0.72826$, obtained by setting $p_1 \approx 0.619$ etc. and following the precomputed decision tree. Since the entire decision tree has to be optimised from the leaves to the root prior to the first decision being made, the $p_i$'s are not really chosen dynamically/reactively at all.

Answer 3

A version of the non-adaptive problem was studied by Uriel Feige, using slightly different language. In his paper, "On Sums of Independent Random Variables with Unbounded Variance, and Estimating the Average Degree in a Graph", he proves the following theorem.

Let $X_1,\ldots,X_n$ be non-negative independent random variables with expectations $\mu_1,\ldots,\mu_n$, respectively, with all $\mu_i \le 1$. Let $X=\sum_{i=1}^n X_i$ and $\mu=\sum_{i=1}^n \mu_i=\mathbb{E}X$. Then for all $\delta > 0$,

$$ \mathbb{P}[ X < \mu + \delta] \ge \min(\delta/(1+\delta),1/13). $$

The value $1/13$ was later improved to $1/8$ by He, Zhang and Zhang. Feige conjectures that in the setting of the above theorem, for every $n$, for all $\delta > 0$ one of the following two examples minimizes $\mathbb{P}[ X < \mu + \delta]$.

1. For each $1 \le i \le n$, $X_i=n+\delta$ with probability $1/(n+\delta)$ and otherwise equals $0$.
2. $X_1=1+\delta$ with probability $1/(1+\delta)$ and otherwise $X_1=0$. For all $1 < i \le n$, $\mathbb{P}[X_i=1]=1$.

If Feige's conjecture is correct, the term $1/13$ may in fact be replaced by $1/e$. The first step in Feige's argument is to show that the general question may be reduced to the case of random variables whose support contains at most one non-zero value; this makes the problem look rather similar to the one given above.

Answer 4

I give here a solution at the limite $b$, $n$, $k$ very large: The optimal strategy is to alway play $\frac{b}{n}$ until you have more budget left than the number of head to get. It will give a probability of win equal to $$2 \mathcal{N}([\frac{k-b}{\sqrt{b(1-\frac{b}{n})}},\infty])$$ With $\mathcal{N}$ the gaussian measure.

We note $S(i)$ the number of heads up to time $i$ and $b(i)=b-\sum_{j<i}p(j)$ the budget you still have after $i$ flip. We define $X$ as $$X(i)=k-S(i)-b(i) $$ The central observation is the following : whatever the strategy you chose $X$ is a Martingale. Therefore for $n,b,k $ large and with a correct scaling it will converge to a continuous stochastic process. We note $t=\frac{i}{n}$ and on $[0,1]$, and we change the notation such that $p(t)=p(i)$, $b(t)=\frac{b(i)}{n}$, $X(t)=\frac{1}{\sqrt{n}}X(i)$. At the limite the system evolves as follow:
$$\begin{cases}dX_t = \sigma(p(t))dB_t \\ db_t=-p(t)dt \end{cases}$$ where $\sigma(p(t))=\sqrt{p(t)(1-p(t))}$. The process $p(t)$ is our strategy and it should be think as $p(t,b_t,X_t)$ where $0\leq p(t)\leq 1$. With initial condition $X_0 = \frac{1}{\sqrt{n}}(k-b)$ and final condition $b(t=1)=0$.

As soon as $X_t=0$, we are in the situation $b\geq k$ one can set $p(s)=1$ and then $p(s)=0$ to finish. Therefore one have to obtimize $$ \mathbb{P}(\exists t : X_t\leq 0)$$ We have an explicit solution for $X$: $$X_t=X_0+B_{\int_0^t \sigma(p(s))^2 ds} $$ And then $$ \mathbb{P}(\exists t \in [0,1]: X_t\leq 0)= \mathbb{P}(\exists u \in [0,\int_0^1 \sigma(p(s))^2 ds]: B_u\leq -X_0)$$ We recall that $\int_0^1 \sigma(p(s))^2 ds$ is not a constant but a random variable depending on the chosen strategy. However here we remark the probability is monotone in $\int_0^1 \sigma(p(s))^2 ds$ and we can conclude : we should always chose $p$ such that $$\int_0^1 \sigma(p(s))^2 ds = \max_{p'} \int_0^1 \sigma(p'(s))^2 ds=\int_0^1 \frac{b}{n}(1-\frac{b}{n})ds= \frac{b}{n}(1-\frac{b}{n})$$ The last equalities follow from the fact that $x\rightarrow \sigma(x)^2$ is concave. And we have $$\max_{p'} \mathbb{P}(\exists t : X_t\leq 0)= \mathbb{P}(\min_{u\in [0,\frac{b}{n}(1-\frac{b}{n})]} B_u\leq -X_0)=2 \mathcal{N}(y \leq \frac{k-b}{\sqrt{b(1-\frac{b}{n})}})$$ With $\mathcal{N}$ the gaussian measure. (the last equality is a well known property of the maximum of the Brownian motion)