7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Aug 24 '12 at 15:22
  • 2
    $\begingroup$ The hidden constant in the $\Theta$ depends on $c$. The Chernoff bound isn't too far off the truth, look up Berry-Esseen. $\endgroup$ – Yuval Filmus Aug 24 '12 at 18:27
  • $\begingroup$ @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 $\endgroup$ – Belle Aug 24 '12 at 18:34
  • 2
    $\begingroup$ I think it's fine as is: we all have our own ways of processing it :), and Tsuyoshi's comment is sufficient to clarify. $\endgroup$ – Suresh Venkat Aug 25 '12 at 0:33
  • $\begingroup$ 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. $\endgroup$ – david Mar 18 '14 at 10:46

Your Answer

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

Browse other questions tagged or ask your own question.