USING CONTINUOUS STATE SPACES FOR PERMUTATIONS 117
6.8.1 Height-2 posets
Another situation where the continuous version provably helps is when dealing with
posets o f height 2. Caracciolo et. al. referred to this as the corrugated surface prob-
lem [20].
Definition 6.8. The height of a poset is the largest integer h such that there exist
distinct elements a
1
,...,a
h
of the poset with a
1
a
2
···a
h
.
Consider the graph that has nodes corresponding to elements of the state space,
and an edge between i and j if i ≺ j or j ≺ i.ThenletΔ be the maximum degree of
this graph. So Δ = max
i
{# j : i ≺ j or j ≺ i}.
First show that the chain is likely to move together if the number of steps is large.
Lemma 6.5. Consider lines 5 through 7 of Linear
extension cftp.Ift≥
2n((2Δ −1)ln(8n
2
)+ln(4n)),then
P
max
i
|x
min
(i) −x
max
(i)| > 1/(8n
2
)
≤ 1/4. (6.19)
Proof. Let d
k
be the vector x
max
−x
min
after executing lines 6 and 7 exactly k times.
Then d
0
=(1, 1,...,1). The proof uses the following potential function on nonnega-
tive vectors:
φ
(d)=
n
∑
i=1
d(i)
2Δ−1
. (6.20)
The goal is to show that the expected value of E[d
k
] decreases exponentially as k
increases. Now
E[
φ
(d
k+1
)|d
k
]=E
n
∑
i=1
d
k+1
(i)
2Δ−1
d
k
. (6.21)
At the k + 1st step, only coordinate I
k+1
could change. Hence
E[
φ
(d
k+1
)|d
k
]=
φ
(d
k
)+E[d
k+1
(I
k+1
)
2Δ−1
−d
k
(I
k+1
)
2Δ−1
|d
k
]. (6.22)
Suppose that I
k+1
is not preceded by any other element. Then
a
min
= a
max
= 0, b
min
= min{1, inf
j:I
k+1
≺j
x
min j
( j)},b
max
= min{1, inf
j:I
k+1
≺j
x
max j
( j)}
(6.23)
which makes d
k+1
(I
k+1
)=U
k+1
(b
max
−b
min
).
If there is no element j such that I
k+1
≺ j then b
max
−b
min
= 0. Otherwise there
exists j
∗
where x
min
( j
∗
)=b
min
.Bydefinition b
max
≤x
max
( j
∗
), which means b
max
−
b
min
≤ x
max
( j
∗
) −x
min
( j
∗
)=d
k
( j
∗
).Usingd
k
( j
∗
)
2Δ−1
≤
∑
j:I
k+1
≺j
d
k
( j)
2Δ−1
gives
[U
k+1
(b
max
−b
min
)]
2Δ−1
≤U
2Δ−1
k+1
∑
j:I
k+1
≺j
d
2Δ−1
j
. (6.24)
Since U
k+1
∼ Unif([0, 1]), taking the expectation of both sides gives
E[d
k+1
(I
k+1
)
2Δ−1
|d
k
,I
k+1
]=E[U
k+1
(b
max
−b
min
)] ≤
1
2Δ
∑
j:I
k+1
≺j
d
k
( j)
2Δ−1
. (6.25)
118 COALESCENCE ON CONTINUOUS AND UNBOUNDED STATE SPACES
A similar result holds if I
k+1
is an element that precedes no other element. Taking
the expectation over I
k+1
to remove the conditioning on I
k+1
gives
E[d
k+1
(I
k+1
)
2Δ−1
|d
k
] ≤
1
n
n
∑
i=1
1
2Δ
∑
j: j≺i or i≺j
d
k
( j)
2Δ−1
=
1
2Δn
∑
j
∑
i:i≺j or j≺i
at most Δ terms
d
k
( j)
2Δ−1
≤
1
2n
φ
(d
k
).
Next note that
−E[d
k
(I
k+1
)|d
k
]=−E[E[d
k
(I
k+1
)|d
k
,I
k+1
]] = −
∑
i
1
n
d
k
(i)
2Δ−1
= −
1
n
φ
(d
k
), (6.26)
which gives the exponential decrease (on average) that we were looking for.
E[
φ
(d
k+1
)|d
k
] ≤
φ
(d
k
)+
1
2n
φ
(d
k
) −
1
n
φ
(d
k
)=
φ
(d
k
)
1 −
1
2n
. (6.27)
A simple induction then gives E[
φ
(d
k
)] ≤n(1−1/(2n))
k
.Using1−x ≤exp(−x),
after k = 2n((2Δ−1)ln(8n
2
)+ln(4n)) steps, E[
φ
(d
k
)] ≤ (1/4)(1/(8n
2
))
2Δ−1
,soby
Markov’s inequality, P(
φ
(d
k
) > (1/(8n
2
))
2Δ−1
) ≤ 1/4. But for any i, d
k
(i)
2Δ−1
≤
φ
(d
k
), which gives the result.
Lemma 6.6. Consider lines 5 through 7 o f Linear extension cftp.Ift≥
2n((2Δ −1)ln(8n
2
)+ln(4n)), then the probability that x
max
and x
min
are interwoven
at the next line is at least 1/2.
Proof. Start by supposing that x is uniform over C
LE
.Thenx
min
≤ x ≤ x
max
, and by
the previous lem ma after t ≥ 2n((2Δ −1)ln(8n
2
)+ln(4n)) steps the chance that any
coordinate of x
min
is farther than 1/(8n
2
) from a coordinate of x
max
is at most 1/4.
After this fixed number of steps, x is still uniform over C
LE
.Letp be the chance
that any two coordinates of x are closer together than 1/(4n
2
).
From our discussion of moving from the continuous state to the permutation state
back to the continuous state from earlier, we know the coordinates of x can be viewed
as the result of n independent uniforms drawn from [0 , 1].Fori = j, the chance that
|U
i
−U
j
|≤1/(4n
2
) ≤ 1/(2n
2
).Thereare
n
2
such i and j, so by the union bound,
p ≤ n(n −1)/(4n
2
) ≤ 1/4.
Suppose for all j, the distance from x
min
( j) to x
max
( j) is at most 1/(8n
2
) and
x
min
( j) ≤ x( j) ≤ x
max
( j). Suppose also that |x( j) −x( j
)| > 1/(4n
2
).Thenx
min
and
x
max
must be interwoven. See Figure 6.5 for an illustration.
To see this analytically, let i ∈{1,...,n −1}.Then
x
min
(
σ
(i + 1)) −x
max
(
σ
(i)) = a −b −c, where
a = x
min
(
σ
(i + 1)) −x(
σ
(i)), b = x(
σ
(i + 1)−x
max
(
σ
(i)), c = x
max
(
σ
(i)) −x(
σ
(i)).
USING CONTINUOUS STATE SPACES FOR PERMUTATIONS 119
x
min
(
σ
(i))
x(
σ
(i))
x
max
(
σ
(i)) x
min
(
σ
(i + 1))
x(
σ
(i + 1))
x
max
(
σ
(i + 1))
δ
1
δ
2
δ
3
Figure 6.5 If
δ
1
and
δ
2
are at most 1/(8n
2
), and
δ
3
> 1/(4n
2
),thenx
min
(
σ
(i + 1)) >
x
max
(
σ
(i)).
If a > 1/(4 n
2
), b ≤ 1/(8n
2
) and c ≤ 1/(8n
2
) for all i,thenx
min
(
σ
(i + 1)) >
x
max
(
σ
(i)) for all i, which makes the two vectors interwoven. By the union bound,
the probability that these inequ alities hold for a, b,c for all i is at least 1/2.
Since each step in this chain takes O(Δ) time, this gives an algorithm fo r gener-
ating perfect samples from height 2 posets in O(nΔ
2
ln(n)) time. In the worst case,
Δ = Θ(n), and this is no better than the bounding chain. However, for sparse graphs
(like lattices), Δ can be small or even fixed, which gives an O(n ln(n)) time algorithm.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.