I mentioned today a problem of minimizing the expected number of questions required to identify the greatest of $X_1,\dotsc,X_n$, where these are i.i.d. $U[0,1]$.
We pick a set $A(1) \subset [0, 1]$ and ask which $X_i \in A(1)$. Depending on the response, we pick another subset $A(2)$ and ask which $X_i \in A(2)$, and so on, until we identify the largest $X_i$.
It turns out that it is optimal to ask questions only of the special form "Which $X_i$ are bigger than a(1)?", "Which $X_i$ are bigger than a(2)", etc.
If you would like to see how this is proved, the paper is An optimal strategy for a conflict resolution problem, by V. Anantharam and P. Varayia, Systems and Control Letters, 1986, pp. 329 -332.
A fact about this problem which is initially surprising is that the minimum expected number of questions required remains bounded as $n\to\infty$. Just make the first question of the form "Which $X_i$ are bigger than n/(n+1)?"
We pick a set $A(1) \subset [0, 1]$ and ask which $X_i \in A(1)$. Depending on the response, we pick another subset $A(2)$ and ask which $X_i \in A(2)$, and so on, until we identify the largest $X_i$.
It turns out that it is optimal to ask questions only of the special form "Which $X_i$ are bigger than a(1)?", "Which $X_i$ are bigger than a(2)", etc.
If you would like to see how this is proved, the paper is An optimal strategy for a conflict resolution problem, by V. Anantharam and P. Varayia, Systems and Control Letters, 1986, pp. 329 -332.
A fact about this problem which is initially surprising is that the minimum expected number of questions required remains bounded as $n\to\infty$. Just make the first question of the form "Which $X_i$ are bigger than n/(n+1)?"
