I have a $Z^2$ lattice. Every element $(z_1, z_2) \in Z^2$ is connected to one of its 4 neighbours $(z_1, z_2) + (0,1)$, $(z_1, z_2) + (0,-1)$, $(z_1, z_2) + (1,0)$, $(z_1, z_2) + (-1,0)$ by an edge. The edges can be "open" with a probability $p$ and "closed" with a probability 1-p.

I call $\sigma_n$ the total number of self avoinding walks starting from $(0, 0)$ and composed of $n$ steps through the edges. Then I define the event {$ N_n = k $} = {"the number of SAW composed of n OPEN steps is k"}. My question is: is it correct writing that the probability of this event is the following?

$$ P(N_n = k) = \binom {\sigma_n} {k} (p^n)^k (1-p^n)^{\sigma_n - k }. $$

This would mean that the events {"this SAW is open"} and {"this other SAW is open"} are all independent one from the other, but I think it should be wrong because some SAWs necessarily share some edge one with the other one. But on the other hand, this is the only way I am able to justify the last equality in the following expression, which I find in many text books of percolation theory, $$ P( N_n \geq 1) = \sum_{k=1}^{\sigma_n} P(N_n =k) \leq \sum_{k=1}^{\sigma_n} k P(N_n = k) =E[N_n] = p^n \sigma_n. $$ where E is the expectation. Could anyone help me to clarify this point?

  • 1
    $\begingroup$ This follows from linearity of expectation. Write $N_n$ as a sum of $\sigma_n$ 0/1-valued random variables. $\endgroup$ Commented Sep 19, 2012 at 11:25
  • $\begingroup$ Yes, but in order to write the last equality in the last expression one should assume that the $\sigma_n$ events are independent each one from the other one. My question is: are these events really independent? If I take a path $P1$ and a path $P2$ and these two paths share some edges, then the "probability that $P1$ and $P2$ are both open" is not equal to the "probability that $P1$ is open" times the "probability that $P2$ is open" $\endgroup$
    – Lorenzo
    Commented Sep 19, 2012 at 13:54

1 Answer 1


I think your formula for $P(N_n=k)$ is false because as you said, paths are dependent on one-another. With that said:

Expectation is linear, regardless of dependence. Let $S_n$ be the index of set of SAWs of length $n$ and $\gamma_{ni}$ denote a self avoiding path of length $n$, $i\in S_n$. You write

$$N_n=\sum_{i\in S_n} 1_{\gamma_{ni}}$$

Now you note that each $\gamma_{ni}$ has probability $p^n$ and $S_n$ has $\sigma_n$ elements in it. Using $E[1_{\gamma_{ni}}]=p^n$, it immediately follows that $E[N_n]=p^n\sigma_n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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