64 BOUNDING CHAINS
W
t
Δ/#V . Hence
E[W
t+1
|W
t
] ≤W
t
−
W
t
#V
+
W
t
Δ
#V
·
λ
1 +
λ
= W
t
1 −
1
#V
1 −
λ
Δ
1 +
λ
.
Let
γ
=(#V )
−1
(1 −
λ
Δ/(1 +
λ
)).NoteE[W
t
]=E[E[W
t
|W
t−1
]] ≤ E[
γ
W
t−1
]=
γ
E[W
t−1
]. So a simple induction gives E[W
t
] ≤
γ
t
E[W
0
].For
α
> 0, 1−
α
≤exp (−
α
)
so
γ
t
≤ exp(−t(#V)
−1
(1 −
λ
Δ/(1 +
λ
))).
Since W
t
is nonnegative and integral, and W
0
= #V , Markov’s inequality gives
P(W
t
> 0) ≤ E[W
t
] ≤ #V exp(−t(#V )
−1
(1 −
γ
Δ/(1 +
λ
).
The bound on the expected running time for CFTP then follows from Lemma 3.1.
4.2.1 The Dyer-Greenhill shifting chain
Now consider the more effective chain for the hard core gas model of Dyer and
Greenhill from Section 1.8.5, called HCGM
shift. Recall that in this chain when an
attempt is made to label node v with a 1 and exactly one neighbor is preventing that
from happening, there is a Bernoulli S ∼Bern(p
swap
).WhenS = 1, the value x(v)=1
and x(w)=0. So when S = 1, the value of x(w) gets shifted over to x(v).
For the bounding chain, this raises many cases to deal with. For instance, suppose
that U <
λ
/(1 +
λ
), S = 1, all but one neighbor of v has label {0}, and exactly one
neighbor w has label {0, 1}. In the original chain, this meant that y(v)={0, 1}.
But now consider how the shifting chain works. If that {0, 1}neighbor w is hiding
a 0 in the underlying state, then y(v) should be 1. If the {0,1} label at w is hiding a 1
in the underlying state, then y(v) should still be 1, since the neighboring 1 would get
shifted to v anyway! Moreover, the value of y(w) should be changed to {0}, since if
there was a 1 there, it has been shifted away!
Then the underlying state x might have x(w)=0orx(w)=1. But if U <
λ
/(1 +
λ
) and S = 1, then if x(w)=0, the new value of x(v) is 1. And if x(w)=1, then
the new value of x(v) is still 1, and the new value of x(w)=0. So y(v)={1} and
y(w)={0} for all underlying states.
So for all underlying states, y(v)={1}and y(w)={0} in the bounding chain.
That is a good move: the {0,1} label at the node w has been removed! Now
suppose that that all but two neighbors of v have label {0}, one neighbor w
1
has label
{0,1}, and one neighbor w
2
has label {1}. Then for x(w
1
)=x(w
2
)=1, whether or
not S = 1orS = 0, no swap occurs, and x(v)=0,x(w
1
)=x(w
2
)=1.
However, if x(w
1
)=0,x(w
2
)=1, then a swap would occur, so x(v)=1,x(w
1
)=
0,x (w
2
)=0. So in the bounding chain, y(v)=y(w
1
)=y(w
2
)={0,1}.Thisisabad
move for the bounding chain, as two new {0,1} labels have been added!
To break down the bounding chain into cases, let N
denote the number of neigh-
bors of the chosen node v given label .WhenN
{0,1}
= 1, let w
{0,1}
denote the neigh-
bor of v with label {0,1},andwhenN
{1}
= 1, let w
{1}
be the neighbor of v with label
{1}. The complete bounding chain update is given in Table 4.1. In this table, deg(v)
denotes the d egree of v ,and∗ is a wildcard character that indicates any value.
So why go to the extra trouble of executing an update which is far more complex