The min of the mean of iid exponential variables

Question

Let $X_1, \ldots, X_n, \ldots$ be iid exponential random variables with mean 1. It is well-known that $\min_{1\le j < \infty} \frac{X_1 + \cdots + X_j}{j}$ follows the uniform distribution U(0,1). Can anyone help me find a reference to this result? Many thanks!

Answer 1

$\newcommand\la\lambda\newcommand\w{\mathfrak w}\newcommand\R{\mathbb R}$We have to show that $P(U<u)=u$ for $u\in(0,1)$, where $$U:=\min_{j\ge1} \frac{X_1+\cdots+X_j}j$$ and $X_1,X_2,\dots$ are iid exponential random variables with mean $1$. This minimum is attained almost surely (a.s.), because, by the strong law of large numbers, $\frac{X_1+\cdots+X_j}j\to1$ a.s. as $j\to\infty$, whereas $\inf_{j\ge1} \frac{X_1+\cdots+X_j}j<1$ a.s.

For each natural $j$ and each $u\in(0,1)$, $$\begin{aligned} U<u&\iff\exists j\ge1\ \;\sum_{i=1}^j X_i<ju \\ &\iff\exists j\ge1\ \;Y_{u,j}:=\sum_{i=1}^j(u-X_i)>0 \\ &\iff\bar Y_u>0, \end{aligned}\tag{1}$$ where $\bar Y_u:=\max_{j\ge0}Y_{u,j}$, with $Y_{u,0}=0$ (of course). By the formula $E e^{i\la\bar Y}=\w_+(\la)/\w_+(0)$ at the very end of Section 19 of Chapter 4 (p. 105) and Theorem 2 in this chapter (pp. 106--107) of Borovkov, $$g_u(\la):=E e^{i\la\bar Y_u}=\frac{(1-u)i\la}{1+i\la-e^{i\la u}}$$ for all real $\la$. Note also that $\bar Y_u\ge Y_{u,0}=0$. So, by Proposition 1 in this paper or its arXiv version , $$P(\bar Y_u>0)=E\,\text{sign}\,\bar Y_u =\frac1{\pi i}\,\int_\R \frac{g_u(\la)}\la\,d\la =\frac1{\pi i}\,\int_\R h_u(\la)\,d\la \tag{2} ,$$ where $$h_u(\la):=\frac{g_u(\la)-g_u(\infty-)}\la =(1-u)\frac{1-e^{i \la u}}{\la(e^{i \la u}-1-i\la)}$$ and the integrals are understood in the principal value sense.

$\require{\ulem}$

In view of (1), it remains to show that the integrals in (2) equal $\pi i u$ for all $u\in(0,1)$.

This is now proved at An integral identity

Answer 2

An elegant and more general result can be derived from Renyi representation of exponential order statistics. See my book Statistics: New foundations, toolkit, machine learning recipes, pp 133-138.

Answer 3

We can explicitly keep track of both the running average and the running minimum average.

Let $f(k,m,r)$ be the probability density that after $k$ variables, the minimum average so far is $m$, and the current running average is $r$ with $m<r$.

Let $g(k,m)$ be the probability density that after $k$ variables, the minimum average so far is $m$, and this is also the running average so far.

I claim that for $k\ge2:$ \begin{align} f(k,m,r) &= \frac{e^{-kr}(kr)^{k-1}}{r(k-2)!}1_{[m<r]}\\ g(k,m) &= \frac{e^{-km}(km)^{k-1}}{(k-1)!} \end{align}

Once we have these formulas, we can guess the limiting distribution from the fact that we are only interested in $f$ and not $g$ (since after many draws, the minimum average has almost surely happened in the past), and only in $r=1$ (since after many draws, the running average is almost surely 1). So we can guess that the limiting distribution is a normalization of $f(k,m,1)$, which we can read off as $1_{[m<1]}$, and is the uniform distribution that was desired.

More formally it is enough to show that $$\int_0^\infty f(k,m,r)dr + g(k,m) \to 1_{[m<r]} \text{ as }k \to \infty$$ which I have verified numerically. The first term is just $\Gamma[k-1,km]/(k-2)!$, so the proof of the limit is probably easy even though I haven't found it yet.

Returning to the claim, the formulas for $f$ and $g$ can be proved by an induction for $k'=k+1$: \begin{align} f(k',m,r)= &\int_{x=m}^{k'r/k} f(k,m,x)k'e^{-k'r+kx}dx \\ &+ g(k,m)k'e^{-k'r+km}\\ g(k',m)= &\int_{r=m}^{\infty}\int_{x=m}^{r} f(k,x,r)k'e^{-k'm+kr}dx\,dr \\ &+ \int_{x=m}^{\infty}g(k,x)k'e^{-k'm+kx}dx \end{align} The four terms on the right-hand sides of those equations are just what is needed to keep track of the four possibilities for $m<r$ or $m=r$ and $m_{old}<r_{old}$ or $m_{old}=r_{old}$.

Answer 4

(Since you are looking for a reference, I turn my comment above into an answer:)

A proof using classical fluctuation theory is given my answer to

Expected supremum of average?

(I'm not aware that this result is well known, or of earlier references).

ADDED:

Consider the associated Poisson process $N(t)$ with $N(0)=0$ and interarrival times $X_i$. Then is is easy to see that for $a>0$ \begin{align*} \sup_{t\geq 0}( N(t)-at) \leq 0 \;\; \Longleftrightarrow \;\;\inf_{n\geq 1}\frac{S_n}{n}\geq \frac{1}{a}\end{align*}

It was shown here https://www.ams.org/journals/tran/1957-085-01/S0002-9947-1957-0084900-X/S0002-9947-1957-0084900-X.pdf and here https://www.jstor.org/stable/2237099 that \begin{align*}\mathbb{P}(\sup_{t\geq 0} (N(t)-at)\leq 0)=\Big\{\begin{array}{cc} 1-\frac{1}{a} \mbox { if } a\geq 1\\ 0 \mbox{ else }\end{array}\end{align*}

Thus in this formulation the result is indeed classical.