# Testing the degree of a vertex

Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or $\mathrm{deg}(v) > \frac{\epsilon}{2}n$. A simple uniform sampling of edges between $v$ and the other vertices, together with the Chernoff bound, tells us that we need $\Theta\left(1 / \epsilon^2 \right)$ samples in order to decide with high probability which is the case.

Now consider a (seemingly) easier problem: under the same settings, decide whether $\mathrm{deg}(v) < \epsilon^2 n$ or $\mathrm{deg}(v) > \epsilon n$. Again the Chernoff bound tells us that we need $\Theta\left(1 / \epsilon^2 \right)$ samples in order to decide with high probability which is the case. Same goes for deciding whether $\mathrm{deg}(v) < \epsilon^c n$ or $\mathrm{deg}(v) > \epsilon n$ for $c$ as large as we want.

This is somewhat counter intuitive to me, as loosely speaking, if $\mathrm{deg}(v) > \epsilon n$, and we sample $\Theta(1/\epsilon)$ edges, we can expect to catch at least one edge with a constant probability - as opposed to the case that $\mathrm{deg}(v) < \epsilon^2 n$, wherein if we only sample $\Theta(1/\epsilon)$ edges, we can expect to catch at least one edge with a probability that is proportional to $\epsilon$.

Is it really the case that number of samples needed to decide whether $\mathrm{deg}(v) < \epsilon^c n$ or $\mathrm{deg}(v) > \epsilon n$ is asymptotically the same for every $c$, or is there a stronger concentration of measure bound that shows we can use less than $\Theta\left(1 / \epsilon^2 \right)$ samples?

• How is your graph given? Adjacency matrix? If so, this question is about approximately counting the number of 1s in a list of 0s and 1s, and it seems to me that stating the question in terms of a graph is a distraction. – Tsuyoshi Ito Aug 24 '12 at 15:22
• The hidden constant in the $\Theta$ depends on $c$. The Chernoff bound isn't too far off the truth, look up Berry-Esseen. – Yuval Filmus Aug 24 '12 at 18:27
• @TsuyoshiIto Yes, it is given as an adjacency matrix. I stated it as a graph problem, because this is the context it appears in the research problem I tackle. However, if people feel I should restate it in a cleaner settings - I'll be happy to oblige – Belle Aug 24 '12 at 18:34
• I think it's fine as is: we all have our own ways of processing it :), and Tsuyoshi's comment is sufficient to clarify. – Suresh Venkat Aug 25 '12 at 0:33
• I don't understand the question as it seems that the first case can be solved with $O(1/\varepsilon)$ samples. The Chernoff bound tells us that $O(1/\varepsilon^2)$ samples suffice to estimate the degree up to $\varepsilon n$ additive error, but that is stronger than required. In fact it also tells us that with $O(1/\varepsilon)$ samples, the degree estimation will be less than $0.4 \varepsilon n$ in the first case, and more than $0.45 \varepsilon n$ in the second case, which allows to distinguish the two. – david Mar 18 '14 at 10:46