Analysis of the Diaconis-Holmes-Neal Markov Chain Sampler for Log Concave Probabilities

Martin Hildebrand

January 15, 2002

Abstract This paper considers an algorithm of Diaconis, Holmes, and Neal. This algorithm is defined in terms of a probability π on a set with n elements. This paper shows that, given ϵ > 0, a multiple of n steps suffice for this algorithm to reach a distribution within a variation distance ϵ from the stationary distribution provided that the probability π is log concave.

1 Introduction

Diaconis, Holmes, and Neal [1] introduced a variant of the Metropolis algorithm of Metropolis et al [4]. This variant is designed to overcome the slowness of the diffusion which the Metropolis algorithm can display and uses a non-reversible Markov chain. These algorithms involve a probability π on a set X = {1, …, n}. In [3], the author has considered the Diaconis-Holmes-Neal Markov chain for certain probabilities π such as when π is V-shaped. This paper considers cases where the probability π is log concave.

For the Diaconis-Holmes-Neal Markov chain, define X̃ to be {(ϵ, j)|j ∈ X and ϵ = ±1}. Assume throughout the paper that π(j) > 0 for j ∈ X and ∑_{j=1}^{n} π(j) = 1. Let π̃((ϵ, j)) = (1/2)π(j). The Diaconis-Holmes-Neal algorithm is as follows. Let θ ∈ (0, 1) be given; θ may depend on n. Suppose we start a step at a point (ϵ, j). Perform the step of the Markov chain by going through the following two substeps:

1. If j + ϵ ∉ X, stay at (ϵ, j). Otherwise go to (−ϵ, j + ϵ) with probability min(1, π(j + ϵ)/π(j)) and stay at (ϵ, j) otherwise.

2. After substep 1, suppose we are at (ϵ′, j′). With probability 1 − θ go to (−ϵ′, j′). Otherwise stay at (ϵ′, j′).

Precisely when the part of substep 2 with probability θ occurs, we say a flip occurs. In other words, flips occur if the Markov chain goes from (+1, j) to (−1, j + 1), from (−1, j) to (+1, j − 1), from (+1, j) to (+1, j), or from (−1, j) to (−1, j).

It can be shown that π̃ is the stationary probability for this Markov chain; indeed, Diaconis, Holmes, and Neal [1] indicate that both substeps leave π̃ invariant.

Suppose n ≥ 2 and that the probability π is also log concave, i.e. (π(j))^{2} ≥ π(j + 1)π(j − 1) for j = 2, …, n − 1. If P and Q are probabilities on X̃, recall the variation distance

∥P − Q∥ := \frac{1}{2} ∑_{s∈X̃} |P (s) − Q(s)|
= max_{A⊆X̃} |P (A) − Q(A)|.

The main result is Theorem 1 Suppose θ = 1/n. Let ϵ > 0 be given. There exists a constant c > 0 which does not depend on the log concave probability π such that if m > cn, then ∥P_{m}−π̃∥ < ϵ where P_{m} is the probability after m steps of the Diaconis-Holmes-Neal Markov chain started at any state in X̃.

2 Notation and Main Lemmmas

Define j_{max} so that π(j_{max}) ≥ π(j) for all j ∈ {1, …, n}. Let J := {(+1, j)|π(j) ≥ 0.1π(j_{max})}∪{(−1, j)|π(j) ≥ 0.1π(j_{max})}. Let j_{u} := max{j|(+1, j) ∈ J} and j_{d} := min{j|(+1, j) ∈ J}. Either j_{u} − j_{max} ≥ j_{max} − j_{d} or j_{max} − j_{d} > j_{u} − j_{max}. In the former case, let the base point B.P. be (+1, j_{max}) and its opposite be (−1, j_{max}); otherwise let the base point B.P. be (−1, j_{max}) and its opposite be (+1, j_{max}). Let w := j_{u} − j_{d} + 1. (w stands for width and tells how wide the set J is.)

Let X_{0} be the starting state of the Diaconis-Holmes-Neal Markov chain and X_{m} be the position after m steps of the Markov chain.

We may talk about paths P_{0} → P_{1} → … → P_{m}. When we talk about the probability of such a path, we mean P (X_{1} = P_{1}, …, X_{m} = P_{m}|X_{0} = P_{0}). Notation such as “given that the path starts at P_{0}” may be used to emphasize the starting condition X_{0} = P_{0}.

We shall use the following lemmas.

Lemma 1 There exists a constant c_{1} > 0 such that for all points P ∈ X̃,

∑_{m=0}^{2n} P (X_{m} = B.P. and X_{ℓ} ≠ B.P. if 0 ≤ ℓ < m|X_{0} = P) ≥ c_{1}.

Lemma 2 There exists a constant c_{2} > 0 such that for any constant c_{3} > 0, if 0 ≤ ℓ < c_{3}n, then P (there exists m ∈ {ℓ, ℓ + 1, …, ℓ + 4w − 1} such that X_{m} = B.P. and no flips occur in the first m steps |X_{0} = B.P., no flips occur in the first ℓ steps, and there are at least k values j in {1, …, ℓ − 1} such that X_{j} = B.P.) > c_{2} for any k where the condition is possible.

Lemma 3 If w > 3, there exists a constant c_{5} > 0 such that for at least max(j_{u} − j_{max}, j_{max} − j_{d}) consecutive odd integers m no more than 2w, P (X_{m} = B.P., exactly one flip occurs in the first m steps, and X_{j} ∈ J − {B.P.} if 0 < j < m|X_{0} = B.P.) ≥ c_{5}/n.

Proposition 1 If w ≤ 3, there exists a constant c_{5} > 0 (which satisfies Lemma 3) such that for at least 2 consecutive odd integers m no more than 2w+1, P (X_{m} = B.P., exactly one flip occurs in the first m steps, and X_{j} ∈ J −{B.P.} if 0 < j < m|X_{0} = B.P.) ≥ c_{5}/n.

Lemma 4 There exists a constant c_{6} > 0 such that for each j ∈ J,

∑_{m=0}^{2n} P (X_{m} = j, X_{ℓ} ≠ B.P. if 0 < ℓ ≤ m|X_{0} = B.P.) > c_{6}

Lemmas 2 and 3 (and Proposition 1) shall give us Lemma 5 There exists a constant c_{7} > 0 such that for each c_{8} > 0, there exists c_{9} > 0 such that

P (X_{m} = B.P.|X_{0} = B.P.) > c_{9}/w

for each m with c_{7}n ≤ m ≤ c_{8}n.

Lemmas 1, 4, and 5 combine to give the following lemma.

Lemma 6 Let m := ⌈(c_{7} + 5)n⌉. There exists a constant c_{10} > 0 such that for each P ∈ X̃ and j ∈ J,

P (X_{m} = j|X_{0} = P) > c_{10}/w.

3 Property Implied by the Log Concavity of π

The propositions in this section will be useful in proving some of the lemmas.

Proposition 2 If j ≥ j_{max} and j + w ≤ n, then π(j + w) ≤ (1/10)π(j).

Proof: Observe that π(j_{max} + w) ≤ (1/10)π(j_{max}) provided that j_{max} + w ≤ n. Thus it suffices to show

\frac{π(j + w)}{π(j)} ≥ \frac{π(j + k + w)}{π(j + k)}

if j ≥ 1, k ≥ 0, and j + k + w ≤ n. So it also suffices to show

ln(π(j + k)) − ln(π(j)) ≥ ln(π(j + k + w)) − ln(π(j + w))

for these j and k. We know that (π(ℓ))^{2} ≥ π(ℓ − 1)π(ℓ + 1) if 2 ≤ ℓ ≤ n − 1. So for such ℓ,

ln(π(ℓ)) − ln(π(ℓ − 1)) ≥ ln(π(ℓ + 1)) − ln(π(ℓ)).

By repeated use of this inequality, we get

ln(π(j + 1)) − ln(π(j)) ≥ ln(π(j + 1 + w)) − ln(π(j + w))
ln(π(j + 2)) − ln(π(j + 1)) ≥ ln(π(j + 2 + w)) − ln(π(j + 1 + w))
…
ln(π(j + k)) − ln(π(j + k − 1)) ≥ ln(π(j + k + w)) − ln(π(j + k − 1 + w))

Adding these terms together gives us

ln(π(j + k)) − ln(π(j)) ≥ ln(π(j + k + w)) − ln(π(j + w)).

♢

Similar arguments give the following proposition. Proposition 3 If j ≤ j_{max} and j − w ≥ 1, then π(j − w) ≤ (1/10)π(j).

4 Proof of Some Lemmas and Main Theorem from the Lemmas

First let’s prove Lemma 6 from Lemmas 1, 4, and 5.

P (X_{m} = j|X_{0} = P)
≥ ∑_{m_{1}=0}^{2n} ∑_{m_{2}=0}^{2n} P (X_{m_{1}} = B.P., X_{ℓ} ≠ B.P. if 0 ≤ ℓ < m_{1}|X_{0} = P)

×P (X_{m_{2}} = j, X_{ℓ} ≠ B.P. if 0 < ℓ ≤ m_{2}|X_{0} = B.P.)
×P (X_{m−m_{1}−m_{2}} = B.P.|X_{0} = B.P.)
> c_{1}c_{6}c_{9}/w

♢

The following lemma, combined with Lemma 6, gives Theorem 1. The lemma will use the following notation. Suppose p_{ij} is the transition matrix of a connected Markov chain on X := {1, …, N}. Let p_{ij}^{(m)} be the probability of going from state i to state j in exactly m steps. Let (p_{1}, …, p_{n}) be the stationary distribution for this Markov chain. Define probabilities Q_{i}^{(m)} and Q on X by Q_{i}^{(m)}(j) = p_{ij}^{(m)} and Q(j) = p_{j}.

Lemma 7 If there is a set J ⊆ X with |J| = N_{1} and

min_{1≤i≤N,j∈J} p_{ij}^{(m)} = δ > 0,

then ∥Q_{i}^{(ℓ)} − Q∥ ≤ (1 − N_{1}δ)^{⌊ℓ/m⌋}.

This lemma follows immediately from Theorem 16.2.4 of Meyn and Tweedie [5] with

ν_{m}^{(j)} = \{ \begin{matrix}δ & if j ∈ J \\ 0 & if j ∉ J. \end{matrix}

This lemma can also be proved with an adaptation of the argument on pages 173-174 of Doob [2].

Now let’s prove Lemma 5 from Lemmas 2 and 3 (and Proposition 1). We start with several propositions.

Proposition 4 Let X be a random variable giving the time it takes to return to B.P. if we start at B.P. and no flips occur before the return. Then

E(X) ≤ 2w + 4w (\frac{1}{10} + \frac{1}{10})

+6w (\frac{1}{100} + (\frac{1}{10})^{2} + \frac{1}{100})

+8w (\frac{1}{1000} + \frac{1}{100} \frac{1}{10} + \frac{1}{10} \frac{1}{100} + \frac{1}{1000}) + …

Note this proposition implies E(X) ≤ c_{11}w for some constant c_{11} > 0.

Proof of Proposition 4: We shall consider paths in X̃ from B.P. to B.P. with no flips and no intermediate returns to B.P. If the path stays in J, its length is no more than 2w. If the path leaves J only such that the second coordinate of points in the path goes inside [j_{d} − w, j_{d}) or only such that the second coordinate of points in the path goes inside (j_{u}, j_{u} + w] (but not both), the length may be as much as 4w. This corresponds to the second term as the probability the path goes below j_{d} is no more than 1/10 and the probability the path goes above j_{u} is no more than 1/10. The third term corresponds to paths where the second coordinate of the points on the path does one of the following three possibilities:

1. Goes inside [j_{d} − 2w, j_{d} − w) and stays inside [j_{d} − 2w, j_{u}].

2. Goes inside [j_{d} − w, j_{d}) and (j_{u}, j_{u} + w] and stays inside [j_{d} − w, j_{u} + w].

3. Goes inside (j_{u} + w, j_{u} + 2w] and stays inside [j_{d}, j_{u} + 2w]. The probability of each of these is no more than 1/100 by Propositions 2 and 3.

The remaining terms are similar. ♢ Remark: The multiples of w in the previous proposition are not

the smallest possible.

The following proposition will be used later.

Proposition 5 Let d be a positive integer, Let Y_{1}, …, Y_{d} be i.i.d. random variables with the same distribution as X in Proposition 4. Then P (Y_{1} + … + Y_{d} ≥ 5c_{11}dw) ≤ 1/5.

Proof: Use Markov’s Inequality. ♢ For the next proposition, let

f(ℓ) := \{ \begin{matrix}c_{5}/n & if ℓ ∈ \{1, 3, 5, …, 2 max(j_{u} − j_{max}, j_{max} − j_{d}) − 1\} and w > 3 \\ c_{5}/n & if ℓ ∈ \{1, 3\} and w ≤ 3 \\ 0 & otherwise \end{matrix}

Proposition 6 There exist positive integer constants c_{12} (odd) and c_{13} (even) such that there exists a constant c_{14} > 0 such that for at least 2w consecutive odd integers m,

∑_{ℓ_{1},...,ℓ_{c_{12}}:ℓ_{1}+...+ℓ_{c_{12}}=m} f(ℓ_{1}) … f(ℓ_{c_{12}}) ≥ c_{14} \frac{w^{c_{12}−1}}{n^{c_{12}}}

and for at least 2w consecutive even integers m,

∑_{ℓ_{1},...,ℓ_{c_{13}}:ℓ_{1}+...+ℓ_{c_{13}}=m} f(ℓ_{1}) … f(ℓ_{c_{13}}) ≥ c_{14} \frac{w^{c_{13}−1}}{n^{c_{13}}}

Proof: First off, note that if f is non-zero on b consecutive odd integers, then

∑_{ℓ_{1},...,ℓ_{c}:ℓ_{1}+...+ℓ_{c}=m} f(ℓ_{1}) … f(ℓ_{c})

is non-zero for cb − (c − 1) consecutive odd integers m if c is odd and cb−(c−1) consecutive even integers m if c is even. Note that if c ≥ 9 and b ≥ 2, then cb−(c−1) ≥ 10 ≥ 2w if w ≤ 5. Furthermore, if w ≥ 6, then b ≥ w/2 for even w and b ≥ (w − 1)/2 ≥ (3/7)w for odd w. Thus cb − (c − 1) ≥ (27/7)w − 8 if w ≥ 6 and c ≥ 9. Note that (27/7)w − 8 ≥ 2w if and only if (13/7)w ≥ 8. This is satisfied if w ≥ 6.

Now suppose w ≥ 100. Observe that \frac{0.5w}{10} ≥ 5. By Proposition 7 below, if c = 9 or c = 10, there will be at least 2w consecutive odd or even (respectively) integers m with at least

⌊\frac{0.5w}{10}⌋^{c−1} ≥ (\frac{4}{5} \frac{0.5w}{10} )^{c−1}

different choices for ℓ_{1}, …, ℓ_{c} summing to m with f(ℓ_{1}) … f(ℓ_{c}) = (c_{5}/n)^{c}. This implies the proposition for w ≥ 100 (where c_{12} = 9 and c_{13} = 10.) For these values of c_{12} and c_{13}, the rest of the proposition is implied by the 2w (or more) consecutive odd or even integer values m where the sum is non-zero. ♢

Proposition 7 If w ≥ 100 and either c = 9 or c = 10, there will be at least 2w consecutive odd (if c = 9) or even (if c = 10) integers m with at least

⌊\frac{0.5w}{10}⌋^{c−1}

different choices for ℓ_{1}, …, ℓ_{c} summing to m with f(ℓ_{1}) … f(ℓ_{c}) ≠ 0.

Proof: We shall consider the case c = 9 and m is odd; the case c = 10 and m is even is similar.

By arguments in the proof of Proposition 6, there are at least 9b − 8 consecutive odd integers m so that

∑_{ℓ_{1},...,ℓ_{c}:ℓ_{1}+...+ℓ_{c}=m} f(ℓ_{1}) … f(ℓ_{c})

is non-zero where b is as in that proof. Note that the first b − 1 such values are (c − 1)1 + 1, (c − 1)1 + 3, …, (c − 1)1 + (2b − 3) and the last b − 1 such values are (c − 1)(2b − 1) + 3, …, (c − 1)(2b − 1) + (2b − 3), (c − 1)(2b − 1) + (2b − 1). It suffices to show that if m is one of these consecutive odd integers but is not one of the first b − 1 or last b − 1 of them, then there are at least ⌊0.5w/10⌋^{c−1} choices of ℓ_{1}, …, ℓ_{c} summing to m with f(ℓ_{1}) … f(ℓ_{c}) ≠ 0. For such an integer m, choose ℓ_{c} as large as possible so that f(ℓ_{1}) … f(ℓ_{c}) ≠ 0 with ℓ_{1}+…+ℓ_{c} = m, and choose the remaining values ℓ_{1}, …, ℓ_{c−1} as evenly as possible. In fact, ℓ_{c} = 2b − 1 since m is not one of the first b − 1 of the consecutive odd integers described earlier. There exists an odd integer a in {1, …, 2b − 3} such that each of ℓ_{1}, …, ℓ_{c−1} is either a or a + 2 and at least one of ℓ_{1}, …, ℓ_{c−1} is a. Let a(i) for i = 1, …, c − 1 be this value of ℓ_{i}.

Now consider the following possible choices for ℓ_{1}, …, ℓ_{c−1}. Let ℓ_{i} be a(i) + 2b(i) where b(i) is in {0, 1, …, ⌊0.5w/10⌋ − 1}. For each of these choices, let ℓ_{c} = m − (ℓ_{1} + … + ℓ_{c−1}). Note that m − ∑_{i=1}^{c−1} a(i) = 2b − 1; so all these choices have ℓ_{c} ≤ 2b − 1. Furthermore ℓ_{c} ≥ 1 since

m − ∑_{i=1}^{c−1}(a(i) + 2b(i)) ≥ m − ∑_{i=1}^{c−1} a(i) − 2(c − 1)(⌊0.5w/10⌋ − 1)
> (2b − 1) − w + 2(c − 1)
≥ (w − 1) − 1 − w + 2(c − 1)
≥ 1.

Furthermore, observe that a(i) + 2b(i) must be less than or equal to 2b − 1. To see this, observe that

m − (c − 1) max_{i=1}^{c−1}(a(i) + 2b(i))

≥ m − ∑_{i=1}^{c−1} a(i) − 2(c − 1)(⌊0.5w/10⌋ − 1) − 2(c − 2)
> (2b − 1) − w + 2(c − 1) − 2(c − 2)
≥ w − 1 − 1 − w + 2 = 0.

So choosing ℓ_{1}, …, ℓ_{c−1} to be max_{i=1}^{c−1} a(i) + 2(⌊0.5w/10⌋ − 1) gives a positive ℓ_{c} with ℓ_{1} + … + ℓ_{c} = m. Since m is not one of the last b − 1 consecutive integers described earlier, this common value of ℓ_{1}, …, ℓ_{c−1} is no more than 2b − 1.

Finally note that we have at least 7b−6 consecutive odd integers m with the desired property and that 7b − 6 ≥ 3w − 6 > 2w when w ≥ 100. ♢

Now let’s prove Lemma 5.

Suppose the value d (as in Proposition 5) is ⌈2 max(c_{12}, c_{13})n/w⌉. Consider a path which has no flips but returns to B.P. at least d times. There are \binom{d}{c_{12}} ways to choose c_{12} of the first d returns.

We shall consider concatenations of paths. The concatenation of the paths P_{0} → P_{1} → … → P_{j−1} → P_{j} and P_{j} → P_{j+1} → … → P_{k−1} → P_{k} is the path P_{0} → P_{1} → … → P_{j−1} → P_{j} → P_{j+1} → … → P_{k−1} → P_{k}. Observe that if p_{1} is the probability the path P_{0} → P_{1} → … P_{j−1} → P_{j} is followed (given a start at P_{0}) and p_{2} is the probability that P_{j} → P_{j+1} → … → P_{k−1} → P_{k} is followed (given a start at P_{j}), then p_{1}p_{2} is the probability that the concatenation of these paths is followed (given a start at P_{0}).

There are 2w consecutive odd integers o such that the probability of getting a path of length o which is the concatenation of c_{12} paths from B.P. to B.P. with 1 flip and no intermediate return to B.P. is at least c_{14}w^{c_{12}−1}/n^{c_{12}}. To see this, use Lemma 3 and Proposition 1 as well as Proposition 6. In particular, in the case w > 3, let a be the smallest of max(j_{u} − j_{max}, j_{max} − j_{d}) consecutive odd integers m from Lemma 3. The probability of getting a path of length o which is the concatenation of c_{12} paths from B.P. to B.P. with exactly one flip and no intermediate return to B.P. is at least

∑_{ℓ_{1},...,ℓ_{c_{12}}:ℓ_{1}+...+ℓ_{c_{12}}=o−c_{12}(a−1)} f(ℓ_{1}) … f(ℓ_{c_{12}}),

which is at least c_{14}w^{c_{12}−1}/n^{c_{12}} for at least 2w consecutive odd o. The case w ≤ 3 is similar.

A similar statement using c_{13} applies for 2w consecutive even integers.

Let r be the largest of the 2w consecutive odd integers and the 2w consecutive even integers. Suppose m > 5c_{11}dw +r but m ≤ c_{8}n for some c_{8} > 0. We shall examine the case where j is odd; the case where j is even is similar. Let the 2w consecutive odd integers be s + 1, …, s + 4w − 1. Then P (there exists m ∈ {j − s − 4w + 1, …, j − s − 1} such that X_{m} = B.P., no flip occurs in the first m steps, and there are at least d returns to B.P. in the first j − s − 4w steps|X_{0} = B.P.) ≥ c_{2}(1 − (1/n))^{c_{8}n}(4/5). At the c_{12} of the first d returns to B.P., we shall insert a path from B.P. to B.P. with one flip and no intermediate return to B.P. For example, inserting the path B.P. → A_{1} → … → A_{a} → B.P. into the path B.P. → B_{1} → … → B_{b} → B.P. → C_{1} → … → C_{c} → B.P. → D_{1} → … → D_{d} → B.P. at the first return to B.P. gives the path B.P. → B_{1} → … → B_{b} → B.P. → A_{1} → … → A_{a} → B.P. → C_{1} → … → C_{c} → B.P. → D_{1} → … → D_{d} → B.P. Note that if p_{1} is the probability the path B.P. → A_{1} → … → A_{a} → B.P. is followed (given a start at B.P.) and p_{2} is the probability that the path B.P. → B_{1} → … → B_{b} → B.P. → C_{1} → … → C_{c} → B.P. → D_{1} → … → D_{d} → B.P. is followed (given a start at B.P.), then p_{1}p_{2} is the probability that the path B.P. → B_{1} → … → B_{b} → B.P. → A_{1} → … → A_{a} → B.P. → C_{1} → … → C_{c} → B.P. → D_{1} → … → D_{d} → B.P. is followed (given a start at B.P.).

Considering cases where the sum of the lengths of the inserted paths is one of the 2w consecutive odd integers, we get for odd m

P (X_{m} = B.P.|X_{0} = B.P.) ≥ \binom{d}{c_{12}}c_{2} (1 − \frac{1}{n})^{c_{8}n} \frac{4}{5}c_{14} \frac{w^{c_{12}−1}}{n^{c_{12}}}

By choosing c_{7} appropriately, we can get the requirement that if m ≥ c_{7}n, then m > 5c_{11}dw + r since r ≤ max(c_{12}(2w + 1), c_{13}(2w + 1)) ≤ 3n max(c_{12}, c_{13}). Note that

\binom{d}{c_{12}} ≥ \frac{1}{c_{12}!}(d − c_{12})^{c_{12}}
≥ \frac{1}{c_{12}!} (c_{12} (\frac{2n}{w} − 1))^{c_{12}}
≥ \frac{1}{c_{12}!}c_{12}^{c_{12}} (\frac{n}{w} )^{c_{12}}

This gives the lemma for odd m, and similar arguments apply for even m using c_{13} in place of c_{12}.

♢

5 Proof of Lemma 2

Suppose we are given that the last visit to B.P. before time ℓ occurs at time ℓ − b, and suppose that we know X_{0}, …, X_{ℓ−b}. Let X be as

[figure: …; …; …; (+1, 1); (−1, 1); (+1, L); (−1, L); (+1, L + 1); (−1, L + 1); (+1, R − 1); (−1, R − 1); (+1, R); (−1, R); (+1, n); (−1, n)]

Figure 1: Illustration of Turnaround Values L and R

in Proposition 4. We wish to show there exists a constant c_{15} < 1 such that P (X ≥ b + 4w|X ≥ b) ≤ c_{15}. (Without loss of generality, we may assume b is even since X is even.) Then choose a positive value c_{2} so that

c_{2} ≤ min_{n=2}^{∞}(1 − c_{15}) (1 − \frac{1}{n})^{4n} .

Paths from B.P. to B.P. with no flips or intermediate returns to B.P. have lengths with distribution given by X.

Such a path has a left turnaround value L and a right turnaround value R; the path goes from (−1, L) to (+1, L) and from (+1, R) to (−1, R). (See Figure 1.)

There are 3 cases to consider for paths of length at least b + 4w:

1. Its left turnaround is also a left turnaround for some path of length b.

2. Its right turnaround is also a right turnaround for some path of length b.

3. Neither case 1 nor 2 Note that cases 1 and 2 overlap. In case 3, the left turnaround is to the left of left turnarounds for all paths of length b and the right turnaround is to the right of right turnarounds for all paths of length b.

In case 1, the probability that the path has length at least b+4w and left turnaround L is at most (1/10)^{2} times the probability that the path has length at least b and left turnaround L. To see this, note that for such a path to have length at least b, the right turnaround must be at or to the right of the right turnaround of the path of length b while for such a path to have length at least b+4w, the right turnaround must be at least 2w to the right of the right turnaround of the path of length b. Proposition 2 (and the fact that the right turnaround is at least j_{max}) gives us this probability.

Case 2 is similar.

For case 3, let P be a path of length b. The probability that a path has length at least b+4w and turnarounds “outside” those of P is no more than the probability that the path has left turnaround at least w to the left of the left turnaround of P and right turnaround at or to the right of the right turnaround of P plus the probability that the path has right turnaround at least w to the right of the right turnaround of P and left turnaround at or to the left of the left turnaround of P. By propositions 2 and 3, each of the probabilities in this sum is no more than (1/10) times the probability that the path has length at least b, left turnaround at or to the left of the left turnaround of P, and right turnaround at or to the right of the right turnaround of P.

Thus

P (X ≥ b + 4w) ≤ (\frac{1}{100} + \frac{1}{100} + \frac{2}{10}) P (X ≥ b)

♢

6 Proof of Lemma 3 and Proposition 1

First let’s prove the proposition (except for the fact that the value can be chosen to also satisfy the lemma). If w = 1, the probability of going on one step from B.P. to B.P. (with a flip) is at least 0.9/n while the probability that X_{1} and X_{2} are both the opposite of B.P. and X_{3} = B.P. given that X_{0} = B.P. is at least (0.9^{3}/n)(1 − 1/n)^{2}.

If w = 2, then without loss of generality, assume B.P. is (+1, j_{d}). The paths (+1, j_{d}) → (−1, j_{u}) → (−1, j_{d}) → (+1, j_{d}) and (+1, j_{d}) → (+1, j_{u}) → (+1, j_{u}) → (−1, j_{u}) → (−1, j_{d}) → (+1, j_{d}) give the desired probabilities. Note that by log concavity π(j_{u} + 1)/π(j_{u}) ≤ π(j_{u})/π(j_{d}) while π(j_{u} + 1)/π(j_{d}) < 1/10. Thus π(j_{u} + 1)/π(j_{u}) < 1/\sqrt{10}, and this fact is useful for verifying that the second path has the desired property.

If w = 3, then without loss of generality, assume B.P. is either (+1, j_{d}) or (+1, j_{d} + 1). In the former case, the paths (+1, j_{d}) → (−1, j_{d} + 1) → (−1, j_{d}) → (+1, j_{d}) and (+1, j_{d}) → (+1, j_{d} + 1) → (−1, j_{u}) → (−1, j_{d} + 1) → (−1, j_{d}) → (+1, j_{d}) give the desired probabilities. In the latter case, consider paths (+1, j_{d} + 1) → (−1, j_{u}) → (−1, j_{d} + 1) → (−1, j_{d}) → (+1, j_{d}) → (+1, j_{d} + 1) and (+1, j_{d} + 1) → (+1, j_{u}) → (+1, j_{u}) → (−1, j_{u}) → (−1, j_{d} + 1) → (−1, j_{d}) → (+1, j_{d}) → (+1, j_{d} + 1) give the desired probabilities. Note that for the case B.P. = (+1, j_{d} + 1) we use the fact that π(j_{d})/π(j_{d} + 1) ≥ 1/10, that π(j_{d} − 1)/π(j_{d}) < 1/\sqrt{10}, and that again π(j_{u} + 1)/π(j_{u}) < 1/\sqrt{10}.

♢

Now let’s prove Lemma 3. Assume that we are in the case B.P. = (+1, j_{max}); the other case is similar.

We shall look at the case where there is one flip between B.P. and its opposite. Consider paths (+1, j_{max}) → (−1, j_{max} + 1) → (−1, j_{max}), (+1, j_{max}) → (+1, j_{max} + 1) → (−1, j_{max} + 2) → (−1, j_{max} + 1) → (−1, j_{max}), ..., (+1, j_{max}) → … (+1, j_{u} − 1) → (−1, j_{u}) → … → (−1, j_{max}) There are j_{u} − j_{max} such paths, and each occur with probability at least

0.1\frac{1}{n} min_{n=2}^{∞} (1 − \frac{1}{n})^{2n}

which is at least c_{17}/n for some constant c_{17} > 0.

Now let’s consider going from the opposite back to B.P. without a flip. Let p_{1} be the probability of going in 1 step, p_{3} be the probability of going in 3 steps, etc. Observe

p_{1} + p_{3} + … + p_{2(j_{max}−j_{d}+1)−1} ≥ (0.9) (1 − \frac{1}{n})^{2n}

Let p_{b} := min_{n=2}^{∞} 0.9(1 − (1/n))^{2n}. If p_{1} ≥ (1/3)p_{b}, then the paths with one flip from B.P. to its opposite and the one step return from the opposite to B.P. have the desired probabilities. Otherwise p_{3} +…+p_{2(j_{max}−j_{d})+1} ≥ (2/3)p_{b}. The probability of going from B.P. to B.P. with one flip in exactly 5 steps is at least p_{3}c_{17}/n, in exactly 7 steps is at least (p_{3} + p_{5})c_{17}/n, etc. For odd number of steps from 2(j_{max} −j_{d})+3 through 2(j_{u} −j_{max})+3 (inclusive), the probabilities will be at least (p_{3}+p_{5}+…+p_{2(j_{max}−j_{d})+1})(c_{17}/n). For 2(j_{u}−j_{max})+5 steps, the probability is at least (p_{5} + … + p_{2(j_{max}−j_{d})+1})(c_{17}/n). For 2(j_{max} − j_{d}) + 1 + 2(j_{u} − j_{max}) steps, the probability is at least p_{2(j_{max}−j_{d})+1}(c_{17}/n).

Let v be the smallest value so that p_{3} + … + p_{v} ≥ (1/3)p_{b}. All terms (p_{3}+…+p_{v})(c_{17}/n) through (p_{v}+…+p_{2(j_{max}−j_{d})+1})(c_{17}/n) are at least (1/3)p_{b}(c_{17}/n), and these correspond to j_{u}−j_{max} consecutive odd values of m with the desired probabilities. ♢

7 Proof of Lemma 1

We shall consider the case where B.P. is of the form (+1, j_{max}); the other case is similar. We shall show that if there are no flips, the Markov chain will reach B.P. within 2n steps.

If P = (+1, j) with j ≤ j_{max}, then unless a flip comes up, the Markov chain must go along the path (+1, j) → (+1, j +1) → … → (+1, j_{max}).

If P = (+1, j) with j > j_{max}, then if there are no flips, the path will go to some point (+1, j_{1}) with j_{1} ≥ j and on the next step to (−1, j_{1}). Later, assuming there still are no flips, the path will reach some point (−1, j_{2}) with j_{2} ≤ j_{max} and on the next step go to (+1, j_{2}). Then, assuming there are no flips, the path will go step by step until it reaches (+1, j_{max}).

If P = (−1, j), then if there are no flips, the path will go to some point (−1, j_{2}) with j_{2} ≤ j_{max} and on the next step go to (+1, j_{2}). Then, assuming there are no flips, the path will go step by step until it reaches (+1, j_{max}).

In each case, the number of steps to reach (+1, j_{max}) is at most 2n (assuming no flips). The lemma follows. ♢

8 Proof of Lemma 4

We shall consider the case where B.P. = (+1, j_{max}); the other case is similar.

In all cases below, we condition on no flips occuring in the first 2n steps; this occurs with probability at least a positive constant. Given this condition, the probability of reaching j before returning to B.P. is at least 1/10.

If j = (+1, j_{0}) with j_{0} ≥ j_{max}, then consider the path (+1, j_{max}) → (+1, j_{max} + 1) → … → (+1, j_{0}). This occurs with probability at least 1/10.

If j = (−1, j_{0}) with j_{0} ≥ j_{max}, then with probability at least 1/10, the path will go from (+1, j_{max}) to some point (+1, j_{1}) with j_{1} ≥ j_{0} and then to (−1, j_{1}) on the next step. Then it will go to j.

If j = (−1, j_{0}) with j_{0} < j_{max}, then the path will go from (+1, j_{max}) to some point (+1, j_{1}) with j_{1} ≥ j_{max} and then to (−1, j_{1}) on the next step. With probability at least 1/10, the path will then go on to j.

If j = (+1, j_{0}) with j_{0} < j_{max}, then the path will go from (+1, j_{max}) to some point (+1, j_{1}) with j_{1} ≥ j_{max} and then to (−1, j_{1}) on the next step. With probability at least 1/10, the path will then go on to some point (−1, j_{2}) with j_{2} ≤ j_{0} and then on the next step go to (+1, j_{2}). From there the path will go to j.

Note that in each case, the paths have length no more than 2n. ♢

9 Problem for Further Study

A problem for further study is to see if results similar to Theorem 1 occur for any unimodal probability π. Recall that π is said to be unimodal if there exists a k such that π(1) ≤ π(2) ≤ … ≤ π(k) ≥ π(k + 1) ≥ … ≥ π(n). Since π is assumed to be positive, if π is log concave, then it is readily shown to also be unimodal.

10 Acknowledgments

The author thanks an associate editor of the Annals of Applied Probability for a suggestion to consider log concave distributions and various people, especially Tim Lance, for encouragement during some trying times when this research was being undertaken.

References

[1] Diaconis, P., Holmes, S., and Neal, R. (2000). Analysis of a nonreversible Markov chain sampler, Ann. Appl. Prob. 10, 726-752.

[2] Doob, J.L. (1953). Stochastic Processes. New York: John Wiley and Sons.

[3] Hildebrand, M. Rates of convergence of the Diaconis-Holmes-Neal Markov chain sampler. Preprint.

[4] Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. (1953) Equations of state calculations by fast computing machines, J. Chem. Phys. 21, 1087-1092.

[5] Meyn, S.P., and Tweedie, R.L. (1993) Markov Chains and Stochastic Stability. New York: Springer-Verlag.