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\text{ (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)

  • 2
    $\begingroup$ It feels like you at least need to add some additional conditions on $p_{ij}$. For example, suppose that $p_{1j}$ is $0$ unless $j=2$, but all other $p_{ij}$ are reasonably large. Then you'll either have many reachable nodes (if the edge between $1$ and $2$ is present), or won't be able to reach anything. $\endgroup$ – Kevin P. Costello Sep 26 '13 at 4:33
  • $\begingroup$ Thanks, I realized this too - $p_{ij}$'s need to satisfy additional constraints for concentration results to hold. $\endgroup$ – adas Sep 28 '13 at 5:43

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.