The process: Given is a clique $C_n$ of size $n$. Consider the following synchronous process, also known as the (synchronous) voter model (e.g., Even-Dar and Shapira): Define an indicator variable $x_i(t)$, which denotes the state of node $i \in \{1,\ldots,n\}$ at step $t$. We interpret $x_i(t)=1$ as "node $i$ is black (infected) at step $t$, and white (uninfected) otherwise."

Initially, $x_1(0)=1$, whereas $x_i(0)=0$ for all $i=2,\ldots,n$. At step $t>0$, each node $i$ picks a neighbour $j \in N(i)$ uniformly at random (we assume that $i \in N(i)$), and sets $x_i(t)=x_j(t-1)$. The process stops only when the nodes are either all-black or all-white. This process is Markovian.

My problem: I want to compute the following probability. For a given $t^*$, compute the probability that for every $i=1,\ldots,n$, $x_i(t^*)=0$. Specifically, I want to show that for $t^*=O(\log n)$, the above probability is $1-o(1)$. In words, I want to show that only after a logarithmic number of steps, the entire clique is all-white w.h.p.

This seems to be similar to the extinction problem in branching programs (wikipedia entry), but I'm not sure if the results for that problem carry over directly to mine.

Update: One can try to solve this problem "from scratch" (without using any known related results), by looking at the following measure.

Let $d(t,j)$ denote the probability that the graph is all-white by step $t$, assuming that there are initially $j$ black nodes (e.g., $x_i(0)=1$ for $i=1,\ldots,j$, and $x_i(0)=0$ for $i=j+1,\ldots,n$). Clearly, we are interested in the value of $d(log n, 1)$. Also, we have that $d(0,0)=1$ and $d(0,j)=0$ for $j>0$; and also $d(t,0)=1$ for $t \geq 0$.

For $t, j>0$, the recurrence can be expressed as follows:


But I'm not sure how to solve it.



Your Answer

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