Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $G_n=(V_n,E_n)$ be an Erdos-Rényi random graph, precisely the vertex set is $V_n=(1,\dots,n)$ and the edge set is $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ \epsilon_{ij}=1)$ where $(\epsilon_{ij})_{ij}$ are i.i.d. random variables with distribution $\textrm{Bernoulli}(c/N)$ .

It is known that $(G_n)_{n\in\mathbb{N}}$ locally converges to tree. I'm trying to prove this fact "by hands". The part which gives me some troubles is the concentration of measure. I state precisely my problem.

Fix $r\in\mathbb{N}$ and $(T,o)$ a finite rooted tree with at most $r$ generations. For any vertex $v\in V_n$ consider $B_{G_n}(v,r)$, the rooted sub-graph of $G_n$ induced by the vertices at graph-distance $\leq r$ from $v$. Consider the following random variable

$$M_n:=\frac{1}{n}\sum_{v=1}^{n}\chi(B_{G_n}(v,r)\equiv(T,o))\ ,$$ where $\chi(A)$ is the indicator function of the event $A$. And consider its expectation

$$\mathbb{E}[M_n]=\frac{1}{n}\sum_{v=1}^{n}\mathbb{P}(B_{G_n}(v,r)\equiv(T,o))\ .$$

I would like to prove that

$$|M_n-\mathbb{E}[M_n]|\xrightarrow[n\to\infty]{}0\ \ a.s.$$

Any idea? I tryed to consider a Doob martingale, exposing vertex by vertex, and to bound its differences in order to apply Azuma-Hoeffding inequality. But did not manage to find a useful bound. Can you help me?

Edit. I write more clearly the way I've tried. Fix $n\in\mathbb{N}$. Define the filtration which at each step let you know the subgraph of $G_n$ induced by the first $i$ vertices: $$\mathcal{F_1}:=(\Omega,\emptyset),\ \ \mathcal{F_i}:=\mathcal{F_{i-1}}\cup\sigma(\epsilon_{i1},\epsilon_{i2},\dots,\epsilon_{i(i-1)})\ \ \forall i=2,\dots,n.$$ Then define the following Doob martingale: $$A_i:=\mathbb{E}[M_n|\mathcal{F_i}]\ \ \forall i=1,\dots,n$$ noticing that $A_n=M_n$ and $A_0=\mathbb{E}[M_n]$. Now if one finds a $c_n>0$ such that $n\ c_n^2\xrightarrow[n\to\infty]{}0$ (fast enough) and $$|A_i-A_{i-1}| < c_n\ \ \forall i=2,\dots,n$$ then by the Azuma-Hoeffding inequality one obtains that $$\mathbb{P}(|M_n-\mathbb{E}[M_n]|>t)\ \leq\ 2\ \exp(-\frac{t^2}{2\ n\ c_n^2})\ \ \forall t>0$$ which allows to conclude thanks to Borel-Cantelli lemma. The problem is bounding $|A_i-A_{i-1}|$.

Edit2. Let $d$ be the maximum degree of the tree $T$. Note that in general if two graphs $G,\tilde{G}$ differ only for one edge (i.e. $G$ contains a given edge $ij$ while $G'$ does not), then the two sums $$\phi_G:=\sum_{v=1}^n\chi(B_{G}(v,r)\equiv(T,o))\ \ ,\ \ \phi_{\tilde{G}}:=\sum_{v=1}^n\chi(B_{\tilde{G}}(v,r)\equiv(T,o))$$ may differ at most for $2 \sum_{l=0}^r d^l$ terms (this is an upper bound for the number of vertices $v$ which can be reached from $i$ or $j$ by a walk of lenght $l\leq r$ completely made of vertces with degree $\leq d$).

Now what happens to $|\phi_G-\phi_{\tilde{G}}|$ if instead the graphs $G,\tilde{G}$ differ for one vertex (i.e. for some edges attached to a given vertex $i$)? I fear the previous bound explodes becoming unuseful in the Azuma-Hoeffding inequality... Am I right?

Maybe is there a way to exploit the fact that in a Erdos-Rényi graph the edges are not too much (precisely $|E_n|/n\xrightarrow[n\to\infty]{}c/2\ a.s.$)?

share|improve this question
add comment

2 Answers

Why not use second moment? For fixed $r$, the correlation between the events that $B_{G_n}(v,r)$ is a tree and the same event for $v'\neq v$ is small, of order $f(c)/n$. Try $r=2$ to see what I mean. You can even (since you need only a lower bound) throw into the random variables the event that the maximal degree in $B_{G_n}(v,r)$ is bounded by some function $g(c,r)$ that grows fast enough.

This argument may be not strong enough for a.s. limits though.

share|improve this answer
add comment

Why to make it so complicated? One can see directly that in the limit these graphs have no cycles (just estimate this probability as a function of $n$).

PS I was never able to understand why probabilists prefer to call weak convergence local - some kind of reinventing the wheel.

share|improve this answer
    
I already showed that the probability of the event "the ball $B_{G_n}(v,r)$ is a tree" goes to $1$ as $n\to\infty$ (I did it by induction on the radius $r$). But now I'd like to prove that the fraction of "balls $B_{G_n}(v,r)$ that are trees" concentrates around its expectation. This way I'd finally obtain an almost sure convergence of this fraction to $1$. –  user22980 Apr 2 '13 at 13:42
1  
Don't understand why you would need any concentration here. If you reverse your condition and talk about the probability of "not being a tree", then you have to deal with convergence of non-negative functions to 0. –  R W Apr 2 '13 at 14:13
    
Maybe I wasn't clear. In the notation of the post: 1) I ALREADY proved that $\sum_{(T,o)}\mathbb{E}[M_n]\to1$ as $n\to\infty$ (so now I'm not interested in it); 2) I'D LIKE TO prove that $\sum_{(T,o)}M_n\to1$ almost surely as $n\to\infty$. You will agree that 2) is not a consequence of 1), unless I prove concentration of measure. –  user22980 Apr 2 '13 at 15:02
    
Almost sure convergence a priori does not make any sense when talking about weak convergence of a sequence of measures. For a.s. convergence one needs a measure in the space of sequences (in your case in the space of sequences of graphs whose size n goes to infinity) - what is the measure with respect to which you want to consider a.s. convergence? –  R W Apr 2 '13 at 16:09
    
Yes, assume all the graphs $G_n,n\in\mathbb{N}$ are defined on the same probability space $(\Omega,\mathbb{P})$. If needed we can assume they are mutually independent. –  user22980 Apr 2 '13 at 17:00
add comment

Your Answer

 
discard

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

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