Tag: dynamic programming

Suppose there are $N$ total questions, and the Sphinx never gives the same answer $Q$ times in a row.

Define $F^{Q}_{n}$ to be the $n^\text{th}$ $Q$-generalized Fibonacci number. Specifically:
\begin{align}
F^Q_{n} &= 0 & \text{for }n \leq 0 \\
F^Q_1 &= 1 \\
F^Q_n &= F^Q_{n-1} + F^Q_{n-2} + \cdots + F^Q_{n-Q} & \text{for }n \geq 2
\end{align}These are also called Fibonacci $Q$-step numbers. Here are some examples (borrowed from here)

The maximum amount of money we can expect to have after $N$ questions assuming optimal play is given by the formula:

$\displaystyle
\text{Maximum guaranteed winnings} = \frac{2^{N-1}}{F^{Q-1}_{N+1}}
$

Here is the optimal strategy that achieves this gain:

• At the first question, answer anything (doesn’t matter) and wager zero.
• Keep track of the streak length $q$, which is how many times in a row the Sphinx has answered the same way, and the number of questions remaining, which we’ll call $n$.
• At every subsequent question, answer the opposite to the correct answer of the most recent question. This ensures that if the Sphinx wants to make you lose again, she will have to lengthen her streak. You should also wager the following fraction of the total money you currently have:
  \[
  \begin{cases}
  0 & \text{if }n+q \lt Q \\
  \frac{2F^{Q-1}_{n+1}}{F^{Q-1}_{n+1} + F^{Q-1}_{n} + \cdots + F^{Q-1}_{n-(Q-q)+2}}-1 & \text{if }n+q \geq Q
  \end{cases}
  \]

Note that as $q$ increases (the Sphinx is getting closer to being forced to answer predictably), the wagers get larger. When $q=Q-1$, the wager fraction simplifies to $1$, i.e. we should wager everything because we know we will win. When $n+q \lt Q$, there aren’t enough questions remaining to force the Sphinx to answer predictably, so we can expect to always lose and we should wager nothing.

Here is a plot showing the maximum guaranteed winnings as a function of $N$ and $Q$ if we start with \$1, which is given by the formula $\frac{2^{N-1}}{F^{Q-1}_{N+1}}$.

When $Q=2$, the Sphinx must alternate answers, so we can double our money every turn! This explains why the plot grows by a factor of 2 when $Q=2$ (the vertical axis is on a logarithmic scale). The plot is also flat for $N \leq Q-1$. This corresponds to the case where we have insufficient questions to force the Sphinx to answer predictably, so our best bet is to wager nothing and cut our losses.

In the detailed write-up, I explain how all of these formulas were derived, and I also go into detail on the asymptotic growth rate we can expect for different $Q$.

We will solve the most general version of the problem, with $N$ questions and no $Q$ answers in a row are ever the same. This is a sequential decision-making problem, where at each turn of the game, we make a move (pick an answer and pick a wager), and then the Sphinx makes a move (picking the correct answer). We are looking to maximize our guaranteed winnings, which means we should assume the Sphinx is doing her best to minimize our winnings, while we are doing our best to maximize our winnings.

We will approach this problem using recursion, by expressing any given state of the game in terms of simpler states of the game. To do this, we must think about what constitutes a state of the game; what is the complete set of information that should be used to determine our next actions? Based on the rules of the game, the key pieces of information are:

• How many questions there are left, which we’ll call $n$. Initially, $n=N$.
• The current answer streak length, which we’ll call $q$. For example, if the Sphinx’s last few responses were (…, False, True, False, False), then $q=2$, since there are two Falses in a row at the end. Initially, $q=0$.
• The limit on streak length, $Q$, which is given in the problem. This means the Sphinx never answers the same way $Q$ times in a row. We will assume $Q\geq 2$ in this problem.

Importantly, the current amount of money we have is irrelevant, because we will always wager some proportion of our current holdings. Likewise, the amount we win in the end will also be proportional to our current holdings. For example, any strategy that guarantees we will have \$1.50 at the end if we currently have \$1 can be used to guarantee us \$3 if we currently have \$2, or \$15 if we currently have \$10.

With this knowledge in mind, define $V_{q,n}^Q$ to be the amount we will have at the end if we start with \$1 and both players (us and the Sphinx) play perfectly, the current streak is at $q$ with a limit of $Q$, and we have $n$ turns remaining. Ultimately, our goal is to find $V_{0,N}^Q$, but we’ll find all possible values in the process of solving the problem. We’ll use a dynamic programming approach, starting from simple cases (small $n$) and working our way back to the general $n=N$ case. The function $V$ we defined is typically called the value function.

Base cases

Let’s call $u$ the amount we wager, with $0\leq u \leq 1$. We can consider several base (or special) cases, for which the answer is immediately apparent. Here they are:

Case $n=0$. If there are no questions left to answer, the game is over and we take home the money we currently have. So we can write:
\[
V_{q,0}^Q = 1
\qquad\text{for all }q,Q.
\]

Case $n + q \lt Q$. If there aren’t enough questions remaining for the Sphinx to reset their streak quota, then the Sphinx can make us lose our remaining turns and they suffer no consequences. If we ever find ourselves in this situation, we should cut our losses and wager $u=0$. Therefore,
\[
V_{q,n}^Q = 1\qquad\text{if }q+n\lt Q\quad\text{with wager }u=0
\]

Case $q=Q-1$. This is the situation where the Sphinx’s hand is forced. They have already answered the same way $Q-1$ turns in a row, so they are forced to answer differently on their next turn, so we can bet everything we’ve got and we’re assured to win and double our money! Therefore, we should answer whatever the opposite to the current streak (i.e., if the correct answer was True $Q-1$ times in a row, we should answer the next question False) and we will win:
\[
V_{Q-1,n}^Q = 2 V_{1,n-1}^Q\qquad\text{and we should wager }u=1.
\]

Case $q=0$. This case is also interesting because it only happens at the start of the game. Once the game in underway, we have $q \geq 1$. So let’s see what happens on that first move. After our move, $n$ is reduced by one, and we either have $1+u$ or $1-u$, depending on whether we answered correctly or incorrectly.
\[
V_{0,n}^Q = \begin{cases}
(1+u)V_{1,n-1}^Q & \text{if we are correct} \\
(1-u)V_{1,n-1}^Q & \text{if we are incorrect}
\end{cases}
\]Keep in mind the Sphinx is out to ruin us, so for all intents and purposes, the Sphinx decides whether we are correct or not. No matter what happens, the Sphinx will accrue a streak of 1 so $q=1$. There is no trade-off here; the Sphinx can make us lose and it doesn’t cost her anything! We will lose any amount we bet, so the only safe move in this case is to bet nothing, and essentially skip our first turn. So we have:
\[
V_{0,n}^Q = V_{1,n-1}^Q
\qquad\text{and we should wager }u=0.
\]

General case

In the general case, with a current streak of $1 \leq q \leq Q-2$ and $n$ questions left to answer, we can answer the same as the current streak, or answer differently. We can also be right or wrong. So there are four possibilities. The possibilities are:
\[
V_{q,n}^Q = \begin{cases}
\text{Answer same:} & \begin{cases}
(1+u)V^Q_{q+1,n-1} & \text{if correct} \\
(1-u)V^Q_{1,n-1} & \text{if incorrect}
\end{cases}\\
\text{Answer different:} & \begin{cases}
(1+u)V^Q_{1,n-1} & \text{if correct} \\
(1-u)V^Q_{q+1,n-1} & \text{if incorrect}
\end{cases}
\end{cases}
\]The Sphinx will always pick the option that causes us to lose as much as possible, so we can simplify this to:
\[
V_{q,n}^Q = \begin{cases}
\min\left\{ (1+u)V^Q_{q+1,n-1}, (1-u)V^Q_{1,n-1} \right\}
& \text{if we answer same}\\
\min\left\{ (1+u)V^Q_{1,n-1}, (1-u)V^Q_{q+1,n-1} \right\}
& \text{if we answer different}
\end{cases}
\]We can simplify further, by noting that $V^Q_{q,n}$ is an increasing function of $q$. In other words, the longer the current streak, the more we can expect to win, because we are closer to forcing an answer out of the Sphinx. These properties imply that $(1+u)V^Q_{q+1,n-1} \geq (1-u)V^Q_{1,n-1}$. So if we “answer same”, the Sphinx will always have us lose. Naturally, if we give the Sphinx an opportunity to take some of our money and reset its streak counter, of course she will take it! This drives us to the striking conclusion:

Always answer the opposite of the previous correct answer.

This simplifies things greatly, but we still don’t know how much to wager. We should wager an amount $u$ that maximizes our winnings assuming the Sphinx plays perfectly. Therefore:
\[
V_{q,n}^Q = \max_{0 \leq u \leq 1}
\min\left\{ (1+u)V^Q_{1,n-1}, (1-u)V^Q_{q+1,n-1} \right\}
\]In other words, we are presenting the Sphinx with a trade-off: she can choose to have us lose our wager, but this will bring her closer to filling her streak quota and forcing her hand. Or, she can reset her streak quota, but at the cost of having us win our wager.

Solving the recursion

Putting everything together, here are the dynamic programming recursions for our value function.
\begin{align}
V_{0,n}^Q &= V_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=0\\
V_{q,0}^Q &= 1\qquad \text{for all }q\\
V_{q,n}^Q &= 1\qquad\text{if }q+n\lt Q\quad\text{with wager }u=0 \\
V_{Q-1,n}^Q &= 2V_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=1 \\
V_{q,n}^Q &= \max_{0 \leq u \leq 1}
\min\left\{ (1+u)V^Q_{1,n-1}, (1-u)V^Q_{q+1,n-1} \right\},\\
&\quad \text{for }\quad 1\leq q \leq Q-2\text{ and }n\geq \max\{Q-q,1\}
\end{align}

The min/max optimization is now straightforward to solve. All functions involved are linear in $u$, so the optimum will occur either at a boundary ($u=0$ or $u=1$), or it will occur at the intersection of both functions. We already took care of all boundary cases, so we are now dealing with the latter case. Therefore, the optimal wager satisfies $(1+u)V^Q_{1,n-1}=(1-u)V^Q_{q+1,n-1}$, which leads to:
\[
u_\text{opt} = \frac{V^Q_{q+1,n-1}-V^Q_{1,n-1}}{V^Q_{q+1,n-1}+V^Q_{1,n-1}}
\quad\text{and}\quad
V^Q_{q,n} = \frac{2V^Q_{q+1,n-1}V^Q_{1,n-1}}{V^Q_{q+1,n-1}+V^Q_{1,n-1}}
\]Our simplified recursion is therefore:
\begin{align}
V_{0,n}^Q &= V_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=0\\
V_{q,0}^Q &= 1\qquad \text{for all }q\\
V_{q,n}^Q &= 1\qquad\text{if }q+n\lt Q\quad\text{with wager }u=0 \\
V_{Q-1,n}^Q &= 2V_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=1 \\
V_{q,n}^Q &= \frac{2V^Q_{q+1,n-1}V^Q_{1,n-1}}{V^Q_{q+1,n-1}+V^Q_{1,n-1}}
\quad\text{with wager }u = \frac{V^Q_{q+1,n-1}-V^Q_{1,n-1}}{V^Q_{q+1,n-1}+V^Q_{1,n-1}}\\
&\qquad\text{for }\quad 1\leq q \leq Q-2\text{ and }n\geq \max\{Q-q,1\}
\end{align}This still looks complicated, but we can make one last simplification. Notice that our only messy expression is the general recursion, which looks like $v = \frac{2ab}{a+b}$. We can rewrite this as: $\frac{1}{v} = \frac{1}{2}\left( \frac{1}{a} + \frac{1}{b} \right)$, which looks much nicer. To this effect, let’s make this change of variables:
\[
W^Q_{q,n} := \frac{2^n}{V^Q_{q,n}} \qquad\text{for all }Q,q,n.
\]With this change of variables, the recursion becomes linear!
\begin{align}
W_{0,n}^Q &= 2 W_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=0\\
W_{q,0}^Q &= 1\qquad \text{for all }q\\
W_{q,n}^Q &= 2^n\qquad\text{if }q+n\lt Q\quad\text{with wager }u=0 \\
W_{Q-1,n}^Q &= W_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=1 \\
W_{q,n}^Q &= W^Q_{1,n-1} + W^Q_{q+1,n-1}
\quad\text{with wager }u = \frac{W^Q_{1,n-1}-W^Q_{q+1,n-1}}{W^Q_{1,n-1}+W^Q_{q+1,n-1}}\\
&\qquad\text{for }\quad 1\leq q \leq Q-2\text{ and }n\geq \max\{Q-q,1\}
\end{align}

Let’s start with the case $q=1$, so we’ll solve for $W^Q_{1,n}$. Applying the last three recursions, we get:
\begin{align}
W^Q_{1,n} &= 2^n \qquad\text{for }0 \leq n \leq Q-2 \\
W^Q_{1,n} &= W^Q_{1,n-1} + W^Q_{1,n-2} + \cdots + W^Q_{1,n-(Q-1)}\qquad\text{for }n \geq Q-1
\end{align}This further simplifies to the compact form:
\begin{align}
W^Q_{1,-k} &= 0 \qquad \text{for all }k\geq 2\\
W^Q_{1,-1} &= 1 \\
W^Q_{1,n} &= W^Q_{1,n-1} + W^Q_{1,n-2} + \cdots + W^Q_{1,n-(Q-1)}\qquad\text{for }n \geq 0.
\end{align}The sequence of $W^Q_{1,n}$ are none other than generalized Fibonacci numbers! I guess we could call them $Q$bonacci numbers? When $Q=3$, we recover the standard Fibonacci numbers (A000045):
\[
\{1,1,2,3,5,8,13,21,\dots\}
\]but shifted by 2 (we are indexing starting from -1 here, but typically Fibonacci numbers are defined where the first “1” occurs at index 1). When $Q=4$, we obtain the so-called Tribonacci numbers (A000073):
\[
\{1,1,2,4,7,13,24,44,\dots\}
\]again shifted by 2. Let’s rename the sequence so it coincides with the standard generalized Fibonacci number naming convention.
\[
F^Q_n := W^{Q+1}_{1,n-2}
\]

We can derive the rest of the $W^Q_{q,n}$ by again using the recursion, and this allows us to write all $W^Q_{q,n}$ in terms of the $Q$bonacci numbers.
\begin{align}
W^Q_{q,n}
&= W^Q_{1,n-1} + W^Q_{1,n-2} + \cdots + W^Q_{1,n-(Q-q)} \\
&= F^{Q-1}_{n+1} + F^{Q-1}_{n} + \cdots + F^{Q-1}_{n-(Q-q)+2}
\end{align}Converting back to the value function notation, we can write a formula for $V^Q_{q,n}$ and the optimal wager $U^Q_{q,n}$ in terms of the $Q$bonacci numbers:
\[
\begin{aligned}
V^Q_{0,n} &= V^Q_{1,n-1} = \frac{2^{n-1}}{W^Q_{1,n-1}} = \frac{2^{n-1}}{F^{Q-1}_{n+1}} \\
U^Q_{0,n} &= 0 \\
V^Q_{q,n} &= \frac{2^n}{W^Q_{q,n}} = \frac{2^n}{F^{Q-1}_{n+1} + F^{Q-1}_{n} + \cdots + F^{Q-1}_{n-(Q-q)+2}}\qquad\text{for }1\leq q \leq Q-1\\
U^Q_{q,n} &= \frac{2F^{Q-1}_{n+1}}{F^{Q-1}_{n+1} + F^{Q-1}_{n} + \cdots + F^{Q-1}_{n-(Q-q)+2}}-1
\end{aligned}
\]

Therefore, the solution to the original question, how much money can we be guaranteed to win if we wager optimally, is given by the formula

$\displaystyle
V^Q_{0,N} = \frac{2^{N-1}}{F^{Q-1}_{N+1}}
$

Growth over time

We might also be interested in the limit $N\to\infty$. In other words, what will our asymptotic growth rate look like if $N$ is much larger than $Q$? The generalized Fibonacci numbers have an asymptotically exponential growth, because they are solutions of a linear recurrence. This leads to Binet’s formula for the $n^\text{th}$ Fibonacci number:
\[
F^2_n = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n – \left(\frac{1-\sqrt{5}}{2}\right)^n \right)
\]In spite of the $\sqrt{5}$ terms, this formula always produces integers! The asymptotic growth of $F^2_n$ is dictated by the term with the largest magnitude. In this case, $F^2_n \sim O\left( \varphi^n \right)$, where $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio. The Binet formula can also be generalized for $Q \gt 2$, and so can the asymptotic rate. The following paper by Dresden and Du does just this. I will summarize the key result.
\[
F^Q_n = O(\alpha^n)
\]Where $\alpha$ is the positive real root (there is only one) of the equation
\[
\alpha^Q = \alpha^{Q-1} + \alpha^{Q-2} + \cdots + \alpha + 1
\]In general, this polynomial will have one root that is positive and less than 2, and the other roots will be negative or complex and will have magnitude less than 1. In the paper, the authors prove that $\alpha$ increases as we increase $Q$, and $2-\frac{1}{Q} \lt \alpha \lt 2$. The growth rate of our earnings is given by $\frac{2}{\alpha}$. Here is what we obtain for different values of $Q$:

There is no known closed-form expression for $\alpha$ when $Q \geq 5$ as quintics (polynomials of degree $5$) are not solvable using standard functions like square roots, but it is easy enough to approximate. One way to do this is to notice that the polynomial that defines $\alpha$ is precisely the characteristic polynomial of the $Q\times Q$ matrix:
\[
A = \begin{bmatrix}
0 & 1 & 0 & \cdots & 0 \\
0 & 0 & 1 & \ddots & 0 \\
\vdots & \vdots & \ddots & \ddots & \vdots \\
0 & 0 & \cdots & 0 & 1 \\
1 & 1 & \cdots & 1 & 1
\end{bmatrix} \in \mathbb{R}^{Q\times Q}
\]Therefore $\alpha = \rho(A)$ is spectral radius of the matrix $A$. This can be found efficiently using something like the Power Iteration, particularly because this top eigenvalue is so well-separated from the other eigenvalues, which have magnitude less than 1.