7
$\begingroup$

Let $a_n$ be a given sequence of positive numbers, and $X_n$ a sequence of independent random variables with each $X_n$ uniformly distributed on $[0, a_n]$.

Question: Let $N \geq 2$ be an arbitrary integer. What is

$$\mathbb P(X_N > X_{N-1} > \dots > X_1)$$

for the following choices of $a_n$?

i) Arithmetic progression: $a_n = n$.

ii) Geometric progression: $a_n = 2^n$.

iii) Square numbers: $a_n = n^2$.

Comments:

The problem seems to boil down to computing the (normalized) volume of some complicated $N$-dimensional shapes. For example, in the simplest case of a constant sequence $a_n = 1$, the probability is the volume of the standard $N$-simplex, $\frac{1}{N!}$.

Update: The problems (1) and (2) are effectively solved by the work of Richard Stanley, as mentioned in the comments. The case of square numbers seems quite interesting to analyze.

$\endgroup$

1 Answer 1

6
+200
$\begingroup$

Not an answer, but a guess that may help someone... Based on computing the first few values $P_N:=\mathbb{P}(X_N>X_{N-1}>\cdots>X_1)$ it is not too difficult to guess the formulas $$P_N = \frac{(N+1)^{N-1}}{(N!)^2}$$ for $a_n=n$ and the generating function $$\sum_{N=0}^\infty P_N x^N = \frac{1}{\sum_{k=0}^\infty \frac{(-1)^k}{k!}\, 2^{-k(k-1)/2} x^k}$$ for $a_n = 2^n$.

$\endgroup$
7
  • $\begingroup$ Maybe, you can prove the general formula by induction ? $\endgroup$
    – G. Melfi
    Commented Oct 27, 2023 at 14:06
  • $\begingroup$ @G.Melfi Induction is not likely to work, since considering the inductive hypothesis on the previous $N-1$ terms tells you the volume of the projection of the $N$ dimensional shape onto the $N-1$ plane spanned by the first few coordinates. Which unfortunately says nothing about the volume of the original shape. I do have an alternative combinatorial description though… will post it up when I have time. $\endgroup$
    – Nate River
    Commented Oct 27, 2023 at 14:20
  • $\begingroup$ @Timothy Budd The formula I have agrees with yours for $N = 2, 3$. It is written as a combinatorial sum instead of explicitly. $\endgroup$
    – Nate River
    Commented Oct 27, 2023 at 14:47
  • 1
    $\begingroup$ In fact I’ve just checked it up to $N = 13$. $\endgroup$
    – Nate River
    Commented Oct 27, 2023 at 15:16
  • 4
    $\begingroup$ @NateRiver This link works for me. The full reference is Rectangle Probabilities for Uniform Order statistics and the Probability That the Empirical Distribution Function Lies Between Two Distribution Functions,G. P. Steck, Ann. Math. Statist. 42(1): 1-11 (February, 1971). $\endgroup$ Commented Oct 27, 2023 at 16:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .