6
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – user22980
    Commented Apr 2, 2013 at 13:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – R W
    Commented Apr 2, 2013 at 14:13
  • $\begingroup$ 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. $\endgroup$
    – user22980
    Commented Apr 2, 2013 at 15:02
  • $\begingroup$ 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? $\endgroup$
    – R W
    Commented Apr 2, 2013 at 16:09
  • $\begingroup$ 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. $\endgroup$
    – user22980
    Commented Apr 2, 2013 at 17:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .