112 COALESCENCE ON CONTINUOUS AND UNBOUNDED STATE SPACES
As noted earlier, the reason such a chain is called reversible is because it looks
the same whether it is run in the forward or reverse direction.
Lemma 6.3. Suppose X
a
∼
π
for {X
t
}a reversible Markov chain. Then for any b > a,
(X
a
,X
a+1
,...,X
b
) ∼ (X
b
,X
b−1
,...,X
a
). (6.12)
Proof. Just use induction on b −a. The statement that (X
a
,X
a+1
) ∼(X
a+1
,X
a
) is just
reversibility. Applying reversibility b −a times gives the induction step.
Because the chain is reversible, it is easy to simulate in the reverse direction;
the updates are done in exactly the same way as forward updates. So for each t,set
D
t−1
=
φ
(D
t
,U
t−1
).
Now consider how to simulate uniforms for the forward chain conditioned on the
values of the dominating chain. Suppose D
i
= j and D
i+1
= j −1. Then the forward
move had to be down, and U
i
must lie in [0,2/3].SodrawU
i
as a uniform conditioned
to lie in [0, 2/3]. On the other hand, if D
i
= j and D
i+1
= j + 1, then the forward move
had to be up, so U
i
is uniform over (2/3,1].
Next, how can the original Vervaat perpetuity process be updated in order to
coalesce the continuity of possible states down to only a few states? Recall X
t+1
=
U
t+1
(1 + X
t
). Another way to state this is that [X
t+1
|X
t
] ∼ Unif([0, 1 + X
t
]).
This can be broken down into two pieces. If U ≤ 1/(1 + X
t
),thenU (1 + X
t
) ∼
Unif([0,1]). So generate a second uniform U
∼Unif([0,1]),andletX
t+1
be U
.Oth-
erwise, let X
t+1
be U(1 + X
t
) as before. This is encoded in the following update
function,
φ
(x,u, u
)=1(u ≤ 1/(1 + x))u
+ 1(u > 1/(1 + x))u(1 + x). (6.13)
Some things to note about this update function: For any values of u and u
in [0,1], this function is monotonic in x. Second, if X
t+1
=
φ
(X
t
,U
t+1
,U
t+1
),and
U
t+1
< 1/(1 + D
t
),thenX
t+1
= U
t+1
and is completely independent of the value of
X
t
. Coalescence has occurred! The result is the following algorithm:
Vervaat perpetuity dominated cftp
1) t ←−1, t
← 0, draw D
0
from P(D
0
= j )=(1/2)
j−4
1( j ∈{5,6,...})
2) cflag ← FALSE
3) Repeat
4) For k from t
−1tot
5) Draw C ← Bern(1/3)
6) D
k
← D
k+1
+C −(1 −C)1(D
k+1
> 5)
7) If D
k+1
> D
k
then draw U
k+1
← Unif((2/3 , 1])
8) If D
k+1
≤ D
k
then draw U
k+1
← Unif([0, 2/3])
9) U
k+1
← Unif([0,1])
10) X
t
← D
t
11) For k from t to −1
12) X
k+1
← 1(U
k+1
≤ 1/(1 + X
k
))U
k+1
+ 1(U
k+1
> 1/(1 + X
k
))(1 + X
k
)U
k+1
13) If X
k+1
≤ 1, then cflag ← TRUE
USING CONTINUOUS STATE SPACES FOR PERMUTATIONS 113
14) t
←t, t ←2t
15) Until cflag is true
6.8 Using continuous state spaces for permutations
Sometimes discrete spaces can be used to make continuous spaces coalesce faster.
In the other direction, sometimes use of a continuous space can simplify perfect
simulation for a discrete chain.
As an example of this, consider the set of permutations on n objects. In Sec-
tions 1.6.2 and 4.5, examples of distributions on the set of permutations were given.
In particular, for the linear extensions of a partial o rder (Section 4.4), bounding
chains were used to do CFTP because the discrete chain does not admit a monotonic
update function.
However, by embedding the set of permutations in a continuous space, it is pos-
sible to create a Markov chain with a monotonic update function!
For the set S
n
of permutations on n, objects, let C
n
be those vectors in [0, 1]
n
whose coordinates take on unique values. That is, C
n
= {x ∈ [0, 1]
n
: (∀i = j)(x(i) =
x( j))}. Then each vector in C
n
encodes a permutation in S
n
.
Definition 6.6. Let f
perm
: C
n
→ S
n
be the function f
perm
(x)=
σ
,where
σ
is the
unique permutation such that
x(
σ
(1)) < x(
σ
(2)) < x(
σ
(3)) < ···< x(
σ
(n)). (6.14)
For instance, f
perm
((0.23,0.14,0.75,0.60)) = (2,1,4 , 3). In fact, f
perm
maps into
the permutatio n (2,1, 4, 3) if and only if x(2) < x(1) < x(4) < x(3 ). An easy way to
read off the permutation from the vector is that
σ
(i)= j means that there are exactly
j components of x that are at most x (i).
Note that if a point X is chosen uniformly from C
n
, then from a symmetry argu-
ment it follows that for a ll
σ
, P( f
perm
=
σ
)=1/n!.
When
σ
is a lin ear extension of a poset, then
σ
(i) ≺
σ
( j) implies that i < j.In
the continuous space, this is the same as saying that if a ≺ b,thenx(a) < x(a).
Therefore, let
C
LE
= C
n
∩{x : (a ≺ b → x (a) < x (b))}. (6.15)
For
σ
a linear extension of a poset , the same symmetry argument as before
gives that for a draw Y ∼ Unif(C
LE
), P( f
perm
(Y )=
σ
)=1/Z,whereZ is the number
of linear extensions of the poset.
Note that it is easy to construc t either a Gibbs or Metropolis-Hastings style Harris
chain whose stationary distribution is uniform over C
LE
. For convenience o f notation,
create the dummy components x(0)=0andx(n + 1)=1, and assume 0 ≺ i ≺ n + 1
for all i ∈{1,...,n + 1}.
Then, for instance, you can choose I uniformly from {1,2,...,n}, and update
x(I) by choosing uniformly from the set of values such that x(I) remains in C
LE
.To
114 COALESCENCE ON CONTINUOUS AND UNBOUNDED STATE SPACES
be precise, choose x(I) uniformly from the interval [a,b],wherea = max
j≺i
{x( j)}},
and b = min
i≺j
{x( j)}.
Consider the componentwise partial order on elements of C
LE
where
(x(1),...,x(n)) (y(1),...,y(n)) if and only if x(i) ≤ y(i) for all i. By placing this
partial o rder on elements of C
LE
(not to be confused with the par tial or der that de-
fines the set of linear extensions), a m onotonic update function can be created. Note
that in the fact below, the update function is defined for all vectors in [0,1]
n
, not just
those that correspond to permutations.
Fact 6.6. Say that x
1
x
2
for x
1
and x
2
in [0,1]
n
if for all j ∈{1,2,...,n},
x
1
( j) ≤ x
2
( j).Forx∈ [0,1]
n
, and given i ∈{1,2,...,n} and u ∈ [0,1],leta(x)=
max
j≺i
{x( j)}and b(x)=mini ≺ j{x( j)}. Consider the update function y =
φ
(x,i,u)
defined as y( j)=x( j) for j = i, and y(i)=(b(x) −a(x))u + a (x).Then
φ
is a mono-
tonic update function.
Proof. Note for x
1
x
2
in [0,1]
n
,
a(x
1
)=max
j≺i
{x
1
( j)}≤max
j≺i
{x
2
( j)} = a(x
2
). (6.16)
Similarly b(x
1
) ≤ b(x
2
),andthatmakesy(i) smaller coming from x
1
than from x
2
.
Since for j = ix
1
( j) ≤ x
2
( j), the result immediately follows.
Therefore in principle, monotonic CFTP could be used on this chain starting
from the minimum state (0, 0,...,0) and maximal state (1,1,...,1). Note that neither
the minimum nor the maximal state actually correspond to permutations, but that is
not important! The only properties that are important is that they do bound any state
that does correspond to a permutation, and the chain being run is monotonic even
with these extra states added in to the state space.
As with other Gibbs sampler chains discussed earlier, th is chain started from
different states will never actually coalesce down to a single state. Th e re are two
ways to solve this problem. The first is to use the multishift coupling for uniforms
from earlier. With this approach, the update function will bring the continuous state
space down to a sin gle state.
But in this case, there is another approach. It is not necessary for this problem
for CFTP to return a single state from C
LE
as long as every state returned ma ps into
the same permutation. This uses the idea of interwoven vectors that was introduced
in [57].
Definition 6.7. Two vectors x
1
and x
2
in [0,1]
n
are in terwoven if for the permutation
σ
= f
perm
(x
1
),
x
1
(
σ
(1)) < x
2
(
σ
(1)) ≤ x
1
(
σ
(2)) < x
2
(
σ
(2)) ≤···≤x
1
(
σ
(n)) < x
2
(
σ
(n)). (6.17)
Figure 6 .4 (which was figure 1 of [57]) shows two interwoven vectors. The pur-
pose of interweaving is as follows: any vector trapped between two interwoven vec-
tors maps to the same permutation as the two original vector s.
USING CONTINUOUS STATE SPACES FOR PERMUTATIONS 115
0 1
r(1)r(2) r(3) r(4)
s(1)s(2) s(3) s(4)
Figure 6.4 Interwoven vectors: r =(0.25,0.1,0.6,0.75),s=(0.3,0.2,0.7, 0.9), and
σ
=
(2,1,3,4).
Lemma 6.4. Suppose x
1
x
2
are elements of C
LE
.Then(∀x ∈ C
LE
: x
1
≤ x ≤
x
2
)( f
perm
(x
1
)= f
perm
(x)= f
perm
(x
2
)) if and only if x
1
and x
2
are interwoven.
Proof. Suppose x
1
< x
2
are interwoven. Let x be a vector with distinct coordinates
satisfying x
1
x x
2
,andlet
σ
= f (x
1
).Then
x
1
(
σ
(1)) ≤ x(
σ
(1)) ≤ x
2
(
σ
(1)) ≤ x
1
(
σ
(2)) ≤···≤x
1
(
σ
(n)) ≤ x(
σ
(n)) ≤ x
2
(
σ
(n)).
Removing the x
1
and x
2
vectors from the above inequality and using the fact that
x ∈ C
LE
gives
x(
σ
(1)) < x(
σ
(2)) < ···< x(
σ
(n))
which implies that f
perm
(x)=
σ
.
Now for the other direction. Suppose x
1
< x
2
are not interwoven, and again let
σ
= f
perm
(x
1
). Then for all i it is true that x
1
(
σ
(i)) < x
2
(
σ
(i)).Sincex
1
and x
2
are not interwoven, there must be an i such that x
2
(
σ
(i)) > x
1
(
σ
(i + 1)). Let c
1
=
(2/3)x
1
(
σ
(i + 1)) + (1/3)x
2
(
σ
(i)) and c
2
=(1/3)x
1
(
σ
(i + 1)) + (2/3)x
2
(
σ
(i)) so
that x
1
(
σ
(i + 1)) < c
1
< c
2
< x
2
(
σ
(i)).
Now create two vectors x and y as follows. Let y(
σ
( j)) = x(
σ
( j)) = x
2
(
σ
( j))
for all j /∈{i,i + 1}.Letx(
σ
(i)) = c
1
,x(
σ
(i +1)) = c
2
and y(
σ
(i)) = c
2
and y(
σ
(i +
1)) = c
1
. Then both x and y are at least x
1
and at most x
2
,but f
perm
(x) = f
perm
(y) as
these permutations differ by a single transposition.
To use this with CFTP, consider a step that takes the state in C
LE
, generates a
permutatio n from that state, and then uses the permutation to generate a state in C
LE
.
This last part is straightforward. Given a permutation
σ
, generate uniformly from
the set of C
LE
that maps to
σ
by first generating n uniform points U
1
,...,U
n
in
[0,1],andfind the order statistics U
(1)
< U
(2)
< ···< U
(n)
(they will be distinct with
prob ability 1.) The state
(U
(
σ
(1))
,U
(
σ
(2))
,...,U
(
σ
(n))
) (6.18)
will be a uniform draw from the states in C
perm
that map to
σ
.
The pseudocode, then, for generating a partial order according to this method is
as follows. First consider the step inside the continuous space.
116 COALESCENCE ON CONTINUOUS AND UNBOUNDED STATE SPACES
Linear extension Gibbs step
Input: x ∈ C
LE
,u ∈ [0,1],i ∈{1,...,n}, Output: x
1) Let a be 0 if no elements precede i,ormax
j: j≺i
x( j) otherwise
2) Let b be 1 if i precedes no other elements, or min
j:i≺j
x( j) otherwise
3) x(i) ← a +(b −a)u
Next make a step that moves from the continuous state to a permutation, then
back to a continuous state.
Permutation step
Input: x ∈ C
LE
,(u
1
,...,u
n
) ∈ [0,1]
n
Output: x
1) For i ∈{1,...,n},let
σ
(i) ← #{j : x( j) ≤ x(i)}
2) Let (u
(1)
,...,u
(n)
be the order statistics of u
1
,...,u
n
3) For i ∈{1,...,n},letx(i) ← u
(
σ
(i))
Finally, use CFTP to generate a uniform draw from C
LE
.
Linear extension cftp Input: t Output: X
1) Draw U
1
,U
2
,...,U
t
iid Unif([0,1])
2) Draw I
1
,...,I
t
iid Unif({1,2,...,n})
3) Draw W
1
,W
2
,...,W
n
iid Unif([0, 1])
4) x
min
← (0, 0,...,0), x
max
← (1, 1,...,1)
5) For t
from 1 to t
6) x
max
← Linear extension Gibbs step(x
max
,U
t
,I
t
)
7) x
min
← Linear extension Gibbs step(x
min
,U
t
,I
t
)
8) If x
max
and x
min
are interwoven
9) x ← x
max
10) Else
11) x ← Linear
extension cftp(2t)
12) For t
from 1 to t
13) x ← Linear
extension Gibbs step(x,U
t
,I
t
)
14) x ← Permutation
step(x
max
,(W
1
,...,W
n
))
So why go to all this trouble, when the bounding chain approach of Section 4.4
is guaranteed to generate a sample in Θ(n
3
ln(n)) time? Recall that method requires
Θ(n
3
ln(n)) now matter how many precedence equations there are in the poset. Even
if there are no elements i and j with i ≺ j, it will still take on the order of n
3
ln(n)
steps. Call this example the empty poset.
Using the continuous approach on the empty poset, the above procedure will only
take Θ(n ln(n)) steps to finish, as the state will coalesce once every dimension has
been chosen, so the number of steps needed is exactly the coupon collector problem.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.