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.
-
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.
-
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.
-
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.
Best Answer
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.