Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For $a \in \mathbb{R}_{+}$ and $n \in \mathbb{N}_{+}$ draw $n-1$ points $X_1, \ldots, X_{n-1}$ independently, uniformly at random from the interval $I = [0, a]$. These points partition $I$ into $n$ disjoint subintervals $I_1 \, \dot\cup \ldots \dot\cup \, I_n = I$. Let $Y_i := |I_i| \in [0, a]$ denote the interval length of the $i$'th subinterval.

How are the $Y_i$'s distributed? I am especially interested in the expectation and the variance.

Here are my thoughts about this: I suppose that all $Y_i$'s are identically distributed, i.e., $Y_i \sim Y$ for some random variable $Y$. Further, I suppose that the expectation of $Y$ is $\mathbb{E}(Y) = \frac{a}{n}$. However, I have no clue about the variance, and I can neither prove my conjectures, nor find an answer on the internet.

Can you help me on this?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

That $\forall i, Y_i \sim Y$ is evident from the symmetry observed if you consider the interval wrapped around as a circle, where $n$ random points are chosen to break the circumference into $n$ random arcs. The length of any arc is obviously identically distributed.

To find the mean, observe that $\sum {Y_i} = a$
Take expectations on both sides, and use $\mathbb{E}(Y_i) = \mathbb{E}(Y)$ to prove your conjecture.

To find the distribution of $Y$ and other properties such as variance, perhaps the easiest way is to focus on $Y_n$. Let $f(t)$ and $F(t)$ denote the distribution function of $Y$ and its cumulative. Then we have,

$\mathbb{P}(Y_n \ge t) = \mathbb{P} (\max X_i \lt a-t)$
$\quad \quad \quad \quad = \mathbb{P}(\forall i, X_i < a-t)$
$\quad \quad \quad \quad = \prod_{i} \dfrac{a-t}{a}$
$\quad \quad \quad \quad = \left( \dfrac{a-t}{a} \right)^{n-1}$

$F(t) = \mathbb{P}(Y_n \lt t) = 1 - \mathbb{P}(Y_n \ge t)$
$\quad= 1 - \left( \dfrac{a-t}{a} \right)^{n-1}$

Differentiating, $f(t) = \dfrac{n-1}{a} \left( \dfrac{a-t}{a} \right)^{n-2}$

Hope that helps! [and thanks for the correction in $f(t)$]

share|improve this answer
    
In the analogy with the circle the fact that the $n$th point is deterministic makes not obvious that the $n$ intervals are exchangeable. Hence obviously in The length of any arc is obviously identically distributed is (obviously) a coup. –  Did Jan 31 '13 at 13:59
    
@Did: I think one can still work out this symmetry argument a bit more carefully: Let the first 'somehow chosen' point represent the origin. Since the interval lengths are defined only by their relative positions to the origin and to each other, the absolute position of the origin on the circle does not matter, thus, it can be chosen deterministically, or uniformly, or according to any other distribution. –  cubic lettuce Jan 31 '13 at 14:14
    
Exploiting the symmetry makes the rest much easier than the other approaches. There is just a small flaw, namely, it has to be $f(t) = \frac{(n-1)}{a} \left( \dfrac{a-t}{a} \right)^{n-2}$. Using this, one also gets that $\mathbb{E}(Y) = \int_0^a t f(t) dt = \frac{a}{n}$, and $\mathbb{E}(Y^2) = \int_0^a t^2 f(t) dt =\frac{2a^2(n-1)}{n^3-n}$, thus, $var(Y) = \mathbb{E}(Y^2) - \mathbb{E}(Y)^2 = \frac{a^2(n-1)}{n^2(n+1)}$, which matches Did's result for $a=1$. –  cubic lettuce Jan 31 '13 at 14:16
    
@cubiclettuce it can be chosen deterministically, or uniformly, or according to any other distribution... For example, uniformly in the circle. Indeed, this is the key. (By the way, nice username!) –  Did Jan 31 '13 at 14:20
    
@cubiclettuce Corrected the flaw - thanks. On the symmetry, yes while $n$ points are randomly chosen on the circle, any one of those is picked (anyhow) to open up the circle back into the interval. –  Macavity Jan 31 '13 at 15:53

Assume without loss of generality that $a=1$ and define $I_i=[Z_{i-1},Z_i]$ hence $Z_0=0$, $Z_n=1$ and $(Z_i)_{1\leqslant i\leqslant n-1}$ is the ordered sample $(X_i)_{1\leqslant i\leqslant n-1}$.

For $x\lt y$ in $(0,1)$, $[Z_{i-1}\leqslant x,y\leqslant Z_i]$ means that $(x,y)\subseteq I_i$ which means that $i-1$ points from the sample $(X_i)_{1\leqslant i\leqslant n-1}$ are in $(0,x)$ and the $n-i$ others are in $(y,1)$. This happens with probability $$ \mathbb P(Z_{i-1}\leqslant x,y\leqslant Z_i)=\binom{n-1}{i-1}x^{i-1}(1-y)^{n-i}, $$ hence $\mathbb P(Z_{i-1}\in\mathrm dx,Z_i\in\mathrm dy)=f_i(x,y)\mathrm dx\mathrm dy$, with $$ f_i(x,y)=\binom{n-1}{i-1}(i-1)(n-i)x^{i-2}(1-y)^{n-i-1}\mathbf 1_{0\lt x\lt y\lt1}. $$ Projecting this on $Y_i=Z_i-Z_{i-1}$ yields $\mathbb P(Y_{i}\in\mathrm dz)=g_i(z)\mathrm dz$, with $$ g_i(z)=\int_0^{1-z}f_i(x,x+z)\mathrm dx. $$ The change of variables $x=(1-z)t$ and the binomial identity $$ \int_0^1t^{i-2}(1-t)^{n-i-1}\mathrm dt=\mathrm{B}(i-1,n-i)=\frac{(i-2)!(n-i-1)!}{(n-2)!}, $$ yield $$ g_i(z)=(n-1)(1-z)^{n-2}\mathbf 1_{0\lt z\lt 1}. $$ It follows that the density of $1-Y_i$ is $(n-1)z^{n-2}\mathbf 1_{0\lt z\lt 1}$, hence, for every $a\gt1-n$, $$ \mathbb E((1-Y_i)^a)=\frac{n-1}{a+n-1}. $$ In particular, $$ \mathbb E(Y_i)=1-\mathbb E(1-Y_i)=\frac1n, $$ and $$ \mathbb E(Y_i^2)=\mathbb E((1-Y_i)^2)-2\mathbb E(1-Y_i)+1=\frac2{n(n+1)}, $$ hence $$ \mathrm{var}(Y_i)=\frac{n-1}{n^2(n+1)}. $$

share|improve this answer

Here is a partial answer that should get you started.

Let $m=n-1$. The values $X_i$ are distinct almost surely. Then, sort the resulting sequence and denote by $Z_i$ the $i$-th element in the sorted sequence. Thus, $Z_1$ is the smallest among the $X_i$ and $Z_m$ is the largest.

We have $Y_k=Z_{k}-Z_{k-1}$ for all $k$ (where for convenience, we put $Z_0=0$ and $Z_{m+1}=b$).

Let us compute the distribution of the $Z_k$. We have

$$ P(Z_k \leq t)=\int_{0}^{t} I_1(x_k)I_2(x_k)dx_k, \tag{1} $$

where

$$ I_1(x_k)=\int_{0}^{x_k}\int_{0}^{x_{k-1}} \ldots \int_{0}^{x_2}dx_1dx_2 \ldots dx_{k-1}=\frac{x_k^{k-1}}{(k-1)!} \tag{2} $$

and

$$ I_2(x_k)=\int_{x_k}^{a}\int_{x_{k+1}}^{a} \ldots \int_{x_{n-1}}^{a}dx_ndx_{n-1} \ldots dx_{k+1}= \frac{(a-x_k)^{n-k}}{(n-k)!} \tag{3} $$

We deduce that $Z_k$ has the the following density :

$$ d_k(t)=\frac{t^{k-1}}{(k-1)!} \times \frac{(a-t)^{n-k}}{(n-k)!} \tag{4} $$

So

$$ E(Z_k)=\int_{0}^a \frac{t^{k}}{(k-1)!} \times \frac{(a-t)^{n-k}}{(n-k)!} dt=\frac{k}{m+1}a \tag{5} $$

and

$$ E(Z_k^2)=\int_{0}^a \frac{t^{k+1}}{(k-1)!} \times \frac{(a-t)^{n-k}}{(n-k)!} dt=\frac{6k}{(m+1)(m+2)}a^2 \tag{6} $$

So $E(Y_k)=E(Z_k)-E(Z_{k-1})=\frac{a}{m+1}=\frac{a}{n}$ as you rightly conjectured.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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