How do I calculate this expected value?

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 ith 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.

• 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). – Jimmy R. Feb 27 '14 at 4:16
• Is perhaps specified that Player 1 is not a recordist? Or something else? The problem, as written, has the solution you have found. – Jimmy R. Feb 27 '14 at 4:25
• Is the first player a recordist or not? The maximum of an empty set is usually undefined. – DanielV Feb 27 '14 at 4:48
• 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. – DanielV Feb 27 '14 at 6:16
• 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. – Mathily Oct 24 '16 at 18:08

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}.$$

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

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$.

• Nicely done.${}{}{}{}$ – André Nicolas Feb 27 '14 at 6:34