What does $\tilde{O}_P(N^\alpha)$ mean? It appears in an estimation error mention in this paper, in the second paragraph on page 3.

What does big O subscript P mean in a probability context?


Pulled from: http://www2.math.uu.se/~svante/papers/sjN6.pdf (definition D5).

A probabilistic version of $\mathcal{O}$ that is frequently used is the following:

$X_n = O_\text{P}(\alpha_n)$ if for every $\epsilon > 0$ there exists constants $C_{\epsilon}$ and $n_{\epsilon}$ such that $\mathbb{P}(|X_n| \leq C_{\epsilon}\alpha_n) > 1 − \epsilon$ for every $n \geq n_{\epsilon}$. In other words, $X_n/\alpha_n$ is bounded, up to an exceptional event of arbitrarily small (but fixed) positive probability. This is also known as $X_n/\alpha_n$ being bounded in probability.

So combining this and D.W.'s answer we get:

$X_n \in \tilde{O}_{\text{P}}(\alpha_n)$ means for every $\epsilon > 0$ there exists constants $C_\epsilon$ and $n_{\epsilon}$ such that $\mathbb{P}(|X_n| \leq C_{\epsilon}\alpha_n n^{\gamma}) > 1 - \epsilon$ for every $n \geq n_{\epsilon}$ and for all $\gamma > 0$.

An looser terms $X_n \in \tilde{O}_{\text{P}}(\alpha_n)$ means $X_n$ is bounded by $\alpha_n$ within a polynomial factor with high probability.

  • $\begingroup$ I think this is a clear and correct answer, thanks! $\endgroup$ – luw Apr 27 '19 at 22:29
  • $\begingroup$ @luw cool, I also combined this info with $\tilde{O}$ from D.W.'s answer to make it more complete. $\endgroup$ – ryan Apr 27 '19 at 22:34

It depends on context; often, saying $f(n) \in \tilde{O}(g(n))$ means $f(n) \in O(g(n) n^{\epsilon})$ for all $\epsilon>0$. For example, $n^2 \log n \in \tilde{O}(n^2)$.

  • $\begingroup$ Any idea what the subscript $P$ could mean? $\endgroup$ – Discrete lizard Apr 27 '19 at 17:50
  • $\begingroup$ @Discretelizard, no clue. $\endgroup$ – D.W. Apr 27 '19 at 18:13
  • $\begingroup$ @Discretelizard could it possibly mean Polynomial? Then you have $f(n) \in \tilde{O}_P(g(n))$ means $f(n) \in O(g(n) \cdot \text{poly}(n))$ ? $\endgroup$ – ryan Apr 27 '19 at 19:30
  • $\begingroup$ @ryan I doubt it, just the tilde is already widely used to ignore polynomial factors. Judging from the context in the paper, I suspect it has something to do with probability. $\endgroup$ – Discrete lizard Apr 27 '19 at 19:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.