5
$\begingroup$

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)

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the example and explanation. I realized additional assumptions are needed on the sequence $\{p_{ij}\}$ for deriving concentration bounds. $\endgroup$ – fenrir Nov 22 '13 at 8:49
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Aaron Roth Sep 26 '13 at 1:23
  • $\begingroup$ @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]$. $\endgroup$ – usul Sep 26 '13 at 1:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.