I have run into this problem in my research, which I'm presenting under a different guise to avoid going into unnecessary background.

Consider a population that is connected in a triangular manner, as shown in the figure below. The root node has a disease, which spreads downwards through the population as follows:

  • With probability $p$ a diseased parent node infects only one of its two child nodes (chosen randomly); and with probability $1-p$ it infects both of them

  • A child node becomes diseased if it is infected by one or two parent nodes

I am interested in the asymptotic behavior of the expected number of diseased nodes at level $k$.

enter image description here

Simulations show that the expected number of diseased nodes grows asymptotically linearly with the number of levels.

Moreover, the slope of this relationship decreases approximately linearly with $p$ (obviously, when $p = 0$ the slope is $1$, as everyone gets diseased; when $p = 1$ the slope is $0$ as the number of diseased nodes remains at $1$ at every level).

So the behavior seems to follow: $E(\text{diseased nodes at level n})=(1 - p)n$, at least to a very good approximation.

enter image description here

enter image description here

  • $\begingroup$ Isn't this just a Galton-Watson branching process with offspring distribution having generating function $P(s)=ps + (1-p)s^2$? $\endgroup$ – Math1000 Oct 28 '15 at 16:24
  • $\begingroup$ @Math1000 I'd never come across branching processes before, so thanks for the pointer! I'll read up on them. $\endgroup$ – MGA Oct 28 '15 at 18:19
  • 1
    $\begingroup$ @Math1000 At least following the definitions given on Wikipedia, this problem is not a Galton-Watson process or a branching process in general. In these, each parent in a generation has a number of offspring independent of the other parents; here, parents are 'sharing' offspring. But maybe there's a way to re-formulate this problem to make it look like a branching process. $\endgroup$ – MGA Oct 28 '15 at 18:53
  • $\begingroup$ Actually yes, this is a bit more complicated, especially because there are two "types" of offspring. $\endgroup$ – Math1000 Oct 28 '15 at 23:56
  • $\begingroup$ Another observation: if $p=1$, this process becomes exactly analogous to a bean machine. The probability of infection of each node $k$ at level $n$ (going from left, $k=1$, to right, $k=n$) is a binomial distribution $\binom{n}{k}$. If $p<1$ the profile of the probability of each node at level $n$ being infected is not a distribution (i.e., it does not sum up to $1$), because the process is not conservative. Simulations show that the profile starts to flatten with decreasing $p$. $\endgroup$ – MGA Oct 29 '15 at 2:43

In this answer I compute the generating function $f(z) = \sum a_n z^n$ where $a_n$ is the expectation of infected nodes at level $n$ if there is a single infected node at level $0$, and use it to get the asymptotic behaviour for $a_n$.

The main obstacle to doing this is to get the generating function of the cells given by $2$ neighbouring infected nodes $N_1$ and $N_2$. By the inclusion exclusion principle this is as hard as getting the generating function of the cells infected by both cells. However, if you look carefully, there is a node $N_3$ that is the earliest common infected from $N_1$ and $N_2$ : a node is infected by both $N_1$ and $N_2$ if and only if it is infected by $N_3$.

Before computing $f$, we need to get the probability law of the level at which $N_3$ appears.

let $b_n$ be the probability that $N_3$ is at level $n$.
If we look at the rightmost infected descendant of the left node at each level, its position moves right with probability $1-p/2$, and moves left with probability $p/2$. Somethiong similar can be said for the leftmost infected descendant of the right node, and so their difference is a biased random walk that moves by $-1$ with probability $(1-p/2)²$, moves by $+1$ with probability $(p/2)^2$ and doesn't move the rest of the time (which is $p-p^2/2$).

Therefore, if we let $g(z) = \sum b_n z^n$, we have $g(z) = z[(1-p/2)^2 + (p-p^2/2)g(z) + (p^2/4)g(z)^2]$.

From this we get
$$g(z) = p^{-2}((2 - p(2-p)z) - 2\sqrt{1 - p(2-p)z}) \\ = (2-p)^2(z/4) + 2p(2-p)^3(z/4)^2 + 5p^2(2-p)^4(z/4)^3 + \ldots \\ = \sum_{n \ge 1} C_np^{n-1}(2-p)^{n+1}(z/4)^n$$

where $C_n$ are the Catalan numbers.

Now that we got $g$, we can focus on $f(z) = \sum a_n z^n$.

We have $f(z) = 1 + zf(z)(p + (1-p)(2-g(z)))$, and so

$$f(z) = 1/(1-(2-p)z+(1-p)p^{-2}[2-p(2-p)z-2\sqrt{1-p(2-p)z}]) \\ = 1 + 2((2-p)z/2) + (3+p)((2-p)z/2)^2 + (4+3p+p^2)((2-p)z/2)^3 + \ldots $$

Now the asymptotic behaviour of those coefficients depend on what kind of singularities $f$ has and where.

After rationalising the denominator we have $$f(z) = \frac{(2-2p+p^2) - p(2-p)z + 2(1-p)\sqrt{1-p(2-p)z}}{(2-p)^2(1-z)^2} \\ = \frac{4(1-p)^2}{(2-p)^2(1-z)^2} + \frac{2p}{(2-p)(1-z)} + \frac{(-2+2p-p^2) + 2p(1-p)z + 2(1-p)\sqrt{1-p(2-p)z^2}}{(2-p)^2(1-z)^2} $$

where that last fraction has a removable singularity at $z=1$.

Computing the Taylor series for the first two terms is not difficult, and the third has a branch point at $z = 1/p(2-p)$, so the Cauchy integral formula implies that its coefficient are a $O((p(2-p))^n)$ :

We get $a_n = \frac{(1-p)^2}{(1-p/2)^2}(n+1) + \frac p{1-p/2} + O((p(2-p))^n)$.

We can go more in-depth and get more information by assigning an indeterminate $x$ for the horizontal axis and using generating functions in two variables. Put the origin of the top row at the position of the original infected node, and put the origin of the next level at the left descendant of the previous origin.

Let $g(x,z) = \sum b_{n,k}x^kz^n$ where $b_{n,k}$ is the probability that $N_3$ appears at the node $k$ at level $n$ ; and $f(x,z) = \sum a_{n,k}x^kz^n$ where $a_{n,k}$ is the probability that the node $k$ at level $n$ is infected.

(we get the old $f$ and $g$ by doing the partial evaluation $x=1$).

Now this is only a matter of refining everything said above.

We have the equations

$$g = z[(1-p/2)^2\frac{1+x}2 + (p-p^2/2)g\frac{1+x}2 + (p^2/4)g^2] \\ f = 1 + zf(p\frac{1+x}2 + (1-p)((1+x)-g)) $$

We eventually get

$ f = \frac{(8-8p+4p^2) - 2p(2-p)(1+x)z + 2(1-p)\sqrt{16 - 8p(2-p)(1+x)z + (p(2-p)(1-x)z)^2}} {(2-p)^2(2 - (2-p+px)z)(2 - (2x+p-px)z)} = t_1+t_2+t_3$


$ t_1 = \frac{16(1-p)^2}{(2-p)^2(2 - (2-p+px)z)(2 - (2x+p-px)z)}$
$ t_2 = \frac{2p}{2-p}\left(\frac 1 {2 - (2-p+px)z} + \frac 1 {2 - (2x+p-px)z}\right)$
$ t_3 = \frac{-8+8p-4p^2 + 2(2-p)pz(1+x) + 2(1-p)\sqrt{16 - 8p(2-p)(1+x)z + (p(2-p)(1-x)z)^2}}{(2-p)^2(2 - (2-p+px)z)(2 - (2x+p-px)z)} $

and once again, the singularity along the two curves in $t_3$'s denominator are removable in this branch of the square root.

$t_1$'s and $t_2$'s constributions have the same asymptotic behaviour around the edges of the triangle, while in the middle, $t_1$'s terms should quickly become more dominant.

$t_1 = \frac {4(1-p)}{(2-p)^2(1-x)} \left(\frac{2-p+px}{2-(2-p+px)z}-\frac{2x+p-px}{2-(2x+p-px)z}\right) = \frac {4(1-p)}{(2-p)^2(1-x)} \left(\sum_{n \ge 0} ((\frac{2-p+px}2)^{n+1} - (\frac{2x+p-px}2)^{n+1}) z^n \right) $

The coefficients of $((2-p+px)/2)^{n+1}$ are the distribution a random walk looking like the left border of the infected population, and after dividing by $1-x$, we obtain the probabilities that we are to the right of that random walk.

After substracting the two terms, it turns out that the coefficients of $t_1$ are $\frac{4(1-p)}{(2-p)^2}$ times the probability to be between the left and right borders of the infected population, if those borders were two (dependant, because they mustn't cross each other) random walks, one with mean $p/2$ the other with mean $1-p/2$ and both with variance $p(2-p)/4$.

Thus those coefficients converge to a rectangular shape of height $\frac{4(1-p)}{(2-p)^2}$, with borders shaped like the error function at positions $pn/2$ and $(1-p)n/2$ and with width $O(\sqrt{np(2-p)})$.

The $t_2$ term is $\frac p{2-p}$ times the position of those random walks, so it adds two small gaussian shapes of height $O(\sqrt{p/n(2-p)^3})$ and width $O(\sqrt {np(2-p)})$ on top of those transitions (note that when $p=1$, $t_1=0$ and this is the dominant term instead)


The width of the $k+1$th row depends on the one infected at each end.
With probability $p^2$, they each have one descendant. Then the width shrinks with probability 1/4, stays the same with probability 1/2 and grows with probability 1/4.
With probability $2p(1-p)$, one edge has two descendants and the other has one. The width stays the same with probability 1/2 and grows with probability 1/2.
With probability $(1-p)^2$, both edges have two descendants, and the next row will be wider.
So the expected width of the next row is $$(W-1)\frac{p^2}4+W\left(\frac{p^2}2+p(1-p)\right)+(W+1)\left(\frac{p^2}4+p(1-p)+(1-p)^2\right)=W+1-p$$ where $W$ is the width of the current row. So the expected width of the $k$th row is $$W(k)=1+(k-1)(1-p)$$

Let $q$ be the probability that an individual within that region is infected. Suppose this is the same for all rows. The chance a child is infected is $$q^2\left(1-\frac{p^2}4\right)+2q(1-q)\left(1-\frac p2\right)+(1-q)^20=q$$ $$q=\frac{1-p}{(1-p/2)^2}$$

So the expected number of infected persons in the $k$th row is $$Wq=\frac{1-p+(1-p)^2(k-1)}{(1-p/2)^2}$$ and an equation for your second, blue graph is $$y=\frac{(1-p)^2}{(1-(p/2))^2}$$

Now for stability. Suppose the density on one row is $q=\frac{1-p}{(1-p/2)^2}+\epsilon Q$. Then, I think the density on the next row is $\frac{1-p}{(1-p/2)^2}+\epsilon pQ+O(\epsilon^2)$. So the density tends to approach steady-state if it starts off close enough.

  • $\begingroup$ Is this assuming that the set of infected individuals at each generation is an "interval"? In the sense that every individual "between" the leftmost infected individual and the rightmost infected individual (the two individuals you call "the edges", I believe) would be infected. $\endgroup$ – Did Oct 29 '15 at 9:36
  • $\begingroup$ @Did No. If the edges are $x=a$ and $x=b$, I expect $(b-a)*q$ of the individuals to be infected. $\endgroup$ – Empy2 Oct 29 '15 at 10:48
  • $\begingroup$ Then I fail to see how the dynamics of the width can be as simple as you pretend. Writing X for an infected site and O for a healthy site, the width after XOOOX and the width after XXXXX do not have the same distribution. And even fixing the proportion of infected sites between the edges, compare XOXOXOX and XXXOOOX... $\endgroup$ – Did Oct 29 '15 at 11:00
  • $\begingroup$ Firstly, I think the widths do have the same distribution. The X at the end always infects at least one child, so the inner sites don't affect the width. Secondly, I was worried about the correlation between neighbouring parents, but the formula is already a good approximation to OP's blue graph. $\endgroup$ – Empy2 Oct 29 '15 at 11:35
  • $\begingroup$ Right, the width is indeed a Markov chain, I overlooked the argument. Next in line is $q$ the probability that an individual within that region is infected. The computation you present assumes that the states of the individuals between the edges are i.i.d. Bernoulli, right? One would expect some positive correlation between neighbouring sites so if indeed your mean field computation is a good approximation there must be some reason... $\endgroup$ – Did Oct 29 '15 at 11:42

I consider the neighbour correlation for this answer.
Within the infected area, I use these probabilities. Let X mean infected, and O mean uninfected. $$ Pr(X)=a+b,Pr(O)=b+c$$ $$ Pr(XX)=a,Pr(XO)=Pr(OX)=b,Pr(OO)=c$$ $$ Pr(XXX)=Pr(XX)Pr(X|X)=\frac{a^2}{a+b},\text{ etc.}$$ Now calculate $Pr(OO)$ and $Pr(OX)$ given that distribution of parents: $$Pr(OO)=Pr(OOO)Pr(OO|OOO)+Pr(OOX)Pr(OO|OOX)+...$$ $$ =\frac1{b+c}\left[c^21+bc\frac p2+bc\frac p2+b^2\frac{p^2}4 \right]=c$$ therefore $$c(1-p)=bp^2/4$$ $$ Pr(OX)=\frac1{a+b}\left[a^2p^2/4+abp^2/4+bap/2+b^2p/2 \right]$$ $$ +\frac1{b+c}\left[b^2(p/2)(1-p/2)+bc0+cb(1-p/2)+c^20 \right]=b$$ Wolfram isn't up to solving that, so I will try Maple tomorrow.
EDIT: Maple gave the same answer with correlation that I got without correlation, and $P(XX)=P(X)P(X)$ etc.
For stability, consider $a=a_0+\epsilon A,c=c_0+\epsilon C$, where $a=a_0$ and $c=c_0$ are the steady-state values just mentioned; and $\epsilon$ is a small parameter. Then, to order $O(\epsilon)$, the equations are linear in $A$ and $C$. Maple's results of my questioning tell me that, for $a=a_0+\epsilon A,c=c_0+\epsilon C$ on one row and $a=a_0+\epsilon A',c=c_0+\epsilon C'$ on the next row, $$\left[\begin{array}{c}A'\\C'\end{array}\right]=\frac1{2(2-p)^2}\left[\begin{array}{cc} p(8-13p+7p^2-p^3)&-(1-p)(4-3p)\\ -p^2(1-p) & p^3-7p^2+8p\end{array}\right]\left[\begin{array}{c}A\\C\end{array}\right]+O(\epsilon)$$ (sorry if the arrays killed the page again) The eigenvalues of the array are $p(3-p)/2$ and $p/2$, so they are both between $0$ and $1$, so $A$ and $C$ both approach zero as the level $n$ increases.

  • $\begingroup$ Your use of $\backslash\backslash$ in this answer and in the other one were breaking the page. $\endgroup$ – Did Oct 29 '15 at 15:54
  • $\begingroup$ I don't get the same results, Taking this correlation into account induces a slight correction. Also I tried a random $p$ and after plugging your $q$ from the other post into $a=q^2,b=q(1-q),c=(1-q)^2$, then none of the following two equations are satisfied. $\endgroup$ – mercio Nov 2 '15 at 12:36
  • $\begingroup$ That's very possible. Perhaps my P(XXX) etc is wrong, or I copied down one of the probabilities wrong, or my logic was wrong. $\endgroup$ – Empy2 Nov 2 '15 at 16:33
  • $\begingroup$ mfw i forgot to write a parenthesis... so my earlier comment seem to be wrong, and I get no correlation at higher levels either oO $\endgroup$ – mercio Nov 3 '15 at 10:33

In this answer I'll show that when you pick the right probability $q$ ($q = \frac {1-p}{(1-p/2)^2}$) and start with a line randomly colored with probability $q$ (each dot independantly from every other), and apply your process, you obtain again a line randomly colored with probability $q$ (each dot independantly from every other).

And so that this random coloring is a fixpoint of your process.

Let $a = \sqrt{1-q} = \frac {p/2}{1-p/2}\in (0;1)$ and consider an infinite Markov chain $(X_n)_{n \in \Bbb Z}$ on $3$ states $\{\circ ; \bullet ; \hat \bullet \}$, with probability matrix

$M_a = \begin {pmatrix} a & 0 & 1-a \\ a & 0 & 1-a \\ 0 & a & 1-a \end{pmatrix}$

Now if you compute $M_a^2$, you will find

$M_a^2 = \begin {pmatrix} a^2 & a-a^2 & 1-a \\ a^2 & a-a^2 & 1-a \\ a^2 & a-a^2 & 1-a \end{pmatrix}$

which means that (amazingly) $(X_{2n})_{n \in \Bbb Z}$ (as well as $(X_{2n+1})_{n \in \Bbb Z}$) are independantly identically distributed with $p(\circ) = a^2, p(\bullet) = a-a^2, p(\hat \bullet) = 1-a$. If you erase the distinction between $\bullet$ and $\hat \bullet$, each dot is colored with probability $q=1-a^2$.

Compare the sequence $(X_{2n})$ with a random row of nodes that are infected independantly with probability $q$. So far they behave the same. On that row, add the information of which infected nodes are going to infect their right child. The nodes are still independant and identically distributed, and the distribution of the three possible states matches perfectly with what our Markov chain does (indeed, the probability of being infected and infecting the right child is $q(1-p/2) = \frac {1-p}{1-p/2} = 1-a = p(\hat \bullet)$)

The goal is then to show that the sequence $(X_{2n+1})$ behaves exactly like the child nodes from the "top row" $(X_{2n})$, i.e. a child note is infected or not depending only on his two parents :

we have to show that if the left parent is $\hat \bullet$ or the right parent is $\bullet$ then the child (from the Markov chain) is always infected, else if the right parent is $\hat \bullet$ then the child is infected with probability $\frac {1-p}{1-p/2}$ (independantly from everything), else it is never infected.

Or we can be lazy and just check that the probability of any configuration happening is what it should be :
$p(\circ\circ\circ) = a^4 = (1-q)^2$
$p(\circ\circ\hat\bullet) = a^3(1-a) = (1-\frac {1-p}{1-p/2})(1-p/2)q(1-q)$
$p(\circ\;\hat\bullet\;\bullet) = a^3(1-a) = (p/2)q(1-q) $
$p(\circ\;\hat\bullet\;\hat\bullet) = a^2(1-a)^2 = (\frac {1-p}{1-p/2})(1-p/2)q(1-q)$
$p(\bullet \circ \circ) = a^3(1-a) = (p/2)q(1-q)$
$p(\bullet \circ \hat\bullet) = a^2(1-a)^2 = (1-\frac {1-p}{1-p/2})(p/2)(1-p/2)q^2$
$p(\bullet\; \hat\bullet\; \bullet) = a^2(1-a)^2 = (p/2)^2q^2$
$p(\bullet\; \hat\bullet\; \hat\bullet) = a(1-a)^3 = (\frac {1-p}{1-p/2})(p/2)(1-p/2)q^2$
$p(\hat\bullet \bullet \circ) = a^2(1-a) = (1-p/2)q(1-q)$
$p(\hat\bullet\; \hat \bullet \; \bullet) = a(1-a)^2 = (p/2)(1-p/2)q^2$
$p(\hat\bullet\; \hat \bullet \; \hat \bullet) + p(\hat\bullet \bullet \hat \bullet) = (1-a)^3 + a(1-a)^2 = (1-p/2)^2q^2$

This is enough because we know that the Markov chain forgets about anything that happens beyond any direct neighbour, so every point in the middle really is only dependant on its two neighbours, and not on anything else and it also cannot influence anything else.

But remember that the sequence $(X_{2n+1})$ is an i.i.d. sequence ! Since it is also matches perfectly with the child sequence of an i.i.d parent sequence, your infection process transforms an infinite i.i.d sequence of density $q$ into another i.i.d sequence of density $q$.

This suggests that this behaviour could be the asymptotic behaviour of what happens from just one infected point (though of course it's not a proof).

  • $\begingroup$ What configuration or property of the OP's tree do your three states represent? $\endgroup$ – rajb245 Apr 20 '16 at 20:36
  • $\begingroup$ If you interpret the nodes at even positions as a top row of nodes, $\circ$ is a noninfected node, $\bullet$ an infected node that doesn't infect his right child, and $\hat \bullet$ is an infected node that infects his right child. Due to properties of the Markov chain, they are all i.i.d. variables. Then, the nodes at odd positions are the bottom row of nodes (the next generation). $\circ$ are uninfected, and $\bullet, \hat \bullet$ are infected, but I'm not sure if there is a natural interpretation of the hat. $\endgroup$ – mercio Apr 21 '16 at 11:42

In this answer I want to prove that in the triangle region under the initial node, the more we go down, the more infection of a particular node is independant from infection of all the other nodes at the same level.

Instead of looking down form an initial infected node, start from a node and look up. To prove the result, I extend the diagram infinitely upwards, which gives me new random variables with which to define an idealised infected random variable, which has the independance property, and then I want to show that they are good approximations of the normal infection random variables.

We change the viewpoint a bit by giving for each node at position $k \in \Bbb Z$ on row $n \in \Bbb N$ a random variable $(Y_{k,n})$ with values in $\{left ; both ; right\}$ telling us which children nodes he would infect if it was infected.

Then I suppose I have random variables $X_{k,0}$ for infectedness at the top level, which determines (with the $Y$'s help) all the random variables $X_{k,n}$ for infectedness at the lower levels ($X_{k,n}$ is completely determined by $X$ and $Y$ at the two parent nodes $(k-1,n-1)$ and $(k,n-1)$)

The question is then about conditional probabilities about $X_{k,n}$ for $n>0$ when knowing $X_{k,0} \iff k=0$ .

Suppose you know about all the $Y_{k,n}$ but not about the $X_{k,n}$. When you look at a node and try to see what needs to be infected among its ancestors to make it infected, you obtain that the event $X_{k_0,n_0}$ is equivalent to a chain of events of the form $E_{k_1(n),k_2(n),n} = \bigvee_{k=k_1(n)}^{k_2(n)} X_{k,n}$, saying "there is an infected node in this horizontal interval" for each $0 \le n < n_0$ (this include empty events when $k_2 < k_1$)

Concretely, if $k_2(n) \ge k_1(n)$ then $E_{k_1(n),k_2(n),n} = E_{k_1(n-1),k_2(n-1),n-1}$ where $k_1(n-1) = k_1(n)$ if $Y_{k_1(n)-1,n-1} = left$ and $k_1(n-1) = k_1(n)-1$ otherwise, and $k_2(n-1) = k_2(n)-1$ if $Y_{k_2(n),n-1} = right$ and $k_2(n-1) = k_2(n)$ otherwise.

$k_1(n)$ and $k_2(n)$ are a sequence of random variables that only depend on $k_0,n_0$ and $Y$. It can happen that there is some level $n$ with $k_2 < k_1$, which means that even if everyone in level $n$ was infected, the disease wouldn't reach $(k_0,n_0)$. As long as this doesn't happen, $k_1$ and $k_2$ are independant biased random walks.

Let $F_{k_0,n_0}$ be the event (depending on the $Y$) that node $(k_0,n_0)$ is infected if the whole top row is infected, or equivalently, that $k_1(n) \le k_2(n)$ forall $0 \le n \le n_0.$. This has some probability $p_{n_0}$ to happen, and the earlier result about population independantly infected with probability $q=1-p/(1-p/2)^2$, we have not only that $\lim_{n \to \infty} p_n = q$, but also that the $m$-uples $(F_{k+1,n}, F_{k+m,n})$ converge in law as $n \to \infty$ to an $m$-uple vector of independant variables.

At this point, we really want to compare $X_{k_0,n_0}$ with $F_{k_0,n_0}$ but for an ideal version of $F$ where we go up infinitely. So we add random variables $Y_{k,n}$ for negative $n$, which allows us to define $\hat F_{k_0,n_0}$ as the event $\forall n \le n_0, k_1(n) \le k_2(n)$.

Now, when you look at them level by level, those variables are independant and identically distributed (any of them happens with probability $q$), and the sequence of probabilities $P(F_{k_0,n_0} \setminus \hat F_{k_0,n_0})$ only depends on $n_0$ and converges to $0$ when $n_0 \to \infty$.

Finally, we can show that when we pick a node in the right region under the initial node $(0,0)$, $X_{k,n}$ is well approximated by $F_{k,n}$ , which essentially means that either $F_{k,n}$ is false (then they are both false), either it leads to an interval containing $0$ (then they are both true), or it is very improbable that it leads to an interval not containing $0$.

Since the borders of that interval are almost independant random walks, we can put a bound on this last case by replacing $k_1,k_2$ with independant random walks (that can cross each other) then applying the central limit theorem.

This shows that $X$ is well approximated by a family of rows of independant random variables.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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