17
$\begingroup$

What is the expected value of an N-dimensional vector of uniformly distributed random numbers which sum to 1 and have been sorted in descending order?

Here is the algorithm for drawing a sample from the distribution of this N-dimensional vector:

  • Create an N-1 dimensional vector of uniformly distributed random numbers between 0 and 1, inclusive. For example, for N=3, [0.564, 0.243].
  • Append the numbers 0 and 1 to the vector, then sort it in ascending order. For example, [0, 0.243, 0.564, 1].
  • Compute the 1st-order differences of the vector, yielding an N-dimensional vector of uniformly distributed random numbers that sum to 1. For example, [0.243, 0.321, 0.436].
  • Sort this vector into descending order. For example, [0.436, 0.321, 0.243].

It is easy to demonstrate by graphical analogy that for N=2, the expected value of the vector is exactly [3/4, 1/4].

For N=3, by sampling I have determined that the expected value is approximately [0.611, 0.277, 0.111].

For N=4, by sampling I have determined that the expected value is approximately [0.520, 0.271, 0.146, 0.063].

What is the analytical form of the expected value for any value of N?

$\endgroup$
  • $\begingroup$ Is the smallest nonzero entry $2^{-N}$? If so, then you can figure out the rest. $\endgroup$ – David Handelman May 11 '16 at 1:21
  • $\begingroup$ Based on the results of my sampling experiments, it does not appear to be that simple, unfortunately. For example, for N=3, the smallest nonzero entry is 0.111 to 3 significant figures, rather than 0.125. $\endgroup$ – Matthew Lloyd May 11 '16 at 1:50
16
$\begingroup$

You pick $N-1$ points $X_1,\dotsc, X_{N-1}$ independently and uniformly at random in $[0,1]$. They divide the segment $[0,1]$ into $N$ segments of lengths $S_1,\dotsc, S_N$ usually referred to as spacings.

To use your description, rearrange the $X_i$ in increasing order $X_{(1)}\leq \cdots \leq X_{(N-1)}$ and then

$$ S_1= X_{(1)},\;\;S_2= X_{(2)}-X_{(1)},\dotsc , S_N=1-X_{(N-1)}. $$

The random vector $\vec{S}=(S_1,\dotsc, S_n)$ is uniformly distributed on the $(N-1)$-dimensional simplex $\newcommand{\bR}{\mathbb{R}}$

$$ \Delta_{N-1}= \bigl\{\; (s_1,\dotsc, s_N)\in \bR^N_+;\;\;\sum_{j=1}^N s_j=1\;\bigr\} $$

equipped with the normalized surface measure. The "area" $A_{N-1}$ of $\Delta_{N-1}$ is found using the recurrence

$$A_1=\sqrt{2},\;\;A_N= \sqrt{\frac{N+1}{N}}\frac{A_{N-1}}{N}. $$

This yields

$$A_N= \frac{\sqrt{N+1}}{N!}. $$

Rearrange the spacings $S_1,\dotsc,, S_n$ in increasing order

$$S_{(1)}\leq \cdots \leq S_{(N)}. $$

The random vector $(S_{(1)},\dotsc, S_{(N)})$ is uniformly distributed in the $N-1$-dimensional polyhedron

$$ P_{N-1}=\bigl\{\, (s_1,\dotsc, s_N)\in \Delta_{N_1};\;\;s_1\leq \cdots \leq s_N\;\bigr\}. $$

This is another $(N-1)$-dimensional simplex with vertices

$$v_1=(0,0,\dotsc, 0,1),\;\;v_2=\frac{1}{2}(0,\dotsc, 0,1,1),\;v_3=\frac{1}{3}(0,\dotsc, 0,1,1,1),\dotsc, $$

and total "area"

$$ \alpha_{N-1}=\frac{1}{N!} A_{N-1}. $$

The mean you are looking for is the center of mass of the simplex $P_{N-1}$, where the mass is uniformly distributed on this polyhedron.

To compute effectively the coordinates of this center of mass it may be convenient to work with new linear coordinates, $x=(x_1,\dotsc, x_N)$ determined by the basis $v_1,\dotsc, v_N$ of $\bR^N$. They are related to the standard Euclidean coordinates $(s_1,\dotsc, s_N)$ of $\bR^N$ via the equalities

$$ s_j=s_j(x) =\sum_{k=N-j+1}^N\frac{1}{k}x_k,\;\;j=1,\dotsc, N.$$

In the $x$-coordinates the simplex $P_{N-1}$ becomes the simplex

$$ D_{N-1}= \bigl\{\; (x_1,\dotsc, x_N)\in \bR^N_+;\;\;\sum_{j=1}^N x_j=1\;\bigr\} $$

Denote by $dA_x$ the normalized area form on $D_{N-1}$. The coordinates of the center of mass of $P_{N-1}$ are $(\bar{s}_1,\dotsc, \bar{s}_N)$, where

$$\bar{s}_j=\int_{D_{N-1}} s_j(x) dA_x,\;\;j=1,\dotsc, N. $$

Now observe that

$$\int_{D_{N-1}} x_j dA_x= \frac{1}{N},\;\;j=1,\dotsc, N.$$

We deduce

$$ \boxed{E[S_{(j)}]=\bar{s}_j=\frac{1}{N}\sum_{k=N-j+1}^N\frac{1}{k},\;\;j=1,\dotsc, N.} $$

Here is also a plausibility test. The above formula implies

$$\bar{s}_1+\cdots + \bar{s}_N=1. $$

This is in perfect agreement with the equality $S_{(1)}+\cdots +S_{(N)}=1$.

Remark. The problem of the distribution of spacings is rather old. For example there is Witworth formula (1897) describing the expectation of the larges spacing $S_{N}$. More precisely it states

$$ E[S_{(N)}]=\underbrace{\sum_{k=1}^{N}(-1)^{k+1} \frac{1}{k^2} \binom{N-1}{k-1}}_{=:L_N}. $$

It looks rather different from what we proved

$$ E[S_{(N)}]=\bar{s}_N=\frac{1}{N}\left(1+\frac{1}{2}+\cdots +\frac{1}{N}\right). $$

I have not thought how prove directly that

$$ L_N=\bar{s}_N, $$

but simple computer simulations show that indeed the two rather different descriptions are identical. For more details about the spacings problem see this blogpost.

$\endgroup$
  • $\begingroup$ Excellent. Yes, I agree that the expected value is the centroid of this polyhedron. Great progress - this is almost, but not yet, an answer! $\endgroup$ – Matthew Lloyd May 11 '16 at 2:16
  • 1
    $\begingroup$ It was late last night and I was tired so I stopped at a point where the problem becomes manageable. $\endgroup$ – Liviu Nicolaescu May 11 '16 at 8:48
  • 2
    $\begingroup$ @Matthew Lloyd Now you have the complete answer. $\endgroup$ – Liviu Nicolaescu May 11 '16 at 13:34
  • 2
    $\begingroup$ The combinatorial identity can be simplified by using $\frac{1}{k} {N-1 \choose k-1} = \frac{1}{N} {N \choose k}$. Multiplying both sides by N, the identity is equivalent to $\sum_{k=1}^N (-1)^{k+1} \frac{1}{k} {N \choose k} = H_N$. The left hand side is $-\int_0^1 ((1-t)^N - 1)/t ~dt = \int_0^1 ((1-t)^N - 1)/((1-t)-1)~ dt$. Factoring $(x^N-1)$, this is $\int_0^1 \sum_{k=0}^{N-1} (1-t)^k dt$ $= \sum_{k=0}^{N-1} \int_0^1 (1-t)^k dt$ $= \sum_{k=0}^{N-1} 1/(k+1) = H_N$. $\endgroup$ – Douglas Zare May 11 '16 at 15:34
  • $\begingroup$ @Liviu Nicolaescu Fantastic, thanks so much Liviu! The analytical form you give agrees perfectly with the results from my sampling experiments. Thanks for spotting the question and being exactly the right person to answer it :) $\endgroup$ – Matthew Lloyd May 11 '16 at 15:42
15
$\begingroup$

Liviu has given an excellent answer with a nice geometric flavor to it. This answer is meant to serve as a complement with a slightly more probabilistic bent. In the process, some of the computations get buried in favor of bringing out the connections to other areas of elementary probability theory.

A well-known alternative mechanism for generating points uniformly on the simplex is as follows: Let $Z_1,\ldots,Z_n$ be iid exponential random variables. Then $(Z_1/Z,\ldots,Z_n/Z)$ is uniformly distributed on the simplex where $Z = Z_1 + \cdots + Z_n$.

This is a special case of the Dirichlet distribution. In your question, you are effectively interested in computing $\mathbb E \frac{Z_{(k)}}{Z}$ for each $k$ where $Z_{(k)}$ is the $k$th order statistic from your iid exponential sample.

By Rényi representation, we can construct $Z_{(k)}$ directly as follows: Let $Z_{(0)} = 0$, and let $(\widetilde Z_i)_{i \geq 1}$ be a sequence of iid exponentials. Then, form $$ Z_{(k)} = Z_{(k-1)} + \frac{\widetilde Z_k}{n-k+1}\>. $$ Note that $Z = \sum_{k=1}^n Z_k = \sum_{k=1}^n Z_{(k)} = \sum_{k=1}^n \widetilde Z_k$.

Hence $$ \mathbb E \frac{Z_{(k)}}{Z} = \sum_{i=1}^k \frac{1}{n-i+1}\mathbb E \frac{\widetilde Z_i}{Z} = \frac{1}{n} \sum_{i=1}^k \frac{1}{n-i+1} \>, $$ since the $\widetilde Z_i/Z$ have the same $\text{Beta}(1,n-1)$ distribution for each $i$.

References

  1. A. Rényi (1953), On the theory of order statistics, Acta Mathematica Hungarica, vol. 4(3–4), pp. 191–231.
  2. L. Devroye (1986), Non-Uniform Random Variate Generation, Springer-Verlag. (Chapter 5: Uniform and Exponential Spacings).

Postscriptum: Note that the algorithms given in this answer for generating a point on the standard simplex and on its sorted variant are both $O(n)$ compared to the $O(n \log n)$ approach in the question, so if $n$ is large and computing $\log x$ for $0 < x < 1$ is cheap, this may lead to meaningful gains in sampling efficiency.

$\endgroup$
  • $\begingroup$ Simple and elegant! Beautiful $\endgroup$ – Liviu Nicolaescu May 11 '16 at 18:07
  • $\begingroup$ Wow - brilliant! Thank you cardinal! I learned a lot from your answer. So elegant. $\endgroup$ – Matthew Lloyd May 12 '16 at 1:15

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.