60
$\begingroup$

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.

$\endgroup$
7
  • 5
    $\begingroup$ Have you considered the case where $n = \infty$? Might be easier to start there. $\endgroup$ Sep 17, 2012 at 17:23
  • 3
    $\begingroup$ Section 2 of arxiv.org/abs/0901.4056, gives an exponential upper bound on the probability of winning in the intermediate (e.g. if $b=k/2$) regime. Non-adaptive strategies will give an exponential lower bound, but with a better exponent. $\endgroup$ Sep 17, 2012 at 18:47
  • $\begingroup$ I'm curious about the World Series example where both teams are equal (n=7, k=4, b=3.5). My instinct tells me that there is a 50% chance of winning no matter how I budget things (provided only that I don't waste any of the budget). Right? $\endgroup$
    – bobuhito
    Sep 26, 2012 at 17:45
  • 1
    $\begingroup$ @bobuhito Your instinct isn't correct. For example, for n=3, k=2, b =1.5, the optimal strategy gives you a 5/8 chance of winning (see my answer below). The game isn't symmetric because only one side is able to bias the outcome. $\endgroup$
    – Granger
    Sep 26, 2012 at 18:49
  • 2
    $\begingroup$ @bobuhito For n=7, k=4 and b=3.5, using the recursion in my answer and maximising over p=i*min(1,b)/1000, for i=0..1000 at each stage, the (approximately) optimal strategy entails setting p_1 = 0.619, not 1/2. If the result is H, then set p_2=0.881, otherwise set p2=0.509, and so on. Using this numerical approach S_{7,4}(3.5) \approx 0.72826. In general I don't think any heuristics will help, since one needs to maximise all the intermediate functions prior to the first decision. In this respect the p_i's are not dynamically chosen; the entire game tree must precomputed from leaves to the root. $\endgroup$
    – Granger
    Sep 27, 2012 at 14:22

4 Answers 4

11
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for the response. Your strategy is one that one of my colleagues also came up with. Maybe I should have mentioned this earlier, but anyway, like you, we were not able to prove rigorously that it was optimal. $\endgroup$ Sep 18, 2012 at 15:35
  • $\begingroup$ To prove that this is optimal for $n=\infty$ it suffices to show that for every $x$, there is no choice of an amount to spend which gives you a higher average value of $f$ on the next time. $\endgroup$ Sep 26, 2012 at 15:05
8
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.