6CCS3AIN – Week 9
Part B: Voter Model Proof of Theorem 1 (version 1.0)
1 Proof of Theorem 1
Recall Theorem 1 from the lecture that we aim to prove:
Theorem 1.1 Let G = (V,E) be a graph that do not allow deadlocks in a voter model process, i.e., a consensus is reached with probability 1.
Given an initial configuration S0 = s, the probability of blue winning is given by
Pr(Send =blue|S0 =s)=
v∈V,s(v)=b
deg(v) 2|E |
analogously for red.
Proof. Consider the random variable given by the sum of degrees of nodes of a given colour, say blue, at a
given round t. Formally,
deg(v) 2|E |
The proof relies on the fact that this quantity does not change, on average, from one round to the next. In other words, if we calculate all the possibilities of Y1 given the configuration at round t = 0, and weight them by their respective probabilities, their sum would amount to Y0. We show that for a given round t,
E(Yt+1 |St =s)=E deg(v) |St =s 2|E|
v∈V,St+1(v)=b
Note that E(X | Z = z) stands for the conditional expectation of X given that we know that Z = z. Because the choice of a node is independent of the choice of other (although dependent on their current colours, of course), we can write the expected value above as a sum for each node v.
1 E(Yt+1 |St =s)= Pr(St+1(v)=b|St =s)degv
Yt = v∈V,s(v)=b
2|E| v∈V
1 blue-neighbours (v) = tdegv
2|E| v∈V degv
where blue-neighbourst(v) is number of blue neighbours of v at round t, i.e., the number of elements in the set {u | u = N(v),St(u) = b}, where N(v) is the set of neighbours of v.
We can now see that degv cancels and we arrive at the sum of blue neighbours for all nodes v. Well, overall that is equivalent to counting each blue node u as many as deg u times, and thus
E(Yt+1 |St =s)= deg(u) =Yt
2|E | u∈V ,St (u)=b
1
Now that we have shown the variable Y does not change in expectation from one round to the next, we may conjecture that this behaviour carries over for as many rounds as we like. Indeed, Optimal Stopping Theorem guarantees that
E(Yend |S0 =s)=E(Y0 |S0 =s)=Y0 = deg(v) (1)
On the other hand, Yend can be only two values. Since Send represents the end of the game, and thus a consensus, Yend can either be zero (consensus in red), or 1 (consensus in blue). The expected value of E(Yend | S0), by definition, is the value the variable can take multiplied by the probability of them happening, thus:
E(Yend |S0 =s)=0×Pr(Send =red|S0 =s)+1×Pr(Send =blue|S0 =s) (2) Putting Equations 1 and 2 together
As we wanted.
Pr(Send =blue|S0 =s)=
v∈V,s(v)=b
deg(v) 2|E |
2|E | v∈V,s(v)=b
2