# Sum of random variables with $x_{i+1}<x_i$

Let $x_{i+1}$ be a uniform distributed random variable in $[0,x_i]$, with $x_0=1$.

Does the sum converge and what is its expected value?
$$\sum_{n=1}^\infty x_n$$

Does there exist a function $f(n)>1$ such that $\lim_{n->\infty} f(n)=1$ and the sum
$$\sum_{n=1}^\infty n^{-f(n)}$$ converges?

-
If $\sum_{n=1}^\infty x_n$ has a finite expectation value $S$, then it must satisfy $S=\int_0^1(x+xS)\mathrm{d}x=(1+S)/2$, and hence $S=1$. – joriki Mar 31 '11 at 23:07
By the way, your two questions being unrelated I am ready to bet they are homework. Did I win? – Did Apr 1 '11 at 6:07

Hint for the first question. Not only that the sum converges and has finite expectation, its distribution is well known: Dickman distribution.

A collection of facts on the generalized Dickman distribution, partially based on the paper "Random minimal directed spanning trees and Dickman-type distributions" by Mathew D. Penrose and Andrew R. Wade [Source: Adv. in Appl. Probab. Volume 36, Number 3 (2004), 691-714.]

For fixed $\theta > 0$ (the case $\theta = 1$ corresponds to the question at hand), define a random variable $X$ by $$X = U_1^{1/\theta } + (U_1 U_2 )^{1/\theta } + (U_1 U_2 U_3 )^{1/\theta } + \cdots ,$$ where $U_1,U_2,\ldots$ is a sequence of independent uniform$(0,1)$ variables. The fact that the infinite random series converges almost surely follows from the monotone convergence theorem (note that the terms are nonnegative, and consider the expectation). The random variable $X$ is equal in distribution to $U^{1/\theta } (1+X)$, where $U$ is uniform$(0,1)$ and independent of $X$. The distribution of $X$ is known as the generalized Dickman distribution with parameter $\theta$ (the ordinary case being $\theta=1$), and denoted by GD$(\theta)$.

The random variable $X$ can be represented (in law) as $X = \sum\nolimits_{n = 1}^\infty {Y_n }$, where $Y_1 > Y_2 > \cdots$ are points of a Poisson point process on $(0,1)$ with intensity measure $(\theta/x)\,{\rm d}x$. Equivalently, consider an increasing L\'evy process (subordinator) $X=\{X(t):t \geq 0\}$ (i.e., $X$ is an increasing process with stationary independent increments, starting at $0$) with L\'evy measure $\nu({\rm d}x) = (\theta/x)\,{\rm d}x$. It has increasing sample paths with infinitely many jumps in the time interval $[s,t]$, for any $0 \leq s < t$. Specifically, the number of jumps in the time interval $[s,t]$ with size in $B \subset (0,1)$ is Poisson distributed with mean $(t-s)\nu(B)$ (note that $\nu((0,1)) = \int_0^1 {(\theta /x)\,{\rm d}x} = \infty$; hence the infinite number of jumps in finite time intervals). The distribution of the random variable $X(1)$ is GD$(\theta)$. For $\theta = 1$, this corresponds to the question at hand as follows. A sample path of the process $X$ in the time interval $[0,1]$ can be realized as follows. With $U_1,U_2,\ldots$ independent uniform$(0,1)$ variables, let the size of the largest jump be $V_1=U_1$. The corresponding jumping time is uniformly distributed on the unit time interval. Now, given $V_1 = v_1$, the size of the second largest jump, $V_2$, is distributed as ${\rm uniform}(0,v_1)$, which is equal in distribution to $v_1 U_2$. As always, the corresponding jumping time is independently and uniformly distributed on the unit time interval. Next, given $V_2 = v_2$, the size of the third largest jump, $V_3$, is distributed as ${\rm uniform}(0,v_2)$, which is equal in distribution to $v_2 U_3$. Continue this way to conclude that $X(1)$ is equal in distribution to $U_1+U_1U_2+U_1U_2U_3+ \cdots$.

The fact that the GD$(\theta)$ distribution corresponds to a marginal distribution of a L\'evy process implies that it is infinitely divisible. In fact, if $X_1$ and $X_2$ are independent GD$(\theta_i)$, $i=1,2$, random variables, then $X_1+X_2$ is a GD$(\theta_1 + \theta_2)$ random variable. Moreover, the Laplace transform of $X \sim {\rm GD}(\theta)$ is given by $${\rm E}[e^{ - uX} ] = \exp \bigg(\int_0^1 {(e^{ - ux} - 1})\nu ({\rm d}x)\bigg) = \exp \bigg(\theta \int_0^1 {\frac{{e^{ - ux} - 1}}{x}\,{\rm d}x \bigg)} , \;\; u \geq 0.$$ The $k$th cumulant of $X$ is $\kappa_k = \theta/k$. Thus, in particular, ${\rm E}(X)=\kappa_1 = \theta$ and ${\rm Var}(X)=\kappa_2 = \theta/2$. There is also an elegant recursive formula for the $n$th moment.

The distribution function of $X$ is quite complicated and can be expressed as a sum of multiple integrals (to be elaborated in another answer). In particular, the probability density function for the case $\theta = 1$ is given by $e^{-\gamma}\rho(x)$, where $\rho$ is the well-known Dickman function.

-
Could you provide a reference for the Dickman distribution? – user4143 Mar 31 '11 at 23:27
Apparently, most of the relevant articles require subscription. I'll give an elaborated answer later on. – Shai Covo Mar 31 '11 at 23:39

For the second question, it is reasonable to see whether the standard example of a slowly converging sum will work. So put $$n^{-f(n)}=\frac{1}{n\log^2n}$$

That gives $$f(n)=\frac{\log(n\log^2n)}{\log n}$$

This $f$ behaves like you wanted it to. (We need to change $f$ a little at the beginning to make it well-defined and $>1$.)

-

Hint for the first question: you could try to compute $E(x_i)$; to do this you could begin by computing $E(x_{i+1}|x_i)$ then use what some call the tower property of conditional expectations.

Hint for the second question: if you can manage to get $n^{-f(n)}$ to be the general term of a series which just converges, for example $n^{-f(n)}=1/(n(\log n)^2)$, you might be done; to be sure, you would have to check that $f(n)\to1$.

-