Return to Answer

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).

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.

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. 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)$.

Assume $S_{n',k'}(b)$ is known for all $n' < n$ and $k' \le k$. Then by this 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).

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).

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. 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)$.

Assume $S_{n',k'}(b)$ is known for all $n' < n$ and $k' \le k$. Then by this 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).

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. 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)$.

Assume $S_{n',k'}(b)$ is known for all $n' < n$ and $k' \le k$. Then by this 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).