On average, how many uniformly random real numbers $u$ are needed for their sum to exceed $1$, if $u_1$ is in $(0,1)$ and $u_k$ is in $(0,eu_{k-1})$?

Question

A well-known question is: on average, how many uniformly random real numbers in $(0,1)$ are needed for their sum to exceed $1$? The answer is $e$.

Let's tweak this question by making each random number $u_k$, after the first, to be in $(0,eu_{k-1})$.

On average, how many uniformly random real numbers $u$ are needed for their sum to exceed $1$, if $u_1$ is in $(0,1)$ and $u_k$ is in $(0,eu_{k-1})$?

Why $e$? Because anything less than $e$ would make the expectation to be infinite, and anything greater than $e$ would make the expectation to be finite (EDIT: Sangchul Lee's answer below justifies this statement). But with $e$, I do not know what the expectation would be.

(Here is a more general version of this question on Math SE, currently unanswered.)

Answer 1

I am not quite sure if the previous long discussion has already resulted in a full proof of anything but here is the crude bound that shows that the expectation in question is infinite.

Let $X_i$ be iid with uniform distribution on $[0,e]$ each and let $Y_i=\log X_i$, so $EY_i=0$, $E[Y_i^2]=\sigma^2$ and $E|Y_i|^3=\rho$ for some $\sigma,\rho>0$. The question is equivalent to asking what is the expectation of the minimal $N$ such that $X_1+X_1X_2+\dots+X_1\dots X_N\ge 1$. We shall estimate from below the probability $p_n$ that $N>n$, i.e., that $X_1+X_1X_2+\dots+X_1\dots X_n< 1$. To show that $EN=+\infty$, it is sufficient (and necessary) to show that $\sum_n p_n=+\infty$.

We now consider the random walk with steps $Y_i$ and prove a few things about it. Our main tool will be the Berry-Esseen bound that in this case says that for every $t>0$ $$ |P(\sum_{i=1}^m Y_i>t\sigma\sqrt m)-\Phi(t)|\le Cm^{-1/2} $$ where $C=C(\sigma,\rho)$ and $\Phi(t)$ is the tail of the normal distribution.

Our first conclusion from here is that there exist an absolute $C_1>0$ such that $P(\max_{k\le m}(Y_1+\dots+Y_k)\le C_1)\ge m^{-1/2}$ for large enough $m$ (just like for the symmetric random walk or the Brownian motion).

The proof is the same using quasi-symmetry instead of symmetry. Consider the sum $S=\sum_{i=0}^{2m}Y_i$. The probability that $S>0$ is at most $\frac 12+Cm^{-1/2}$ (Berry-Esseen with $t=0$). On the other hand, if $k\le m$ is the first index with the sum up to $k$ exceeding $C_1$, then the conditional probability that the remaining sum of $2m-k$ terms is $-C_1$ or more is at least $\Phi(-C_1\sigma^{-1}(2m)^{-1})-Cm^{-1/2}$, which is at least $\frac 12+C_1(8\sigma)^{-1}m^{-1/2}$ if $C_1$ is much bigger than $C\sigma$ and $m$ is large enough. Thus the probability of the event that the maximum is large is at most the ratio of $\frac 12+Cm^{-1/2}$ and $\frac 12+C_1(8\sigma)^{-1}m^{-1/2}$, which is less than $1-m^{-1/2}$ for large $m$ and we are done.

The next claim is similar but a bit more complicated. We want to show that the above probability won't change significantly if we impose the additional condition that $\sum_{i=1}^mY_i\le -\sigma\sqrt{m}$. Note that the unconditional probability of that event is approximately $\Phi(1)$. We want to show that conditioning upon the event that we don't go up too much is not going to diminish it drastically. To this end, we want to argue that for each $k$ as above $$ P(\sum_{i=k+1}^m Y_i\le -\sigma\sqrt{m}-C_1)\le P(\sum_{i=1}^mY_i\le -\sigma\sqrt{m})\,. $$ Then we shall conclude that the conditional probability that the full sum is large negative conditioned on the remaining event we are interested in should be at least the full probability to keep the balance.

We consider two cases. The first case is that $m-k<\delta m$ with fixed small $\delta>0$. In this case the Chebyshev bound immediately yields $$ P(\sum_{i=k+1}^m Y_i\le -\sigma\sqrt{m})\le \frac{m-k}{m}<\delta\ll \Phi(1) $$ and we are done.

Otherwise we have enough terms to use the normal approximation and to write $$ P(\sum_{i=k+1}^m Y_i\le -\sigma\sqrt{m}-C_1)\le P(\sum_{i=k+1}^m Y_i\le -\sigma\sqrt{m-k}-C_1) \\ \le\Phi(1+C_1\sigma^{-1}(m-k)^{-1/2})-C(m-k)^{-1/2}\le \Phi(1)-cC_1\sigma^{-1}m^{-1/2}\le \Phi(1)-Cm^{-1/2} $$ and we are done again, provided that $C_1$ was chosen large enough.

Now take huge $n$, large $K$ and not too small $Q$.

Consider that event that the first $Q$ values of $X_i$ are less than $1/4$, say. Then the sum of the first $Q$ products is $\le 1/3$ and the probability of this event is $e^{-CQ}$ with some absolute $C>0$. Moreover, $X_1\dots X_Q\le 4^{-Q}$. Consider now the event that the next $K$ values of $Y_i$ are such that their partial sums are below $C_1$ and the last sum is $\le -\sigma\sqrt K$. Then the sum of the corresponding products of $X$-s is at most $K4^{-Q}e^{C_1}$ and the probability of this event is $cK^{-1/2}$. Also $X_1\dots X_{K+Q}\le e^{-\sigma\sqrt K}$. Finally consider the event that the remaining $Y_i$ have partial sums at most $C_1$. Then the corresponding sum is $\le ne^{-\sigma\sqrt K}e^{C_1}$ and the probability is $n^{-1/2}$.

Thus, the full sum is at most $$ \frac 13+4^{-Q}Ke^{C_1}+e^{-\sigma\sqrt K}ne^{C_1}\,, $$ and the total probability is $$ e^{-CQ}cK^{-1/2}n^{-1/2}\,. $$ It remains to put $K=100\log^2n/\sigma^2$ and $Q=100\log\log n$, say.

Answer 2

We can try the method from the second answer to the first question you linked to. I originally thought that would clarify everything, but that was based on a miscalculation. I can now finally prove something (namely, that the integral equation for the expectation that I derive below has a finite solution for $c>e$), though this isn't very close to what the OP asked.

Let $X_j$ be iid and uniformly distributed on $[0,1]$, and $$ S_n = X_1 +cX_1X_2+ \ldots + c^{n-1} X_1X_2\cdots X_n . $$ Define $N(x)=\min\{ n\ge 1: S_n\ge x\}$ and $f(x)=EN(x)$. We are then interested in $f(1)$.

Notice that $S_n=X_1(1+cT_{n-1})$; here $T_{n-1}$ is independent of $X_1$ and has the same distribution as $S_{n-1}$. Condition on $X_1$: $$ E(N(x)|X_1=y)=\begin{cases} 1 & y\ge x\\ 1+ f((x-y)/(cy)) & y<x\end{cases} \quad\quad (1) $$ We then have $$ f(x) = \int_0^1 E(N(x)|X_1=y)\, dy , $$ and now (1) and a substitution yield $$ f(x) = 1 + cx \int_{\max \{ 0,(x-1)/c\} }^{\infty} \frac{f(t)}{(1+ct)^2}\, dt . \quad\quad (2) $$

We can prove that (2) has a solution $f(x)<\infty$ for $c>e$; as Iosif pointed out in a comment below, the significance of this is unclear.

We argue as follows: View (2) as an equation $f=1+Lf$ in the space $X=C^{b}_w([0,\infty))$, that is, functions $g=wh$ with $h$ bounded and continuous and with weight $w(x)=(1+cx)^{\alpha}$ and norm $\|g\|=\|h\|_{\infty}$. Then, for $x\ge 1$, \begin{align*} \frac{|(Lg)(x)|}{\|g\|_X} & \le \frac{cx}{(1+cx)^{\alpha}}\int_{(x-1)/c}^{\infty} (1+ct)^{\alpha-2}\, dt \\ & = \frac{x^{\alpha}}{(1-\alpha)(1+cx)^{\alpha}} \le \frac{1}{(1-\alpha)c^{\alpha}} . \end{align*} This can be made $<1$ for $c>e$ by taking $\alpha\to 0+$. A similar calculation works for $0\le x\le 1$. So if $c>e$, we are dealing with a contraction, and thus (2) has a solution satisfying $f(x)=O(x^{\alpha})$ for all $\alpha>0$, which we can find by iterating (2).

Answer 3

Here is a probabilistic argument for OP's statement, showing that the expectation is finite for $a>e$ and infinite for $a<e$.

Setting. Let $(\tau_k)_{k\geq 1}$ denote a sequence of i.i.d. $\text{Exp}(1)$ variables. Let $\mu=\log a$ so that $a = e^{\mu}$, and consider the sum

$$ S_n = \sum_{k=1}^{n} e^{(k-1)\mu - X_k}, \qquad X_k = \sum_{j=1}^{k} \tau_j. $$

Noting that $e^{-\tau_k}\sim\text{Uniform}(0,1)$, this is the same setting as in OP. Then we are interested in the expectation of the stopping time

$$ N(x) = \inf\{ n \geq 1 : S_n > x \}. $$

Case $a < e$. In this case, SLLN tells that

$$ \sqrt[k]{e^{(k-1)\mu - X_k}} \longrightarrow e^{\mu-1} < 1 \qquad\text{a.s.,} $$

hence $S_n$ converges a.s., say, to $S_{\infty}$. Then by noting that

$$ S_{\infty} = e^{-\tau_1}( 1 + e^{\mu} \tilde{S}_{\infty} ) $$

for some $\tilde{S}_{\infty} \stackrel{d}= S_{\infty}$ independent of $\tau_1$, it is easy to show that

\begin{align*} \mathbf{P}(N(1) = \infty) &= \mathbf{P}(S_{\infty}\leq 1) \\ &= \int_{0}^{\infty} e^{-t} \mathbf{P}\biggl(S_{\infty} \leq \frac{e^t - 1}{e^{\mu}} \Biggr) \, \mathrm{d}t > 0. \end{align*}

Therefore, $\mathbf{E}[N(1)] = \infty$.

Case $a > e$. In this case, $\mu > 1$. Define the stopping time $T$ by

$$ T = \inf\{k \geq 1: (k-1)\mu > X_k\}. $$

Then SLLN shows that $T$ is finite a.s. Also, since $S_T > 1$ holds, we have $N(1) \leq T$. Hence,

\begin{align*} \mathbf{P}(N(1) > n) &\leq \mathbf{P}(T > n) \\ &\leq \mathbf{P}((n-1)\mu \leq X_n). \end{align*}

Using $X_n \sim \text{Gamma}(n)$ and applying the Chernoff bound, we can show that the last line is further bounded by $e^{\mu-1-nI(\mu)}$, where $I(\mu)=\mu-1-\log\mu>0$.¹⁾ Consequently,

$$ \mathbf{E}[N(1)] = \sum_{n=0}^{\infty} \mathbf{P}(N(1) > n) \leq e^{\mu-1}\sum_{n=0}^{\infty} e^{-nI(\mu)} < \infty. $$

---

Addendum. Here is a numerical simulation of $\mathbf{E}[N(1)]$ as a function of $\frac{1}{\mu-1}$, where $\mu = \log a$ and $a > e$, using $10^5$ samples:

This seems hinting that $\mathbf{E}[N(1)] \sim (\mu - 1)^{-1}$ as $\mu \to 1^+$ and hence $\mathbf{E}[N(1)] = \infty$ for $a = e$, although I have no idea how to justify this result.

---

^{1) My original bound was of the form $\mathcal{O}(e^{-\varepsilon\sqrt{n}})$, which was a consequence of CLT-like estimate. However, large deviation estimates gives better result. Thanks @Pierre PC for pointing this out!}

Answer 4

With Christian Remling's notation and $a=e$ let us sample $X_1, \dots, X_{300}$. An estimator of $p_n = \mathbf{P}(N(1) = n)$ might be the related frequency $\hat{p}_n$ we observe on the samples. It seems to stabilize soon enough at small $n$ as we increase the sampling size, and suggests $p_n$ behave like $n^{-1.55}$ at large $n$. As a consequence, the average stopping number $\sum kp_k$ the OP asks might be infinite, behaving as the divergent series $\sum k^{-0.55}$.

With $2\times 10^9$ samples (and 128-bit floating arithmetics) I got $$\hat{p}_2 \approx 0.516870$$ while the true value is $p_2 = 1 - \frac{\log(1+e)}{e} = 0.5168780242\dots$ $$\hat{p}_3 \approx 0.155932$$ while the true value $p_3$ $\dots$ is tedious to express. It involves $\log(1+e+e^2)$ and $\text{dilog}(e+e^2)$. $$\hat{p}_4 \approx 0.0745461$$ $$\hat{p}_5 \approx 0.0437586$$ $$\hat{p}_6 \approx 0.0288801$$ $$\hat{p}_7 \approx 0.0205670$$

With $10^8$ samples (and some scaling trick to hit $N(1)=300$ on every sample) I got

$\frac{\log(5\hat{p}_n)}{\log(n)}$ over $10^8$ samples for $n=2, 3, \dots, 300$ and the line $y=-1.55$" />

$\frac{\log(5\hat{p}_n)}{\log(n)}$ over $10^8$ samples for $n=25, 26, \dots, 300$ and the line $y=-1.55$" />

$\left(\frac{\hat{p}_{n+1}}{\hat{p}_n}-1\right)n$ over $10^8$ samples for $n=2, 3, \dots, 299$ and the line $y=-1.55$" />

Answer 5

The integral equation in Christian Remling's answer can be written:

$$\frac{f(x)-1}{x}=c \int_{\max\{0,(x-1)/c\}}^\infty \frac{f(t)}{(1+ct)^2}dt$$

Differentiating and then multiplying by $x^2$ gives

$$x f'(x)+1-f(x)=-f\left(\frac{x-1}{c}\right)\text{ for }x>1$$

This has a near-solution of $$f(x)\sim a + \frac{\log(x+\frac{1}{c-2})}{\log c - 1}\ \text{ for }c>e,\ x>1$$ in the sense that it makes the differential equation accurate to order $O(1/x^2)$, and that for $c<e$ the value of $f$ would be negative and not meaningful. We can also get more accuracy with more terms, e.g. $x+\frac{1}{c-2}+\frac{1}{2(c-2)^2(c^2-3)}x^{-1}$ for $O(1/x^3)$.

So the equation as a whole has a near-solution for $c>e$ of $$f(x)\sim 1+\Big(\!\min\{x,1\}\Big)\Big(a - 1 + \frac{\log(\max\{x,1\}+\frac{1}{c-2})}{\log c - 1}\Big)$$

At $x=1$, this gives $$f(1)=a+\frac{\log(1+\frac{1}{c-2})}{\log c -1}$$ which suggests that one additional boundary condition might be enough to give a nice approximate answer to the question.