What does $O(T^{-\eta})$ mean?

Question

Let $\hat{\theta}$ be an estimator of a true parameter $\theta$. I am confused with the following (simplified) statement in a paper: $$\Pr(\lVert\hat{\theta} - \theta\rVert \leq \kappa) \geq 1 - O(T^{-\eta}),$$ where $\eta > 0$.

So how do I reed it? My guess is that as $T\to \infty$ we have that $T^{-\eta} \to 0$ and we should consider that $O(T^{-\eta})$ tends to zero. Then, I would read it as follows: as $T$ goes to infinity, the probability that difference between the estimator and the true parameter is less than any positive constant $\kappa$ goes to one.

Confusion arises also form the fact that I am not sure what $O(\cdot)$ means. Is it in terms of algorithm complexity or convergence of a sequence. So I mainly look for explanation of $O(T^{-\eta})$ term.

Answer 1

As a disclaimer: I didn't have time to read the paper carefully, but the authors seem to be simply using the big O notation, i.e.

$$ f(x) = O(g(x)) $$

if there exists some coinstant $M$ such that

$$ |f(x)| \le |Mg(x)| $$

so $O(\cdot)$ drops the constant(s) from the function. So the equation says that the difference between the probability and $1$ is proportional to $T^{-\eta}$.

Answer 2

This notation is used to simplify the exposition of results involving asymptotic behaviour.

It is indeed plain old Big O Notation, as found in complexity and convergence.

What it (most likely) means is that the result was proved for a lower bound of the form $$ 1-(cT^{-\eta}+S) $$ where $c$ is a constant and $S$ is a collection of lower-order terms. The problem is that $c$ and/or $S$ are perhaps ugly and would mar their presentation.

Precisely because they are lower-order, if there are $n$ such terms, for sufficiently large $T$ we can state $$ 1-(cT^{-\eta}+S) \geq 1-\left((c+n)T^{-\eta}\right) $$ And by definition, $(c+n)T^{-\eta} = O(T^{-\eta})$ as $T\rightarrow \infty$ (and of course so does the smaller function $cT^{-\eta}+S$).

To sum up, they cannot write $$ p\geq 1-T^{-\eta} $$ as that is a presumably better bound than what was actually proved. So

$$ p\geq 1-O(T^{-\eta}) $$ allows them to get away with an almost equally neat result.

Answer 3

That's the Big O notation.

You are correct with your interpretation.

$O(T^{-\eta})$ can be any function $f(T)$ such that for sufficiently large values of $T$,

$|f(T)| \leq M T^{-\eta}$,

for a certain constant $M$. So, yes: for large values of $T$,

$1 - O(T^{-\eta})$ will tend to 1.