4
$\begingroup$

There are $m$ i.i.d. draws of $x$ made from a uniform distribution on $[0,1]$. The $n$ ($n\leq m$) lowest draws are "winners", i.e. if we write $x_1\leq\ldots\leq x_n\ldots\leq x_m$, the draws $x_1$ to $x_n$ are "winning draws".

Now player/draw $i$ learns his $x_i$ and the fact that he is a winner, i.e. $i\in[1,n]$. What is the expected value of the remaining $(n-1)$ winning draws, given $i$'s knowledge of his own draw and the fact that he is a winner (but not knowing his "rank"/position among the winners).


EDIT: With the help of the comments below, this is what I have managed to do (credits to the commentators!):

  • The unconditional expected value of the winning draws is $\frac{1}{n}\sum_{i=1}^n \frac{i}{1+m}=\frac{n+1}{2(m+1)}$.
  • Obviously, the unconditional cdf is given by $F(x)=x$ for $x\in[0,1]$.
  • $i$ can be the 1st, 2nd, ... nth of the winners. For each rank, compute the expected value of the remaining $n-1$ winners (distributed below/above him, depending on $i$'s rank) and weight it by the probability of this rank.
  • The expected value of the remaining winners, conditional on $x_i$ and the knowledge that $i$ is a "winner", can hence be computed by (incomplete and possibly wrong!):

\begin{alignat*}{3} \frac{1}{n-1}\bigg(% &(1-x_i)^{m-1} &\cdot\binom{m-1}{0} &[(1-1)\frac{x_i}{2} &+\sum_{k=1}^{n-1}(x_i+(1-x_i)E[x_{(k)}^{m-1}])]\\ + &(1-x_i)^{m-2}x_i^1 &\cdot\binom{m-1}{1} &[(2-1)\frac{x_i}{2} &+\sum_{k=1}^{n-2}(x_i+(1-x_i)E[x_{(k)}^{m-2}])]\\ + &\ldots\\ + &(1-x_i)^{m-j-2}x_i^{j-1} &\cdot\binom{m-1}{j-1} &[(j-1)\frac{x_i}{2} &+\sum_{k=1}^{n-j}(x_i+(1-x_i)E[x_{(k)}^{m-j}])]\\ + &\ldots\\ + &(1-x_i)^{m-n-1}x_i^{n-1} &\cdot\binom{m-1}{n-1} &[(n-1)\frac{x_i}{2} &+\sum_{k=1}^{n-n}(x_i+(1-x_i)E[x_{(k)}^{m-n}])]% \bigg) \end{alignat*}


QUESTIONS:

  1. Is the above correct? For example, am I missing a normalisation?
  2. Is it correct that if in addition $i$ also knew his "rank", rather than using the summation above, he would only consider the respective summand indicating the correct position. (From the comments, this seems to be correct.) How does this change a potential normalisation?
  3. Is it correct that $$ E[x_{(k)}^{m-j}]=\frac{k}{m+1-j} $$ in the equation above, with $x_{(k)}^{m-j}$ being (if I understand it correctly) the k-th lowest out of $m-j$ iid draws?
  4. If I was also interested in the expected square of the other "winners" (not the square of the expected other winners), I would need to modify the formula above such that:
    • replace $(j-1)\frac{x_i}{2}$ by $$E[\sum_{k=1}^{j-1}x_k^2|x_k\sim U(0,x_i), \text{ iid}]=\frac{x_i^2 (2j-1)}{6j}$$
    • and $E[x_{(k)}^{m-j}]$ by $$E[(x_{(k)}^{m-j})^2]=(\frac{k}{m+1-j})^2$$

Also, should I delete my lengthy (and wrong) comments below? Should I make this question more "canonical" (and if so, how)?

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ If the rank $i$ and the position $x$ are both known, the remaining winning sample is made of $i-1$ values i.i.d. uniform on $(0,x)$ and of the $n-i$ lowest positions in an i.i.d. sample of size $m-i$ uniform on $(x,1)$. Thus the conditional mean $w$ of the remaining winning sample is $$E(w\mid x,i)=(i-1)\frac{x}{2}+\sum_{k=1}^{n-i}(x+(1-x)E(x_{(k)}^{m-i}))=(i-1)\frac{x}{2}+\sum_{k=1}^{n-i}\left(x+(1-x)\frac{k}{m-i+1}\right).$$ $\endgroup$ – Did Jun 21 '16 at 8:56
  • 1
    $\begingroup$ The general question can be reformulated, maybe more canonically, as follows. Let $(X_k^{(m)})_{1\leqslant k\leqslant m}$ denote an ordered sample uniform on $(0,1)$ and $W_n^m=\{X_k^{(m)}\mid1\leqslant k\leqslant n\}$, then, what is $$E(X_1^{(m)}+\cdots+X_n^{(m)}-x\mid x\in W_n^m)\ ?$$ $\endgroup$ – Did Jun 21 '16 at 9:01
  • $\begingroup$ @Did, is this really the same? Your expression, I would presume, could be rewritten $$ E(X_1^{(m)}+\cdots+X_n^{(m)})-x|_{x\in W_n^m} = \frac{n+1)}{2(m+1)}-x, $$ i.e. we would be considering the $n$ lowest draws (in expectation) and substract one realisation ($x$) rather than only considering the remaining ($n-1$) other lowest draws (in expectation). Is this really the same? $\endgroup$ – Bernd Jun 21 '16 at 10:20
  • 1
    $\begingroup$ @Bernd: Yes, unfortunately that answer was incorrect, because I'd wrongly assumed that $x$ is equally likely to be any of the first $n$ order statistics. To get the answer, multiply your lines by the binomial coefficients given above, fill in the dots using Did's expression for the expected value for known rank (taking into account that he repurposed $i$ to denote the rank), add up all the lines and normalise by the sum of the probabilities (including the binomial coefficients). $\endgroup$ – joriki Jun 21 '16 at 19:43
  • 1
    $\begingroup$ I didn't post this as an answer because that tends to reduce attention for the question and someone might find a closed form after all; but if you like I can write it out as an answer. $\endgroup$ – joriki Jun 21 '16 at 19:44
0
$\begingroup$

Based on the comments above, this is what I've come to:

There are $m$ i.i.d. draws of X from $U(0,1)$, with $x_{(1)}\leq\ldots\leq x_{(n)}\leq\ldots\leq x_{(m)}$ being the order statistics. Given some $x_{(i)}=x_i, i\in N=\{1,\ldots,n\}$, I want to compute the expected average of the $(n-1)$ remaining lowest draws - conditional on knowing $x_i, i\in N$, but not knowing the rank $(i)$ itself! That is, I know that the draw $x_i$ is among the $n$ lowest, but not its precise order.

With the help of the comments, the solution seems to be that this expectation equals

$$ \underbrace{\frac{1}{(n-1)}}_{1.}\cdot\underbrace{\frac{1}{\sum_{j=1}^n \binom{m-1}{j-1}\left(1-x_i\right)^{m-j}x_i^{j-1}}}_{2.}\cdot\sum_{j=1}^n\underbrace{\binom{m-1}{j-1}(1-x_i)^{m-j}x_i^{j-1}}_{3.}\underbrace{\left((j-1)\frac{x_i}{2}+\sum_{k=1}^{n-j}(x_i+\frac{k(1-x_i)}{m-j+1})\right)}_{4.} $$

where the terms represent

  1. average ($n-1$ items)
  2. normalisation
  3. probability of $x_i$ being order position $j$
  4. conditional expectation of the remaining $(n-1)$ samples if $x_i$ is order position $j$

If anyone can confirm this (I posted it as a comment previously), I'd be very grateful. Also, if one of the commenters who helped me with the solution would like to post this as an answer themselves, I am more than happy to mark it as accepted!

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.