The best probability distribution for the game of Number Master

Question

In the game of Number Master, the player controls a number starting with $1$ and hits the other numbers one by one on the road.

If the player hits a number smaller or equal to the current controlling number, then the controlling number will become the sum of itself and the number he/she just hit.

If the player hits a number larger than the current controlling number, then he/she loses the game and the score is $0$.

If the player finished the game without hitting a number larger than the number he/she controls, then he/she wins the game and gets the score of the value of the final number he/she controls.

We assume the numbers on the road are generated randomly and independently from a probability distribution $D$, and $N$ is a sufficiently large integer.

The question is to find $D$ such that the expectation of the score is maximized for the following two settings:

Q1: There are $N$ numbers on the road and the player must hit them one by one and cannot skip any numbers.

Q2: There are $N$ pairs of numbers on the road and the player must hit one number and skip the other number of each pair of numbers, and the player always choose the better number to hit on each pair of numbers: If both of them are smaller or equal to the current controlling number, then he/she hits the larger one. If only one of them are smaller or equal to the current controlling number, then he/she hits the smaller one. If both of them are larger than the current controlling number, then he/she loses the game with score $0$.

My answer to Q1 is to set $D$ as $Pr(X=1)=1$, then the expectation of the score is $N+1$. It seems that the expectation of the score is less than $N+1$ for any other probability distributions. The answer to Q2 is not clear yet, I guess the power-law distribution may work, but need more effort to find out the explicit answer.

Answer 1

Q1. We can prove your answer to Q1 for small $N$ as follows.

Note first that we can replace each number $x$ to hit by $\lceil x\rceil$, nondecreasing the score. Moreover, no number $x$ bigger than $2^{N-1}$ can be hit. That is, we can suppose that the set $X_N$ of numbers to hit is $\{1,2,\dots, 2^{N-1}\}$ and each natural number $x\in X$ has a probability $p_x$ in the distribution $D$.

For any natural numbers $n\le N$ and $x\le 2^{N-1}$ let $E(n,x)$ be the expectation of the score when there remains $n$ numbers to hit and the current controlling number is $x$. Then $$E(1,x)=\sum_{y=1}^x (x+y)p_y\mbox{ and }E(n,x)=\sum_{y=1}^x E(n-1,x+y)p_y$$ for $n>1$. This easily implies that the required expectation $E(N,1)$ of the score is equal to $$\sum\{(x_0+\dots+x_N)p_{x_1}\dots p_{x_N}: x_0=1\mbox{ and }X\ni x_i\le\sum_{j=0}^{i-1} x_j\mbox{ for each natural }i\le N\}.$$

Now we can answer the question for small $N$.

Let $N=2$. Then in the sum for $E(N,1)$ we have the following sequences $(x_1,x_2)$: $(1,1)$ and $(1,2)$. Then $$E(N,1)=3p_1^2+4p_1p_2=p_1(3p_1+4(1-p_1))=p_1(4-p_1),$$ that is maximized when $p_1=1$.

$N=3$ Let $N=2$. Then in the sum for $E(N,1)$ we have the following sequences $(x_1,x_2,x_3)$ with the corresponding sums $\sum_{i=0}^N x_i$ and the products of probabilities:

$(1,1,1):$ $4$ $p_1p_1p_1$

$(1,1,2):$ $5$ $p_1p_1p_2$

$(1,1,3):$ $6$ $p_1p_1p_3$

$(1,2,1):$ $5$ $p_1p_2p_1$

$(1,2,2):$ $6$ $p_1p_2p_2$

$(1,2,3):$ $7$ $p_1p_2p_3$

$(1,2,4):$ $8$ $p_1p_2p_4$

Thus $$E(N,1)=p_1(4p_1^2+10p_1p_2+6p_1p_3+6p_2^2+7p_2p_3+8p_2p_4).$$

Replacing $p_4$ by $1-p_1-p_2-p_3$, we obtain

$$E(N,1)=p_1(4p_1^2+2p_1p_2+6p_1p_3-2p_2^2-p_2p_3+8p_2).$$

Increasing $p_1$, if needed, we can assume that $p_1+p_2+p_3=1$. Then replacing $p_3$ by $1-p_1-p_2$, we obtain

$$E(N,1)=p_1(-2p_1^2-3p_1p_2-p_2^2+6p_1+7p_2).$$

Since $\frac{\partial E(N,1)}{\partial p_2}=p_1(-3p_1-2p_2+7)\ge 0$, increasing $p_2$, if needed, we can assume that $p_1+p_2=1$. Then replacing $p_2$ by $1-p_1$, we obtain

$$E(N,1)=p_1(6-2p_1),$$ that is maximized when $p_1=1$.