2
$\begingroup$

There are several threads on this topic including:

How is an epsilon of 1/1000 non-negligible?

How to calculate if probability is negligible or not

(and others)

but I do not fully understand the answers in those threads.

My question is:

I would like to see what the definition of negligible & non-negligible means in an intuitive sense and unpack the definitions and use an example to see how the definitions apply.

The definition I am using is:

$\epsilon$ is a function $\epsilon$: $Z^{+}$ $\rightarrow$ $R^{+}$ and

$\epsilon$ is non-neg: $\exists$d: $\epsilon$($\lambda$) $\geq$ 1/$\lambda^{d}$ inf often ($\epsilon$ $\geq$ 1/polynomials, for many $\lambda$)

$\epsilon$ is neg: $\forall$d, $\lambda \geq \lambda_{d}$: $\epsilon$($\lambda$) $\leq$ 1/$\lambda^{d}$ inf often ($\epsilon$ $\leq$ 1/polynomials, for large $\lambda$)

Several questions:

  1. What do these definitions mean in an "intuitive" sense?
  2. What does $\epsilon$, $\lambda$, d, $\lambda^d$ mean?
  3. How can you use these definitions to show that $\epsilon$:($\lambda$)=1/$2^{\lambda}$ is negligible and $\epsilon$($\lambda$)=1/$\lambda^{1000}$ is non-negligible?

(I know one of these examples is shown in another thread but I do not understand their solution and I want to see what each piece in the definition means in 'english' and then see how the definition is applied to each of these examples to show that they are negligible and non-negligible. I am hoping someone can provide a fresh explanation to the definitions and show how the definitions are applied to these problems and problems in general.)

Thanks!

$\endgroup$
  • $\begingroup$ intuitively: a function is negligible if it approaches 0 zero "faster" than any polynomial ever could (exponential functions do this). $\endgroup$ – SEJPM Aug 14 '16 at 9:39
  • $\begingroup$ The terms negligible and non-negligible is probably most often used about probabilities. In this setting the simple intuition is that a negligible event means that the event will not happen (given the right parameters). A non-negligible event is then an event that might happen. If you think about what the English word "negligible" really means, it actually makes pretty good sense. $\endgroup$ – Guut Boy Aug 15 '16 at 12:25
1
$\begingroup$

As @SEJPEM mentioned in the comment: intuitively, for every positive polynomial $p(n)$ ($n\in\mathbb{N}$) that you take, consider the function $q(n)=\frac{1}{p(n)}$, then we say that the function $\epsilon(n)$ is negligible if from some point $N\in\mathbb{N}$ it follows that $\epsilon(n)<q(n)$. This means that $\epsilon(n)$ reaches 0 very fast because it doesn't matter whether you take $p_1(n)=n$ or $p_2(n)=n^{100000}$, by the definition there would be $N_1$ from which $\epsilon(n)<\frac{1}{n}$ and $N_2$ from which $\epsilon(n)<\frac{1}{n^{100000}}$.

Now, to interpret the definition that you copied: $\lambda_d\in\mathbb{N}$ refers to $N$ in my explanation above, then the definition of negligible function requires that for every $\lambda\in\mathbb{N}$ such that $\lambda>\lambda_d$ (in my explanation above: for all $n$ that is bigger than this $N$) it follows that $\epsilon(\lambda)<q_d(\lambda)=\frac{1}{p_d(\lambda)}=\lambda^d$.

In order to show that $\epsilon(\lambda)=\frac{1}{2^\lambda}$ is negligible you need to show that for every polynomial $p(\lambda)$ it follows that $\epsilon(\lambda)=\frac{1}{2^\lambda}<q(\lambda)=\frac{1}{p(\lambda)}$ from some point $N\in\mathbb{N}$ (this point could be different for different $p(\lambda)$-s. Now take some arbitrary $p(\lambda)$, we can discover this $N$ from which $\epsilon(\lambda)<\frac{1}{p(\lambda)}$ as follows: let $p(\lambda)=\lambda^k$ then we want to find $\lambda$ such that $\frac{1}{2^\lambda}<\frac{1}{\lambda^k}$, thus, we want to find $\lambda$ such that $\lambda^k<2^\lambda$, or in other words, we want to prove that from some $\lambda$ the term $2^\lambda$ is bigger than $\lambda^k$, and this can be proven using the definition of a limit (see this proof).

Now take $\epsilon(\lambda)=\frac{1}{\lambda^{1000}}$, in order to show that it is not negligible you need to show that there exists some polynomial $p(\lambda)$ that violates the definition. Take the polynomial $p(\lambda)=\lambda^{2000}$, there exist no $\lambda_{2000}$ (or $N$) from which $\epsilon(\lambda)=\frac{1}{\lambda^{1000}} < q(\lambda)=\frac{1}{p(\lambda)}=\frac{1}{\lambda^{2000}}$ (i.e. for every $\lambda\in\mathbb{N}$ that you take, it follows that $\epsilon(\lambda)>\frac{1}{p(\lambda)}$.

I hope that it helps.

$\endgroup$
  • $\begingroup$ Thanks for your excellent reply. I now have an "intuitive" understanding what negl and non-negl. function is (I get the spirit of the def), but I'm still struggling to understand what $\lambda$ represents. Is $\lambda$ a polynomial? Can you write out an explicit $\lambda$ so I can better understand the definition of negl fn (i.e. can you write the definition of negl fn with an explicit $\lambda$ , degree d etc).-- this would help me immensely. Basically, I need to see the definition spelled out with a specific explicit example using an actual $\lambda$ and degree. Thanks so much! $\endgroup$ – Max Aug 15 '16 at 15:13
  • $\begingroup$ $\lambda$ is not a polynomial, it is an integer. Consider some function $\epsilon(\lambda)$, and take some polynomial $p(\lambda)$, if there exist some integer $\lambda_d$ such that for every $\lambda>\lambda_d$ that you would take it follows that $\epsilon(\lambda)<1/p(\lambda)$ and this will be true for every polynomial $p$ that you would take, then the function is negligible. $\endgroup$ – Bush Aug 17 '16 at 12:34
  • $\begingroup$ Take for example the negligible function $\epsilon(\lambda)=1/2^\lambda$. Consider some polynomial $p(\lambda)$, if I want to prove that $\epsilon(\lambda)$ is negligible then I need to find $\lambda_d$ such that for every $\lambda>\lambda_d$ it holds that $\epsilon(\lambda)=1/2^\lambda<1/p(\lambda )$. For example if you take $p(\lambda)= \lambda $ then the question is: Is there some $\lambda_d\in\mathbb{N}$ such that for every $\lambda>\lambda_d$ it follows that $1/2^\lambda<1/ \lambda $? and the answer is that if you take $\lambda_d=1$ than it is indeed works! $\endgroup$ – Bush Aug 17 '16 at 12:43
  • $\begingroup$ Now, every polynomial $p(\lambda)$ that you take might give you a different $\lambda_d$, this is fine since the definition requires that this $\lambda_d$ is exists per polynomial. And not the same $\lambda_d$ for all polynomials. $\endgroup$ – Bush Aug 17 '16 at 12:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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