Assume we randomly take $M$ integers $t_1 \le t_2 \le \dots \le t_M$ from the set of integers $\{ 1, 2, \dots, T \}$ such that $t_M = T$. We further denote $t_0 = 1$ for convention. For each $s \in [1,T]$, denote the smallest $t_i \ge s$ as $\tilde{t}(s)$. Note that $\tilde{t}(s)$ is a random variable for each $s$ because it depends on $t_i$. It is easy to show that $$ \sup_{s \in [1,T]} E[\tilde{t}(s) - s] \ge C_1 \frac{T}{M} $$ where the expectation is taken over the randomness of $t_i$ and $C_1$ is a positive constant independent of$M$ and $T$.

For example, let's take the uniform probability distribution $P$ over $[1,T]$ and consider $\int_{s \in [1,T]} E[\tilde{t}(s) - s] dP(s)$. We have \begin{align*} \int_{s \in [1,T]} E_{t_i}[\tilde{t}(s) - s] dP(s) &= E_{t_i}[ \int_{s \in [1,T]}(\tilde{t}(s) - s) dP(s)] \\ &= E_{t_i}[ \frac{1}{T} \sum_{i=1}^M \frac{(t_i - t_{i-1})^2}{2}]\\ &\ge E_{t_i}[ \frac{1}{T} \sum_{i=1}^M \frac{(T/M)^2}{2}] \quad (*)\\ &= \frac{1}{2} \frac{T}{M} \end{align*} The inequality $(*)$ comes from the fact that $\sum_{i=1}^M (t_i - t_{i-1})^2 $ is minimized when $t_M - t_{M-1}=t_{M-1} - t_{M-2}=t_{M-2} - t_{M-3}= \dots =t_2 - t_1 = \frac{T}{M}$.

Since $\sup_s E[\tilde{t}(s) - s] \ge \int E[\tilde{t}(s) - s] dP(s)$, the integral inequality proves the desired proposition.

I would like to prove the productive version of the previous proposition. The setting of $t_i$ and $\tilde{t}(s)$ stays the same. I want to prove that $$ \sup_{s \in [1,T]} E[\frac{\tilde{t}(s)}{s}] \ge C_2 T^{\frac{1}{M}}$$ where the expectation is taken over the randomness of $t_i$ and $C_2$ is a positive constant independent of$M$ and $T$.

These two propositons have similar structures. The difference is that the first proposition is additive while the second(unproved) proposition is productive. However, the integral argument for the first proposition fails on the second proposition, and I cannot figure out how to prove the second proposion.

Could you please help me? Suggestions or possible references are welcome!

  • $\begingroup$ What do you mean by "randomly take $M$ integers $t_1 \le t_2 \le \dots \le t_M$"? What is the joint distribution of $t_1 , t_2,\dots , t_M$? Are $t_1 , t_2,\dots , t_M$ the order statistics for an iid sample $(X_1,\dots,X_M)$ from the uniform distribution on $\{1,\dots,M\}$? $\endgroup$ Jun 9, 2022 at 17:47
  • $\begingroup$ @IosifPinelis Thanks for comment. By "randomly take $M$ integers", I mean that these $M$ integers are not deterministic but randomized. The specific distribution of these intergers is arbitrary. In other words, I want to prove those two propositions for all possible distributions. I make the randomness assumption because the proposition is trivial if these $t_i$ are deterministic, since there must be an $i$ s.t. $\frac{t_i}{t_{i-1}} \ge T^{\frac{1}{M}}$ $\endgroup$ Jun 9, 2022 at 18:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.