4
$\begingroup$

Imagine you have $n$ coins. Coin $i$ has a probability $p_i$ to get heads. You can choose these probabilities so long as $\sum_{i=1}^n p_i = \alpha$ for some constant $\alpha \leq n$. Now that you've chosen the probabilities, you must play a game. Flip coin 1; if it comes up tails, you must restart the game. However, if it comes up heads, flip coin 2; if it comes up tails, you must restart the game. To win the game you must flip $n$ heads in a row. You want to assign the probabilities $p_i$ such that the expected number of coin flips is minimized.

Note that if the question were to assign $p_i$ such that the probability of winning is maximized, a standard result is to choose $p_i = \frac{\alpha}{n}$ for all $i$.

Formally, this problem can be stated as:

$$\min_{p_i} E_n \text{ where } E_n = \left(n \prod_{i=1}^n p_i + \sum_{i=1}^n (E_n + i) \ p_1 p_2 \ldots p_{i-1} (1 - p_i)\right)$$

With the following constraints:

$$\sum_{i=1}^n p_i = \alpha \text{ and } p_i \in [0, 1]$$

In the case of $n=2$ this is easy, we have $p_2 = \alpha - p_1$ and:

$$E_2 = 2 p_1 (\alpha - p_1) + (E_2 + 1)(1 - p_1) + (E_2 + 2)p_1(1 - \alpha + p_1)$$

Solving for $E_2$ and setting $\frac{\partial E_2}{\partial p_1} = 0$, we eventually find:

$$p_1 = \sqrt{1 + \alpha} - 1$$

For $\alpha = 1$, this gives $p_1 \approx 0.414$. This agrees with intuition - instead of doling out the probabilities equally, you should favor lower probabilities for low indices $i$ and higher probabilities for high indices $i$. When $\alpha \geq 2$, we would expect the formula to return $p_1 \geq 1$, since $p_1 = p_2 = 1$ is optimal, but for some reason it does not do this.

However, it already becomes very difficult when $n=3$. Is there a general way to attack this problem?

I'm able to derive the following:

$$E_n = \frac{1 + p_1 + p_1 p_2 + \ldots + p_1 p_2 \cdots p_{n-1}}{p_1 p_2 \cdots p_n}$$

Using the method of Lagrange multipliters, I can get the following $n+1$ nonlinear equations in $n+1$ variables:

$$\frac{\partial E_n}{\partial p_i} = -\frac{1 + p_1 + p_1 p_2 + \ldots + p_1 p_2 \cdots p_{i-1}}{p_1 p_2 \cdots p_{i-1} p_i^2 p_{i+1} \cdots p_n} + \lambda = 0$$

$$\frac{\partial E_n}{\partial \lambda} = p_1 + p_2 + \ldots + p_n - \alpha = 0$$

But I don't see how to solve this set of nonlinear equations.

$\endgroup$
9
  • 1
    $\begingroup$ In your $n=2$ some strange things also happen if $\alpha \le \frac12$ $\endgroup$ Commented Jan 23, 2023 at 21:55
  • $\begingroup$ How do you get that re-statement? Just considering the possible outcomes of the first round we get $E=n\times \prod p_i +\sum_{i=1}^{n-1} \left((i+E)\times p_1p_2\cdots (1-p_i)\right)$ but that's not obviously equivalent to what you wrote. $\endgroup$ Commented Jan 23, 2023 at 22:02
  • $\begingroup$ Maybe I'm missing a step, but the minimization I'm getting is a little different: I have the number of tries $f$ with $f=q_1(1+f)+q_2(2+f)+...+q_{n-1}(n-1+f)+n \prod p_i$ where $q_i$ is the chance of failing after $i$ throws. Solving for $f$ there seems to give you something more complex? $\endgroup$ Commented Jan 23, 2023 at 22:02
  • $\begingroup$ I think you are using the wrong formula to compute the expected value of coin flips. For instance, in the sum you are not including the cases in which the number of coin flips is greater that $n$. Also, the expected value of coin flips shouldn’t be less than $n$, whlie in the formula you are allowing for values between $1$ and $n$. Maybe I am misreading and that is not the expected value of coin flips, but then I suspect the minization problem is still not equivalent to the one you wrote in words $\endgroup$ Commented Jan 23, 2023 at 22:04
  • $\begingroup$ Well, by the way, to minimize that quantity you wrote in the formula, you simply need to choose $p_1=0$ (at least in the cases you are able to do so, i.e., when $\alpha\leq n-1$)… I guess this is strong evidence that the formula you wrote is doing something different than what you want to do $\endgroup$ Commented Jan 23, 2023 at 22:12

2 Answers 2

Reset to default
2
$\begingroup$

For the $n=2$ case, I would have said $$E=(1+E)(1-p_1)+(2+E)p_1(1-p_2)+2p_1p_2$$ implying $$E=\frac{1+p_1}{p_1p_2}$$ as the expected number of throws until you get two consecutive heads.

If you also know $p_1+p_2=\alpha$ then you want to minimise $\frac{1+p_1}{p_1(\alpha -p_1)}$. This will certainly need $0 \le p_1 \le p_2\le 1$ and so happens when $p_1=\sqrt{\alpha+1}-1$ as your corrected calculations show.

However, if $\alpha \gt \phi$ the golden ratio $\frac{1+\sqrt{5}}2\approx 1.618$, then this is no longer satisfactory as it would suggest optimal $p_2 >1$ so not a probability. In that case the optimal probabilities are $p_2=1$ and $p_1=\alpha-1$. This resolves your concern about what happens when $\alpha =n=2$.

$\endgroup$
2
  • $\begingroup$ This makes me think the full optimization problem is too hard, as it requires considering the constraint $p_i \in [0, 1]$ too carefully. It may be easier to consider the problem where $\alpha = \frac{n}{2}$, in which case it seems unlikely that any $p_i > 1$ using the optimization procedure. I am able to obtain numerical results using a standard optimizer, and I imagine the answers are the roots of some polynomial (as in the $n=2$ case), but I don't see what polynomial. $\endgroup$ Commented Jan 24, 2023 at 3:41
  • $\begingroup$ I agree with $E$ being the fraction you wrote. The rest looks right as well $\endgroup$ Commented Jan 24, 2023 at 15:55
2
$\begingroup$

Edit. Corrected massive typos. Now everything is working and looks consistent with other answers and comments.

Here I am not answering the original question, but this question needs a clarification.

First, the quantity you wrote is not the correct one to minimize to find the optimal values of $p_1,\dots, p_n$. You can simply choose $p_1=0$ (as long as $\alpha\leq n-1$) to make that quantity achieve the minimum. That quantity is simply the average number of coin flips needed to either win the game or to score tails once.

The quantity you want to minimize is then slightly different.(the original post has been corrected).

The expected value of coin flips in your problem is given by $$ E_n=al+n, $$ where the number $a$ is the average number of coin flips before losing the game once assuming you are going to lose, $$ a=\frac{\sum_{i=1}^{n}ip_1\cdots p_{i-1}(1-p_i)}{\sum_{i=1}^{n}p_1\cdots p_{i-1}(1-p_i)}, $$ and the number $l$ is the average number of tails (losses) before winning the game (computed using the formula of the mean value of a geometric distribution) $$ l=\frac{1}{p_1\cdots p_n}-1. $$ (the $-1$ comes from the fact that I am counting the very last $n$ coin flips separately). It is then possible to simplify the quantity to the expression $$ E_n=\frac{\sum_{i=1}^{n}ip_1\cdots p_{i-1}(1-p_i)}{p_1\cdots p_n}+n= \frac{\left(\sum_{i=1}^{n-1}ip_1\cdots p_{i-1}(1-p_i)\right) +np_1\cdots p_{n-1}}{p_1\cdots p_n} $$ which further simplifies to $$ E_n=\frac{1+p_1+p_1p_2+\dots + p_1\cdots p_{n-1}}{p_1\cdots p_n}. $$ An easy recursive formula, which could be helpful in finding a way of computing the minimum expected value, is then given by $$ E_n=\frac{E_{n-1}+1}{p_n}. $$

I have checked carefully that all the steps work and the formula is consistent with the formula of @Henry in one of the comments (thanks!). How to find the optimal values of $p_1,...,p_n$ I don’t see at the moment.

$\endgroup$
5
  • $\begingroup$ Your expression for $E_n$ isn't equivalent to mine, I don't think. Consider $n=2$ and $p_1 + p_2 = 1$, then if I'm not mistaken you get $E_2 = \frac{1}{p_1} + 2$, but this possibly doesn't account for the fact that when you get heads and then tails, you have to add 2 to your running total of flips. $\endgroup$ Commented Jan 24, 2023 at 2:00
  • $\begingroup$ My calculations suggest $E_n=\dfrac{1+p_1(1+p_2(1+p_3(1+\cdots (1+p_{n-1}(1+p_n))\cdots)))}{p_1p_2p_3\cdots p_{n-1}p_n}$ which I think may be equivalent to what you have written $\endgroup$ Commented Jan 24, 2023 at 2:36
  • $\begingroup$ Okay, I agree with that expression for $E_n$. Using Lagrange multipliers it is possible to derive a set of nonlinear equations that minimize $E_n$. Solving these in closed form does not seem so easy for $n > 2$. Numerically it looks like $p_1$ and $p_n$ converge (but to what?) as $n \to \infty$ but it's hard to even get numerical results for $n > 10$. $\endgroup$ Commented Jan 24, 2023 at 4:28
  • $\begingroup$ It's not that simple to do, but it looks straightforward. You could try to reproduce the argument of Henry in his question, which will work at least when $\alpha$ is small enough. For instance, for $n=3$, you first write $p_3=\alpha-p_1-p_2$ in the expression for $E_3$; then you fix $p_2$ and minimize $E_n$ with respect to $p_1$; then you minimize what you get with respect to $p_2$... $\endgroup$ Commented Jan 24, 2023 at 16:25
  • $\begingroup$ @Henry yes, after some corrections, I see that what you wrote agrees with what I wrote. Thank you! $\endgroup$ Commented Jan 24, 2023 at 16:26

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.