debugMinor
What does $\tilde{O}_P(N^\alpha)$ mean?
Viewed 0 times
alphawhatmeantildedoes
Problem
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?
What does big O subscript P mean in a probability context?
Solution
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.
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.
Context
StackExchange Computer Science Q#108615, answer score: 4
Revisions (0)
No revisions yet.