<p>Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon&gt;0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) &lt; \frac{\epsilon}{3}n$ or $\mathrm{deg}(v) &gt; \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.</p>

<p>Now consider a (seemingly) easier problem: under the same settings, decide whether $\mathrm{deg}(v) &lt; \epsilon^2 n$ or $\mathrm{deg}(v) &gt; \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) &lt; \epsilon^c n$ or $\mathrm{deg}(v) &gt; \epsilon n$ for $c$ as large as we want.</p>

<p>This is somewhat counter intuitive to me, as loosely speaking, if $\mathrm{deg}(v) &gt; \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) &lt; \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$.</p>

<p>Is it really the case that number of samples needed to decide whether $\mathrm{deg}(v) &lt; \epsilon^c n$ or $\mathrm{deg}(v) &gt; \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?</p>

CC BY-SA 3.0
2012-08-24T15:22:37.443Z
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
CC BY-SA 3.0
2012-08-24T18:27:12.513Z
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
CC BY-SA 3.0
2012-08-24T18:34:57.197Z
@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
CC BY-SA 3.0
2012-08-25T00:33:58.733Z
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
CC BY-SA 3.0
2014-03-18T10:46:35.810Z
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
CC BY-SA 3.0
2014-03-18T10:54:24.200Z
(The reason we don't need $O(1/\varepsilon^2)$ samples is that we can allow larger errors in the estimation when the degree is significantly larger than $\varepsilon n$.)
david
<ds.algorithms><graph-algorithms><machine-learning><pr.probability><property-testing>
Testing the degree of a vertex
Belle
# Testing the degree of a vertex

(Asked by: username_0 on 2012-08-24)

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?

**Tags:** ds.algorithms, graph-algorithms, machine-learning, pr.probability, property-testing
> **Comments:**
> **username_1**: 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.  
> **username_2**: The hidden constant in the $\Theta$ depends on $c$. The Chernoff bound isn't too far off the truth, look up Berry-Esseen.  
> **username_0**: @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  
> **username_3**: I think it's fine as is: we all have our own ways of processing it :), and Tsuyoshi's comment is sufficient to clarify.  
> **username_4**: 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.  
> **username_4**: (The reason we don't need $O(1/\varepsilon^2)$ samples is that we can allow larger errors in the estimation when the degree is significantly larger than $\varepsilon n$.)  

---

## 0 answers

