2
$\begingroup$

The problem is as follows:

Six players draw, one after another and independently, a number uniformly distributed on $[0,1]$.

A player is called a recordist if he draws a number that is larger than all the numbers drawn by players before him.

What is the expected value of the number of recordists?

Attempted solution:

I define $X_i,\ 1 \leq i \leq 6$, as the indicator of the $i$th player being a recordist. In other words, $$X_i = \left\{ \begin{array}{ll} 1 &, \text{if the $i$th player is a recordist} \\ 0 &, \text{else} \end{array} \right. $$ Now since for all $\,i \neq j, \; \Pr(X_i \gt X_j ) = 0.5\,$, we have $$\Pr(X_i = k) = \left\{ \begin{array}{ll} \left(\frac{1}{2}\right)^{i-1} &, k=1\\ \ \ \ \ 0 &, k=0 \end{array} \right. $$ Next, $X = \sum_{i=1}^{6} X_i$ , is the number of recordists, and so $$ \mathbb{E} X = \mathbb{E} \left(\sum_{i=1}^{6} X_i\right) = \sum_{i=1}^{6} (\mathbb{E} X_i) = \sum_{i=1}^{6} \left(\frac{1}{2}\right)^{i-1} = \sum_{i=0}^{5} \left(\frac{1}{2}\right)^{i} = \frac{63}{32} $$ This is not the correct answer and so I turn to you for help. Thx, Gal.

$\endgroup$
  • $\begingroup$ It is not true $Pr(X_i=k)=0$ for $k=0$ as you have written, but that is a typo and does not affect the solution (which I still cannot figure, because I find the same as you do). $\endgroup$ – Jimmy R. Feb 27 '14 at 4:16
  • $\begingroup$ Is perhaps specified that Player 1 is not a recordist? Or something else? The problem, as written, has the solution you have found. $\endgroup$ – Jimmy R. Feb 27 '14 at 4:25
  • $\begingroup$ Is the first player a recordist or not? The maximum of an empty set is usually undefined. $\endgroup$ – DanielV Feb 27 '14 at 4:48
  • $\begingroup$ Interestingly, it doesn't matter what the range is or whether the draw is uniform. All that matters is that it is a non discrete range. $\endgroup$ – DanielV Feb 27 '14 at 6:16
  • $\begingroup$ To help clarify what was wrong in your solution: Let the numbers the players draw be $Y_1,\ldots,Y_6$, then $$Pr(X_3=1)=Pr(Y_3>\max(Y_1,Y_2))=Pr(Y_3>Y_2|Y_2>Y_1)Pr(Y_2>Y_1)+Pr(Y_3>Y_1|Y_1>Y_2)Pr(Y_1>Y_2) = \star $$ You are correct that $Pr(Y_i>Y_j)=\frac{1}{2}$, and together with the symmetry of the summands, this gives: $$\star=2Pr(Y_3>Y_2|Y_2>Y_1)\frac{1}{2}=Pr(Y_3>Y_2|Y_2>Y_1)<Pr(Y_3>Y_2)=\frac{1}{2}$$ In short, there are messy conditional probabilities you'd have to deal with in this style of approach. $\endgroup$ – Mathily Oct 24 '16 at 18:08
2
$\begingroup$

As in your calculation, let $X_i=1$ if Player $i$ is a recordist, and $0$ otherwise.

Since we are dealing with a continuous distribution, the probability of a tie is $0$. Since all permutations are equally likely, the probability $i$ is a recordist is $\frac{1}{i}$. Thus the expected number is $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}.$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 This is the same answer I got, but a much simpler way of looking at it. $\endgroup$ – DanielV Feb 27 '14 at 6:16
  • $\begingroup$ Thx very much!Can I view the problem this way: when player i draws his number, the interval $[0,1]$ $\endgroup$ – GalMichaeli Feb 27 '14 at 8:01
  • $\begingroup$ The intended comment did not get fully transmitted, I only have one line of it. $\endgroup$ – André Nicolas Feb 27 '14 at 14:41
1
$\begingroup$

If I understand your question correctly then the answer is $\frac {1764} {720} = \frac {49} {20}$.

To each person assign a ranking. The person who draws lowest has ranking 1, the person who draws the largest number has ranking 6.

List the rankings of a drawing in order as an array, $S$, by the order of draw; for example, one $S$ could be $\{3, 4, 1, 6, 5, 2\}$. The number of recordists is given by the length of a set: $$|\{i\, \text{ s.t. } (\forall\, j < i)\, S_j < S_i\}|$$

There are $6!$ possible permutations. With an epiphany we see that all permutations are equally likely. There is probably some clever way to divide the $720$ permutations into cases, for example we know that all permutations starting with $6$ have only $1$ recordist, the first drawer. You can probably recursively define the rest based on that property.

I found it easier to run the $720$ cases through a C program and got $1764$.


Calling the number of players $N$, and given that there are $N!$ permutations which forms the denominator for the probability, the numerator of this probability forms a sequence as a function of $N$ which is apparently something called "Unsigned Stirling numbers of the first kind". Here is its entry: Online integer Encyclopedia.

They don't show any nice closed form, which means using a computer was probably the only approach for a general $N$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nicely done.${}{}{}{}$ $\endgroup$ – André Nicolas Feb 27 '14 at 6:34

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.