Timeline for Upper bound of the waiting time of a sum process
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 22, 2015 at 12:16 | vote | accept | Fisher | ||
| May 19, 2015 at 21:10 | comment | added | Michael | I should have said "(worst) over all $(x_1,x_2)$." Sorry. | |
| May 19, 2015 at 21:01 | comment | added | Fisher | Some banal objection, perhaps I missunderstand the "regardless of": If we choose $(\epsilon, 1 - \epsilon)$, then $C$ tends to $\frac{5}{4}$ (which should be maximal), for sufficiently small $\epsilon$, but if you choose $(1/2, 1/2)$, then $C$ could be obviously chosen to be $1$. But I observed the overshoot $1/2$ in a related problem, so nevertheless this was very helpful. | |
| May 19, 2015 at 20:28 | comment | added | Michael | For $n=2$ it seems that the expected overshoot is $0.25$ regardless of $(x_1,x_2)$. | |
| May 19, 2015 at 20:14 | history | edited | Michael | CC BY-SA 3.0 |
added 115 characters in body
|
| May 19, 2015 at 19:38 | comment | added | Michael | Oh I see, 1 is only far from 0 when we restrict to $x_i$ values that are themselves much smaller than $1$, whereas in my extremal distribution I was maximizing $E[X^2]/(2E[X])$ but that has an extreme $x_n$ value that is almost the full threshold itself. So if the threshold "1" was changed to something much larger than 1, the $E[X^2]/(2E[X])$ would come into play. | |
| May 19, 2015 at 17:45 | comment | added | James Martin | 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! | |
| May 19, 2015 at 17:43 | comment | added | James Martin | @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...$ | |
| May 19, 2015 at 16:56 | comment | added | Michael | 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$. | |
| May 19, 2015 at 16:51 | history | edited | Michael | CC BY-SA 3.0 |
I removed the example $n=1$, $x_1=1-\epsilon$, since indeed that does not sum to 1!
|
| May 19, 2015 at 16:50 | comment | added | Michael | 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. | |
| May 19, 2015 at 10:05 | comment | added | Fisher | 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. | |
| May 19, 2015 at 1:53 | history | edited | Michael | CC BY-SA 3.0 |
added 353 characters in body
|
| May 19, 2015 at 1:33 | history | edited | Michael | CC BY-SA 3.0 |
added 303 characters in body
|
| May 19, 2015 at 1:12 | review | First posts | |||
| May 19, 2015 at 2:47 | |||||
| May 19, 2015 at 1:11 | history | answered | Michael | CC BY-SA 3.0 |