Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

Question

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)

Answer 1

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.

Answer 2

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)$.