I have met the sentence that something will happen "with all but negligible probability" in the paper "Homomorphic Signatures for Polynomial Functions". However, I cannot quite figure out what exactly they mean by this. I know the definition of something happening with negligible probability, it is the "all but" that throws me off. In the paper they are referencing, it is described that it happens with probability $1-2^{-\Omega(n)}$, so I figure this must be the definition of it happening with all but negligible probability? However, I do not know what they mean by $\Omega(n)$, and I cannot seem to find the definition in the paper. Can someone perhaps clean things up for me?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
$\Omega(n)$ is a mathematical notation from the same family that the notation $O(n)$ comes from.
To review, $O(n)$ is bounded from above; that is, if we say that $f(n) = O(g(n))$, what we're actually saying is that, for all sufficiently large $n$, there exists a constant $c > 0$ such that $f(n) < c \cdot g(n)$, that is, $f(n)$ grows no faster than $g(n)$.
$\Omega(n)$ is the same, except that it is bounded from below; that is, if we say that $f(n) = \Omega(g(n))$, then (for all sufficiently large $n$) there exists a constant $c > 0$ such that $f(n) > c \cdot g(n)$, that is, $f(n)$ grows at least as fast as $g(n)$.
Hence, what they mean when they say $1 - 2^{-\Omega(n)}$, there's a constant $c$ such that the probability of success is always $> 1 - 2^{-cn}$ (except for possibly small $n$); hence, for large $n$, the probability is quite high (however, that doesn't say what "large" means in this context :-)
In case you're wondering, from the same family, we also have "little-oh" notation $f(n) = o(g(n))$ ("f grows strictly slower than g"), little-omega notation $f(n) = \omega(g(n))$ ("f grows strictly faster than g") and theta notation $f(n) = \Theta(g(n)))$ ("f grows as fast as g, within multiplicative upper and lower bounds")
-
$\begingroup$ Thank you for the thorough answer. I have learned about this notation at some point, but while I often use $\mathcal{O}(n)$, I don't think I've used $\Omega (n)$ since I learned about it, and I had all but forgotten it existed. $\endgroup$– MBrownFeb 20, 2017 at 7:59
$\begingroup$
$\endgroup$
In this instance, $\Omega(n)$ denotes any function that grows at least linearly with $n$. The symbol $\Omega$ is akin to the Big-$\mathcal O$ notation very commonly used to describe runtime bounds of algorithms: If you are familiar with that, the usual definition of $\Omega$ in computer science is that $f\in\Omega(g)$ if and only if $g\in\mathcal O(f)$.
"All but negligible probability" means that the probability is $1-p$, where $p$ is negligible. ("All probability" is $1$, since probabilities are never greater than $1$.) In other words: The complement of the considered event occurs with negligible probability.
