4
$\begingroup$

Let $n \in \mathbb{N}$, $x_1, \ldots, x_n \in (0,1)$ fix but arbitrary, s.t. $\sum_{i=1}^n x_i = 1$. Let $X_i \sim \operatorname{Unif}(\{x_1, \ldots, x_n\})$ i.i.d., and $T_n = \min\{t \in \mathbb{N} \, : \, \sum_{i=1}^t X_i \geq 1\}$.

I think there exists a constant $C$, which is independent of $n$, s.t. $$\mathbb{E}[T_n] \leq C \cdot n.$$

(At least, if we assume, that $x_1 \geq \frac{1}{2}$, then $C \leq 2$.)

My question is the following: What is the smallest possible $C$, s.t. the estimate holds? Do you know, if there is any work regarding this problem?

I could show, that in a special case $C \approx 1.36$, and I think it is the worst case, but couldn't prove it up to now.

Improve this question
$\endgroup$
3
  • $\begingroup$ Is your $\approx 1.36$ in fact $\int_0^\infty \frac{e^{-x}}{1-xe^{-x}} dx$? This is what I get in the limit with $n$ large, $\epsilon$ small, and $x_i=(1-\epsilon)\epsilon^{i-1}$. I also haven't seen anything bigger.... $\endgroup$
    – James Martin
    Commented May 18, 2015 at 21:58
  • $\begingroup$ The Lorden's inequality (a bound on the overshoot of Wald-type problems) looks relevant here: en.wikipedia.org/wiki/Lorden%27s_inequality $\endgroup$
    – Michael
    Commented May 19, 2015 at 1:18
  • $\begingroup$ @James Martin: The exact value is $\frac{143}{108} + \sum_{i=3}^\infty \frac{i!}{(i+1)^{i+1}}$, but it seems to coincide with your integral. The idea to choose one large $x_1$ and exponential decreasing small $x_i$ is the same. $\endgroup$
    – Fisher
    Commented May 19, 2015 at 9:54

1 Answer 1

Reset to default
1
$\begingroup$

This looks like a "Wald equality" question. Define $Y=\sum_{i=1}^{T_n} X_i$. Then: \begin{align} 1 + x_{max} \geq Y =\sum_{i=1}^{\infty} X_i1\{T_n\geq i\}\\ \end{align} where $1\{T_n\geq i\}$ is an indicator function that is $1$ if $T_n\geq i$, and 0 else. Taking expectations of both sides gives: $$ 1 + x_{max} \geq \sum_{i=1}^{\infty} E[X_i]Pr[T_n\geq i] $$ where we used the fact that $X_i$ is independent of the event $\{T_n \geq i\}$. Using the fact that $E[X_i]=1/n$ for all $i$ gives: $$ 1 + x_{max} \geq (1/n)\sum_{i=1}^{\infty}Pr[T_n\geq i] = (1/n)E[T_n] $$ Thus $E[T_n] \leq (1+x_{max})n \leq 2n$.

So you can use $C=1+x_{max}$ if you have a bound on $x_{max}$, or you can use $C=2$ else.

The James Martin observation looks interesting if you only require the condition to hold for large $n$.

The Lorden inequality (link in comment above) shows that $E[T_n]/n \leq 1 + \frac{E[X^2]}{E[X]}$. However, intuitively I would expect the overshoot for large $n$ to be $\approx \frac{E[X^2]}{2E[X]}$, which can be arbitrarily close to $1/2$ (so $C \approx 1.5$) by choosing $\{x_1, \ldots, x_n\} = \{\epsilon, \ldots, \epsilon, 1-(n-1)\epsilon\}$. [See comment below by James Martin on why this conjecture is not correct due to the threshold "1" being too small]

Improve this answer
$\endgroup$
9
  • $\begingroup$ Since we require, that $x_i \in (0,1)$, and that the sum of the $x_i$ is equal to $1$, $n$ must be at least $2$. I'm not sure about your reasoning, that we could achieve $C$ to be $3/2$. If you use just one $\epsilon$ to define the $x_i$, a quick Monte-Carlo simulation suggests a bound of $\approx 1.2$ in this case. I think, we have to choose the $x_i$ in a way James Martin did (but at the moment it's just a suggestion). Your suggestion about Lorden's inequality seems to be very useful. I wait another one or two days, and then I will accept your answer. Thank you very much. $\endgroup$
    – Fisher
    Commented May 19, 2015 at 10:05
  • $\begingroup$ I didn't notice that about $n=1$ not adding to 1. So my example for $n=1$ does not make sense. I will remove that example. $\endgroup$
    – Michael
    Commented May 19, 2015 at 16:50
  • $\begingroup$ The value $E[X^2]/(2E[X])$ is the standard formula for average residual time we observe at a random time in a system with back-to-back renewal intervals. Try your monte-carlo for large $n$ and the case $(x_1,\ldots,x_{n-1},x_n) = (\epsilon_n, \ldots, \epsilon_n, 1-(n-1)\epsilon_n)$ for $\epsilon_n = 1/(n-1)^3$. This should give: $$\frac{E[X^2]}{2E[X]} = \frac{1}{2} - \frac{1}{(n-1)^2}+\frac{1}{2(n-1)^4}+\frac{1}{2(n-1)^5} \approx \frac{1}{2}$$. So I expect for large $n$ you will find $C \approx 1.5$. $\endgroup$
    – Michael
    Commented May 19, 2015 at 16:56
  • 3
    $\begingroup$ @Michael: no, it's really not as big as that. Consider at step $m$ whether you have exceeded 1. If $m<n$, then to exceed 1 you must have chosen the large value at least twice. If $m>n$, then you should have chosen the large value at least once. Let $n$ be large; then at time $m=xn$, the number of times you have chosen the large number has distribution approximately Poisson($x$). From this you get $P(T_n/n>x)\approx(1+x)e^{-x}$ for $x<1$ and $P(T_n/n>x)\approx e^{-x}$ for $x>1$. Then $E(T_n/n)=\int_0^\infty P(T_n/n>x)dx\approx\int_0^1 xe^{-x}dx+\int_0^\infty e^{-x}dx=2(1-e^{-1}) = 1.26424...$ $\endgroup$
    – James Martin
    Commented May 19, 2015 at 17:43
  • 2
    $\begingroup$ I haven't thought much, but I believe the problem with your heuristic is the phrase "at a random time". Starting from 0, the distribution of the overshoot past 1 is rather different from the distribution of the overshoot past a "typical point", because 1 is rather close to 0. That is perhaps what makes the question interesting! $\endgroup$
    – James Martin
    Commented May 19, 2015 at 17:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .