<p>In general, it seems that you cannot get the concentration you want without  more constraints on the probabilities. </p>

<p>Consider the following graph on $n$ vertices. Let vertices $C = \{2,\ldots,n\}$ form a clique such that for all $i,j \in C$, $p_{ij} = 1$. Let vertex $1$ be connected to this clique via only one edge, with $p_{1,2} = 1/\log(n)$, and $p_{1,j} = 0$ for all $j \in C$ with $j \neq 2$. Then with probability $1/\log(n)$, all $n$ vertices are reachable from $1$ with 2 hops, and with probability $1 - 1/\log(n)$ none are. So the expected number of reachable vertices is $n/\log(n)$, but with probability $1/\log(n) \gg n^{-1}$, it is $n$, larger than its expectation by a $\log(n)$ factor. </p>

<p>In fact, since you are interested in paths of length $\log n$, all that we require is that the realized edges in $C$ form an expander, not a clique, with high probability. This can be accomplished with $p_{ij} = o(1)$ as well, so this condition does not save you. </p>

<p>The essence of the problem is this: since you can have a group of vertices $C$ that are highly connected with high probability, how many vertices vertex $1$ is connected to can depend only on whether it is connected to $C$ or not, which can depend on only a single edge. You can't expect something depending on only a single Bernouli random variable to be well concentrated. </p>

CC BY-SA 3.0
2013-11-22T08:49:02.090Z
Thank you for the example and explanation. I realized additional assumptions are needed on the sequence $\{p_{ij}\}$ for deriving concentration bounds.
fenrir
CC BY-SA 3.0
2013-09-25T12:45:00.737Z
2013-09-25T12:45:00.737Z
Aaron Roth
<p>Here's a heuristic argument to say that, if each vertex has an expected number of edges of at least $\Omega(\log d)$, then you can get such a bound, and furthermore it depends mainly on this expected number of edges per vertex (not much on $n$ or $d$). (<strong>Edit</strong>: As Aaron points out in comments, though, a bound for $H_d$ does not look like it will help us bound $Z_d$!) Let's write $H_d$ as</p>

<p>$H_d = \sum_{i_2\neq 1}X_{1i_2} \left(1 + \sum_{i_3 \neq 1} X_{i_2 i_3} \left(1 + \cdots \sum_{i_{d-2}\neq 1}X_{i_{d-2}i_{d-1}} \left(1 + \sum_{i_d \neq 1} X_{i_{d-1}i_d}\right)\cdots \right) \right)$.</p>

<p>Now use Chernoff from the inside and move outward. For each index $i_k$, let $\mu_k = \sum_{j \neq 0} p_{i_k j}$.</p>

<p>$\Pr\left[\sum_{i_d \neq 0} X_{i_{d-1}i_d} &gt; (1 + \delta)\mu_d\right] \leq \approx e^{-\delta^2 \mu_d}$. So replace this innermost sum with the constant $(1+\delta)\mu_d$ and add $e^{-\delta^2 \mu_d}$ onto the probability we need. Now expand outwards, adding the probabilities (union-bounding). For example, at the next step we say</p>

<p>$\Pr\left[\sum_{i_{d-1}\neq 0} X_{i_{d-2}i_{d-1}} \left(1 + (1+\delta)\mu_d\right) \geq (1+\delta)(\mu_{d-1} + (1+\delta)\mu_d)\right] \leq \approx e^{-\delta^2 \mu_{d-1}}$.</p>

<p>At the end we get</p>

<p>$\Pr\left[H_d &gt; (1+\delta)\mu_1 + (1+\delta)^2 \mu_1 \mu_2 + ~\cdots~ + (1+\delta)^d \mu_1 \cdots \mu_d \right] \leq \approx de^{-\delta^2 \mu_{min}}$</p>

<p>where $\mu_{min}$ is the smallest $\mu_k$. If the number of edges per vertex were independent across vertices (not true, but maybe "close" if $\mu = \omega(1)$), then we could say</p>

<p>$\Pr\left[H_d &gt; (1+\delta)^d E[H_d] \right] \leq \approx de^{-\delta^2 \mu_{min}}$.</p>

<p>So based on this it seems like a sufficient (and hopefully not too loose) condition should be that for every vertex $k$, the expected number of neighbors is $\mu_k = \Omega(\log d)$.</p>

CC BY-SA 3.0
2013-09-26T01:23:27.993Z
I don't think that the condition that the expected number of neighbors of each vertex be $\Omega(\log n)$ is enough. You could just repeat the construction in my answer with two cliques, one of size $O(\log n)$, and one of size $O(n)$ connected by an edge which occurs with probability $1/\log(n)$, and reach the same conclusion. This modified construction would satisfy your condition.
Aaron Roth
CC BY-SA 3.0
2013-09-26T01:55:14.803Z
@AaronRoth, I think I agree: the problem seems to be that in a small clique, $H_d$ will overcount (by many times) vertices that $Z_d$ only counts once. So a concentration bound for $H_d$ does not actually help us bound $Z_d$ because $E[H_d] \gg E[Z_d]$.
usul
CC BY-SA 3.0
2013-09-25T22:30:39.587Z
2013-09-26T01:56:26.620Z
2013-09-26T01:56:26.620Z
usul
<p>Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, i.e., $p_{ij}\rightarrow 0$ as $n\rightarrow \infty$, if it makes things simpler). We define Bernoulli r.v. $X_{ij}$ such that $X_{ij}=1$ iff edge $(i,j)$ exists. We also assume that $X_{ij}$'s are independent r.v.'s (so the existence of edges are independent events). </p>

<p>We consider a random instance of the graph and define $Z_d=$ number of nodes that are reachable from node 1 via paths of length at most $d$ (we can assume $d=O(\log n)$). Then </p>

<p>$Z_d \leq H_d = \sum_{i\neq 1}X_{1i}+\sum_{i,j\neq 1}X_{1i}X_{ij}+\sum_{i,j,k\neq 1}X_{1i}X_{ij}X_{jk}+\ldots$ (till $d$ levels).</p>

<p>I wanted to know if it is possible to get a concentration inequality for $Z_d$, like</p>

<p>$P(Z_d&gt;cE[H_d]\log n)\leq P(H_d&gt;cE[H_d]\log n)\leq c'n^{-1}$, </p>

<p>where $c,c'$ are constants? ($\exp(-c''n)$ in place of $c'n^{-1}$ would be desirable) </p>

<p>(whether $P(H_d&gt;cE[H_d]\log n)\leq c'n^{-1}$ is possible or not is the concentration inequality for function of independent Bernoulli r.v.'s that I am interested in)</p>

<graph-theory><pr.probability>
Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)
fenrir
# Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

(Asked by: username_0 on 2013-09-25)

Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p\_{ij}$ (we may assume $p\_{ij}=o(1)$ for all $i,j$, i.e., $p\_{ij}\rightarrow 0$ as $n\rightarrow \infty$, if it makes things simpler). We define Bernoulli r.v. $X\_{ij}$ such that $X\_{ij}=1$ iff edge $(i,j)$ exists. We also assume that $X\_{ij}$'s are independent r.v.'s (so the existence of edges are independent events).

We consider a random instance of the graph and define $Z\_d=$ number of nodes that are reachable from node 1 via paths of length at most $d$ (we can assume $d=O(\log n)$). Then

$Z\_d \leq H\_d = \sum\_{i\neq 1}X\_{1i}+\sum\_{i,j\neq 1}X\_{1i}X\_{ij}+\sum\_{i,j,k\neq 1}X\_{1i}X\_{ij}X\_{jk}+\ldots$ (till $d$ levels).

I wanted to know if it is possible to get a concentration inequality for $Z\_d$, like

$P(Z\_d>cE[H\_d]\log n)\leq P(H\_d>cE[H\_d]\log n)\leq c'n^{-1}$,

where $c,c'$ are constants? ($\exp(-c''n)$ in place of $c'n^{-1}$ would be desirable)

(whether $P(H\_d>cE[H\_d]\log n)\leq c'n^{-1}$ is possible or not is the concentration inequality for function of independent Bernoulli r.v.'s that I am interested in)

**Tags:** graph-theory, pr.probability

---

## 2 answers

### Answer by username_1 on 2013-09-25. Score: 7 | Accepted answer

In general, it seems that you cannot get the concentration you want without more constraints on the probabilities.

Consider the following graph on $n$ vertices. Let vertices $C = \{2,\ldots,n\}$ form a clique such that for all $i,j \in C$, $p\_{ij} = 1$. Let vertex $1$ be connected to this clique via only one edge, with $p\_{1,2} = 1/\log(n)$, and $p\_{1,j} = 0$ for all $j \in C$ with $j \neq 2$. Then with probability $1/\log(n)$, all $n$ vertices are reachable from $1$ with 2 hops, and with probability $1 - 1/\log(n)$ none are. So the expected number of reachable vertices is $n/\log(n)$, but with probability $1/\log(n) \gg n^{-1}$, it is $n$, larger than its expectation by a $\log(n)$ factor.

In fact, since you are interested in paths of length $\log n$, all that we require is that the realized edges in $C$ form an expander, not a clique, with high probability. This can be accomplished with $p\_{ij} = o(1)$ as well, so this condition does not save you.

The essence of the problem is this: since you can have a group of vertices $C$ that are highly connected with high probability, how many vertices vertex $1$ is connected to can depend only on whether it is connected to $C$ or not, which can depend on only a single edge. You can't expect something depending on only a single Bernouli random variable to be well concentrated.

> **Comments:**
> **username_0**: Thank you for the example and explanation. I realized additional assumptions are needed on the sequence $\{p_{ij}\}$ for deriving concentration bounds.  

---

### Answer by username_2 on 2013-09-25. Score: 1

Here's a heuristic argument to say that, if each vertex has an expected number of edges of at least $\Omega(\log d)$, then you can get such a bound, and furthermore it depends mainly on this expected number of edges per vertex (not much on $n$ or $d$). (**Edit**: As Aaron points out in comments, though, a bound for $H\_d$ does not look like it will help us bound $Z\_d$!) Let's write $H\_d$ as

$H\_d = \sum\_{i\_2\neq 1}X\_{1i\_2} \left(1 + \sum\_{i\_3 \neq 1} X\_{i\_2 i\_3} \left(1 + \cdots \sum\_{i\_{d-2}\neq 1}X\_{i\_{d-2}i\_{d-1}} \left(1 + \sum\_{i\_d \neq 1} X\_{i\_{d-1}i\_d}\right)\cdots \right) \right)$.

Now use Chernoff from the inside and move outward. For each index $i\_k$, let $\mu\_k = \sum\_{j \neq 0} p\_{i\_k j}$.

$\Pr\left[\sum\_{i\_d \neq 0} X\_{i\_{d-1}i\_d} > (1 + \delta)\mu\_d\right] \leq \approx e^{-\delta^2 \mu\_d}$. So replace this innermost sum with the constant $(1+\delta)\mu\_d$ and add $e^{-\delta^2 \mu\_d}$ onto the probability we need. Now expand outwards, adding the probabilities (union-bounding). For example, at the next step we say

$\Pr\left[\sum\_{i\_{d-1}\neq 0} X\_{i\_{d-2}i\_{d-1}} \left(1 + (1+\delta)\mu\_d\right) \geq (1+\delta)(\mu\_{d-1} + (1+\delta)\mu\_d)\right] \leq \approx e^{-\delta^2 \mu\_{d-1}}$.

At the end we get

$\Pr\left[H\_d > (1+\delta)\mu\_1 + (1+\delta)^2 \mu\_1 \mu\_2 + ~\cdots~ + (1+\delta)^d \mu\_1 \cdots \mu\_d \right] \leq \approx de^{-\delta^2 \mu\_{min}}$

where $\mu\_{min}$ is the smallest $\mu\_k$. If the number of edges per vertex were independent across vertices (not true, but maybe "close" if $\mu = \omega(1)$), then we could say

$\Pr\left[H\_d > (1+\delta)^d E[H\_d] \right] \leq \approx de^{-\delta^2 \mu\_{min}}$.

So based on this it seems like a sufficient (and hopefully not too loose) condition should be that for every vertex $k$, the expected number of neighbors is $\mu\_k = \Omega(\log d)$.

> **Comments:**
> **username_1**: I don't think that the condition that the expected number of neighbors of each vertex be $\Omega(\log n)$ is enough. You could just repeat the construction in my answer with two cliques, one of size $O(\log n)$, and one of size $O(n)$ connected by an edge which occurs with probability $1/\log(n)$, and reach the same conclusion. This modified construction would satisfy your condition.  
> **username_2**: @AaronRoth, I think I agree: the problem seems to be that in a small clique, $H_d$ will overcount (by many times) vertices that $Z_d$ only counts once. So a concentration bound for $H_d$ does not actually help us bound $Z_d$ because $E[H_d] \gg E[Z_d]$.  

---

