I'm studying a paper where the authors stated preliminarily:

$$\mid R_{i,T}\mid \leq \frac{C \theta_0}{K(i_\theta,\theta,T)}, \forall i\in\{1,\dotsc,\theta^x\}$$

where $C$ is a finite contant; $\theta_0$ a positive integer; $R_{i,T}:=R(i,T)$; and $i_\theta=i-\theta\left \lfloor{\frac{i-1}{\theta}}\right \rfloor $ ; and $\theta^x$ is the least common multiple of $\theta$ and $\theta_0$; and $\theta \in \{1,\dotsc,\Theta_T\}$ integer. Note that $i_\theta \in \{1,\dotsc,\theta\}$. However, it was given that $K(i_\theta,\theta,T)=\left \lfloor{\frac{T-i_\theta}{\theta}}\right \rfloor +1$, which implies that this function can only be either $\left \lfloor{\frac{T}{\theta}}\right \rfloor$ or $\left \lfloor{\frac{T}{\theta}}\right \rfloor +1$. It also implies that $K(i_\theta,\theta,T)=O\big(\frac{T}{\theta}\big)$. Untill here it was everything fine to me. But, from this, they claimed that:

$$\mid R_{i,T}\mid \leq \frac{C\Theta_T}{T}, \forall i\in\{1,\dotsc,\theta^x\}$$

Is it right?

It is true that $\frac{C \theta_0}{K(i_\theta,\theta,T)}\leq \frac{C}{\left \lfloor{\frac{T}{\theta}}\right \rfloor}$. On one hand, $\frac{C}{\left \lfloor{\frac{T}{\theta}}\right \rfloor} \geq \frac{C}{\frac{T}{\theta}}$ (and then cannot be used), on the other, $\frac{C}{\frac{T}{\theta}} \leq\frac{C\Theta_T}{T}$. How they simply dropped the floor function and stablished the that upper bound? Even asymptotically, I don't see that $\frac{C}{\left \lfloor{\frac{T}{\theta}}\right \rfloor} = \frac{C}{\frac{T}{\theta}}$ does hold.

The asymptotics here respects $T \rightarrow \infty$, $\Theta_T \rightarrow \infty$ at a slower rate than $T$ (implying $\mid R_{i,T}\mid \rightarrow 0$).

Reference: Proof of 'lemma a.4'

Thanks in advance!

  • $\begingroup$ With no restriction on $\theta_0$, you have no bound at all. Did you copy this correctly? $\endgroup$ – Matt Samuel May 24 at 13:45
  • $\begingroup$ In my view, $\theta_0$ is a parameter (constant). If I put $\theta_0 \in \{1,...,\Theta_T\}$, does it help anything? I will try to link the paper here. $\endgroup$ – Danmat May 24 at 14:02
  • $\begingroup$ If it's constant and it is absorbed into $C$, then sure it holds. $\left\lfloor \frac T{\theta}\right \rfloor$ differs from $\frac T{\theta} $ by at most $1$, so certainly it is asymptotically equal. $\endgroup$ – Matt Samuel May 24 at 14:08
  • $\begingroup$ @MattSamuel Yes! I know it, $\frac{T}{ \theta}-1<{\left \lfloor{\frac{T}{\theta}}\right \rfloor} \leq \frac{T}{ \theta}$. But there is no guarantee that $ \mid R_{i,T}\mid \leq \frac{C \theta}{T}$ from the first inequality. This is the problem. I can just guarantee that $\mid R_{i,T}\mid \leq \frac{C}{{\left \lfloor{\frac{T}{\theta}}\right \rfloor}}$ $\endgroup$ – Danmat May 24 at 14:31
  • $\begingroup$ @MattSamuel If $\theta$ happen to be $\Theta_T$, clearly, the first inequality shows that $\mid R_{i,T}\mid$ could be greater than $\frac{C \theta}{T}$. $\endgroup$ – Danmat May 24 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.