One day you stumble across a magic genie, who says that if you play a simple game with him, you could win fabulous riches. You take the genie up on his offer, and he hands you a stick of length 1. He says that behind his back is another stick, with a random length between 0 and 1 (chosen uniformly over that interval).
Next, you must break your stick into two pieces and present one of those pieces to the genie. If that piece is longer than the genie’s hidden stick, then you win a prize of $\$1$ million times the length of your remaining piece. For example, if you present to the genie a length of $0.4,$ and that’s longer than the genie’s stick, then you win $\$1$ million times $0.6,$ or $\$600,000.$ However, if the genie’s stick is longer, then you win nothing.
Being a regular reader of The Riddler, you crunch some numbers and prepare to break your stick in half. But then you have a thought. You ask the genie if you can have more than one turn. For example, if you present the genie with a length of $0.4,$ but the genie’s stick is longer, can you break off a piece of the remaining length of $0.6$ — say, a length of $0.5$ — and then present that to the genie? To keep things fair, your winnings will still be proportional to the leftover length. So had the genie’s length indeed been between $0.4$ and $0.5,$ your first and second guesses, then the remaining length would have been $0.1,$ and you would have won $\$100,000$.
The genie doesn’t think any of this really matters and says you can have as many turns as you desire. If your goal is to maximize your expected winnings, what will your strategy be? And how much money would you expect to win on average?
Mea culpa .... I had a "fundamental misunderstanding of the material" moment and proceeded with the following answer, which only works if you can then also glue all of your tiny stick pieces back together, which I suppose is a bit of a stretch interpretation of the prompt.
Assume that you want to make $n \geq 1$ breaks in the stick, let's say at $0 \leq x_1 \leq x_2 \leq \cdots \leq x_n \leq 1.$ If the genie's stick has length $G \sim U[0,1]$, then the payoff would be $$V_n(G \mid x) = \begin{cases} 1-x_1, &\text{if $G \leq x_1$ }\\ 1-x_2, &\text{if $x_1 \lt G \leq x_2$}\\ \cdots & \\ 1-x_n, &\text{if $x_{n-1} \lt G \leq x_n$}\\ 0, &\text{if $G \gt x_n$}\end{cases}$$ therefore the expected payoff (as a fraction of the genie's $\$1$ million) is $$Q_n(x) = \mathbb{E}_G \Big[ V_n(G \mid x) \Big] = \sum_{i=1}^n (1-x_i) (x_i - x_{i-1}),$$ where we assume that $x_0 = 0.$
Therefore, the optimal selection of breakpoints satisfies the maximization problem \begin{align*}\max_x \,\, & \sum_{i=1}^n (1-x_i) (x_i - x_{i-1}) \\ \text{such that} \,\, & 0 = x_0 \leq x_1 \leq \cdots \leq x_n \leq 1\end{align*} First note that $$\Delta Q_n = \begin{pmatrix} -2 & 1 & 0 & 0 & \cdots & 0 \\ 1 & -2 & 1 & 0 & \cdots & 0 \\ 0 & 1 & -2 & 1 & \cdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & -2 \end{pmatrix} \leq 0$$ is negative semi-definite and hence concave. Further, Slater's condition holds for the set of inequalities $0 = x_0 \leq x_1 \leq \cdots \leq x_n \leq 1,$ so we have the necessary and sufficient conditions that if $\hat{x}$ satisfies $0 \lt \hat{x}_1 \lt \hat{x}_2 \lt \cdots \lt \hat{x}_n \lt 1$ and $\nabla Q_n(\hat{x}) = 0$ then is an optimal solution of the maximization problem.
For $i = 2, \dots, n-1,$ we have $$\frac{\partial}{\partial x_i} Q_n(x) = \frac{\partial}{\partial x_i} \left( (1-x_i) (x_i - x_{i-1} ) + (1 - x_{i+1}) (x_{i+1} - x_i) \right) = x_{i-1} + x_{i+1} - 2x_i.$$ We additionally have $$\frac{\partial}{\partial x_1} Q_n(x) = \frac{\partial}{\partial x_1} \left( (1-x_1) x_1 + (1 - x_2) (x_2 - x_1) \right) = x_2 - 2x_1$$ and $$\frac{\partial}{\partial x_n} Q_n(x) = \frac{\partial}{\partial x_n} (1-x_n) (x_n - x_{n-1}) = 1 + x_{n-1} - 2x_n.$$ Therefore, if we define $\hat{x}^{(n)} = (\hat{x}^{(n)}_1, \dots, \hat{x}^{(n)}_n )$ with $\hat{x}^{(n)}_i = \frac{i}{n+1},$ then we see that $\nabla Q_n(\hat{x}^{(n)}) = 0$ and hence $$Q_n(\hat{x}^{(n)}) = \sum_{i=1}^n (1-\frac{i}{n+1}) \frac{1}{n+1} = \frac{1}{(n+1)^2} \frac{n(n+1)}{2} = \frac{n}{2(n+1)}$$ is the optimal fraction of the $\$1$ million that can be won from the genie when making $n$ cuts. As $n \uparrow \infty,$ we get $\lim_{n\to \infty} Q_n(\hat{x}^{(n)}) = \lim_{n \to \infty} \frac{n}{2(n+1)} = \frac{1}{2},$ so you can win as close to $\$500,000$ as desired.
No comments:
Post a Comment