Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

$Z_d \leq H_d=\sum_{i\neq 1}X_{1i}+\sum_{i\neq 1}\sum_{j\neq 1}X_{1i}X_{ij}+\ldots$.

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)

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.