Guessing the upper bound of an interval from 10 independent uniform draws

Question

Suppose you draw an integer $N$ uniformly in $[1, 1000]$. Then draw 10 integers $(X_1, ..., X_{10})$ uniformly from $[1,N]$. Suppose you are shown the 10 numbers, and the game is you win \$1 if you guess $N$ right and loose \$1 each time you fail.

1. What could be your strategy ?
2. Now what if you win \$N if you guess correctly ?
3. Now what if you win \$N/2 ?

Answer 1

[Partial answer]

The MLE and MAP estimators of $N$ in this case are both $\max_i X_i$.

Let $p_n := P(N = \max_i X_i \mid N=n)$ be the conditional probability of success given $N=n$. You can show that this equals $p_n = 1 - \left(\frac{n-1}{n}\right)^{10}$.

Let $w_n$ be the amount you win when $N=n$. In the three parts, we have $w_n$ being $1$, $n$, and $n/2$ respectively.

The expected payoff is $\sum_{n=1}^{1000} (w_np_n - (1 - p_n)) = -1000 + \sum_{n=1}^{1000} (w_n+1) p_n$.

Not sure how to handle the $p_n$. Some crude approximations for $p_n$ (for large $n$) are $10/n$ and $1-e^{-10/n}$, but neither seem helpful.

Numerical results: the expected payoffs of this estimator are approximately $-899$, $8799$, and $3924$ respectively.

Answer 2

Fix values $x_1,\ldots,x_{10}$. Now for any $n\in[\max_ix_i,1000]$ we have $$P(X_1=x_1,\ldots,X_{10}=x_{10}\mid N=n)=\frac{1}{n^{10}},$$ and by Bayes' rule, noting that $P(N=n)$ is constant, $$P(N=n\mid X_1=x_1,\ldots,X_{10}=x_{10})=\frac{C}{n^{10}}$$ for some $C$ that does not depend on $n$.

The three games come down to maximising $f(n)P(N=n\mid X_1=x_1,\ldots,X_{10}=x_{10})$ for $f(n)=2,1+n,1+n/2$ respectively. In each case $f(n)P(N=n\mid X_1=x_1,\ldots,X_{10}=x_{10})=an^{-10}+bn^{-9}$ for some $a,b\geq 0$ and is decreasing in $n$ for $n\in[\max_ix_i,1000]$, so we should just guess the maximum of the $X_i$.