Expected Value of Riemann Sum for Random Partitions

Question

Source:

This question from order statistics appeared on the qualifying exam for Probability and Stochastic Processes in the Electrical Engineering Department.

Question:

Let $(X_{1},⋯,X_{n})$ be uniformly distributed and from the set \begin{equation} \{(x_{1},⋯,x_{n}):0<x_{1}<⋯<x_{n}<1\}. \end{equation} Also, let $f$ be a continuous function on $[0,1]$. Set $X_{0}=0$. Let $R$ be the weighted sum \begin{equation} R=\sum_{i=0}^{n−1}f(X_{i+1})(X_{i+1}−X_{i}). \end{equation} Show that \begin{equation} E[R]=\int^{1}_{0}f(t)(1−(1−t)^{n})dt. \end{equation}

What I tried:

I was initially trying to integrate over the joint distribution of $X_{1},\cdots,X_{n}$ (assuming all of them are independent) but I am confused how to integrate $f$ in that case.

I would be very thankful for any help in proving this. I found a similar post here Expected value of Rieman sums of a continous function over all possible patitions of $[0,1]$ into n+1 subintervals. but it is unanswered.

Answer 1

I was sure there is an elegant probabilistic argument for this, but sadly, I don't see it. One can do this using the joint density of order statistics. One can easily find online that the joint PDF for $(X_i,X_{i+1})$ is $f_{i,i+1}(u,v)=\frac{n!}{(i-1)!(n-i-1)!}u^{i-1}(1-v)^{n-i-1}$ on $0<u<v<1$. Therefore, one can easily compute

\begin{align} \mathbb{E}[f(X_{i+1})(X_{i+1}-X_i)]&=\int_0^1\int_0^v f(v)[v-u]f_{i,i+1}(u,v)\mathrm{d}u\mathrm{d}v\\ &=\int_0^1\left(\frac{n!(1-v)^{n-i-1}}{(i-1)!(n-i-1)!}\right)f(v)\left(\int_0^v [v-u]u^{i-1}\mathrm{d}u\right)\mathrm{d}v\\ &=\int_0^1\left(\frac{n!(1-v)^{n-i-1}}{(i-1)!(n-i-1)!}\right)f(v)\left[\frac{v^{i+1}}{i(i+1)}\right]\mathrm{d}v\\ &=\int_0^1f(v)\left[{n \choose i+1}v^{i+1}(1-v)^{n-i-1}\right]\mathrm{d}v. \end{align}

Note that this actually holds also for $i=0$ under your convention. Then summing from $i=0$ to $n-1$, reindexing, and interchanging sum and integrals, we obtain:

\begin{align} \mathbb{E}[R]=\int_0^1 f(v) \sum_{i=1}^n {n \choose i}v^{i}(1-v)^{n-i}\mathrm{d}v. \end{align}

But note that $\sum_{i=0}^n {n \choose i}v^{i}(1-v)^{n-i}=(v+(1-v))^n=1$, hence the sum from $i=1$ to $n$ is equal to $1-(1-v)^n$. This is the desired formula.

Answer 2

Note that $R=g(X_1,...,X_n)$ for some function $g$. Moreover, since $(X_1,...,X_n)$ is uniformly distributed on symplex $C:=\{(x_1,...,x_n): 0<x_1<...<x_n<1\}$ which is of $\frac{1}{n!}$ measure, so that the density $h$ of vector $(X_1,...,X_n)$ is given by $h(x_1,...,x_n) = n! \cdot 1_C(x_1,...,x_n)$. Hence $$ \mathbb E[R]=\mathbb E[g(X_1,...,X_n)] = \int_{C}g(x_1,...,x_n)h(x_1,...,x_n)d\lambda_n(x_1,...,x_n)$$ $$ = n!\int_C\sum_{k=1}^nf(x_k)(x_k-x_{k-1})dx_1...dx_n $$ Let's look at case $k=1$ firstly. Our integral is then $$ n!\int_0^1\int_{x_1}^1...\int_{x_{n-1}}^1 f(x_1)x_1dx_n...dx_1 = n!\int_0^1f(x_1)x_1(1-x_1)^{n-1}\frac{1}{(n-1)!}dx_1$$ Now, fix $k \in \{2,...,n\}$ and let us calculate $$ \int_0^1 \int_0^{x_n}...\int_0^{x_2} f(x_k)(x_k-x_{k-1})dx_1...dx_n= \int_0^1...\int_0^{x_k}f(x_k)(x_k-x_{k-1})\frac{x_{k-1}^{k-2}}{(k-2)!}dx_{k-1}...dx_n $$ $$=\int_0^1 ... \int_0^{x_{k+1}}\frac{f(x_k)}{(k-2)!}\big(\frac{x_k^k}{k-1} - \frac{x_k^k}{k})dx_k...dx_n = \int_0^1...\int_0^{x_{k+1}}\frac{f(x_k)x_k^k}{k!}dx_k...dx_n $$ Applying fubini theorem to change order of integration our integral becomes $$ \int_0^1 \int_{x_{k}}^1 ... \int_{x_{n-1}}^1 \frac{f(x_k)x_k^k}{k!}dx_n...dx_k = \int_0^1 \frac{f(x_k)x_k^k}{k!}\cdot(1-x_k)^{n-k}\frac{1}{(n-k)!}dx_k$$ Putting everything together, we arrive at $$ \mathbb E[R] = \sum_{k=1}^n n! \int_0^1 f(x)\frac{x^k}{k!}\frac{(1-x)^{n-k}}{(n-k)!}dx = \int_0^1 f(x) \sum_{k=1}^n{n \choose k}x^k(1-x)^{n-k}dx $$ Now, add the $0'$th term and we arrive at $$ \mathbb E[R]= \int_0^1f(x)\Big(\sum_{k=0}^n {n \choose k}x^k(1-x)^{n-k} - {n \choose 0}x^0(1-x)^n\Big)dx = \int_0^1 f(x)\big(1 - (1-x)^n\big)dx$$

Remark

I've used two facts which you can easily prove by induction, namely $$ \int_{y_j}^1 ... \int_{y_{m-1}}^1 dy_{m}...d_{y_{j+1}} = \frac{1}{(m-j)!}(1-y_j)^{m-j}$$ $$ \int_{0}^{y_m}...\int_0^{y_{j+1}} dy_j...dy_{m-1} = \frac{y_m^{m-j}}{(m-j)!}$$ And one fact, which probably is known to you (which boils down to Bernoulli scheme being a probability distribution (and is a special case of Newton Formula)) $$ \sum_{k=0}^n {n \choose k}x^k(1-x)^{n-k} = 1$$

Answer 3

Think of the $X_k$ as the order statistics from an i.i.d. sample $U_1,\ldots,U_n$ from the uniform distribution on $(0,1)$.

Consider first $f$ of the form $f=1_{(0,s]}$ for fixed $s\in(0,1)$. Then $$ R=X_{N(s)}, $$ where $N(s):=\#\{k:X_k\le s\}$. Therefore $$ P[R\le u]=[1-(s-u)]^n,\qquad 0<u<s, $$ because $R\le u$ if and only if none of the $X_k$ fall into the interval $(u,s]$, which has probability $[1-(s-u)]^n$. Therefore $$ \eqalign{ E[R] &=\int_0^s P[R>u] du \cr &=\int_0^s\left\{1-[1-(s-u)]^n\right\} du =\int_0^s[1-(1-t)^n] dt\cr &=\int_0^1f(t)[1-(1-t)^n] dt.\cr } $$ The result for step functions follows immediately from this, and then by approximation for continuous $f$. (In fact, a little further thought shows that the identity of the problem is true for all bounded measurable $f$.)

Using $R_n$ to indicate the dependence of $R$ on $n$ for a fixed $f$, it's clear that $$ \lim_n E[R_n]=\int_0^1 f(t)\, dt $$ for bounded measurable $f$ (dominated convergence). If $f$ is Riemann integrable, then you also have $\lim_nR_n=\int_0^1 f(t) dt$, almost surely.