Rapidly Mixing Chain and Perfect Sampler
for Logarithmic Separable Concave
Distributions on Simplex

Shuji Kijima*1 and Tomomi Matsui*2
Department of Mathematical Informatics,
Graduate School of Information Science and Technology,
University of Tokyo, Japan

*1: kijima@misojiro.t.u-tokyo.ac.jp*2: tomomi@mist.i.u-tokyo.ac.jp

2Problem
Giveneach fi is log-concave

log-concave functions vector f = (f1,..., fn)
Sample space

simplexΞ = ｛(x1,..., xn )∈Zn | xi ≥ 0, x1+ ‥+xn = K｝
Probability function

logarithmic separable
concave function

wherelog-concave function fifi : Z → R++ ( i ∈ {1,…,n}),2 ln fi (z+1) ≥ ln fi (z) + ln fi (z+2).

ex. of log-concave• exponential dist.,• normal dist.,• positive concave.

logarithmic separable concave function
product of single variable log-concave functions.

Main results3

For any logarithmic separable concave
discrete distribution on simplex,
we give two hit-and-run chains.
• One provides an approximate sampler.
¾ The mixing time τ(ε) satisfies¾ Proof by path coupling.
• The other provides a perfect sampler.
¾ The chain is monotone.
¾ The perfect sampler is based onmonotone CFTP (Coupling From The Past)⇒ Exactly according to the stationarydistribution.

Related works and applications
Related works• A. Frieze and R. Kannan (‘97)¾log-concave on continuous polytope⇒ polynomial time mixing• L. Lovasz and S. Vempara (‘02)¾log-concave on continuous polytope⇒ mixing time is O*(n4)• D. Randall and P. Winker (‘05)¾uniform on continuous simplex⇒ mixing time is Θ(n3 ln n)
Discrete is NOT easyApplications• Jackson networks• Discretized Dirichlet Distribution

4

5

An application- Jackson networks: Queueing network theory: job (customer)

How long should we wait?

: node (server)

Steady state distribution of jobs

with given positive constant vectors(θ1θ2,…,θn), (μ1,μ2,…,μn) and (s1s2,…,sn)6Another application- Discretized Dirichlet Distribution(u1, u2, u3) = (10, 20, 50)(u1, u2, u3) = (1, 2, 5)(u1, u2, u3) = (0.1, 0.2, 0.5)

mean =(1/8, 2/8, 5/8)

7Markov chain
Current state:• Chose a pair of indices, u. a. r.

• Set• Chosew. p.

• Set

i1= 3

i2= 5

X = (4,8,5,3,1,6)
k=6⋅⋅⋅ ⋅⋅⋅(4,8,0,3,6,6) ⋅⋅⋅ ⋅⋅⋅ (4,8,6,3,0,6)
chose one

8

Stationary distribution

Them.
The chain is ergodic and has a uniquestationary distribution which is π

Current state

n=3x3
K

Chose a line.
Transit to the next state.

Kx2
Kx1

9

Approximate sampler- Sampling via Markov chain

Basic idea
1: Start from an initial state
2: Make several transitions
3: Output a sample

Ξ: State Spacexxx・・・xxIf a chain is ergodic, it converges toa unique stationary distribution.

10Mixing time

Them. 1The mixing time τ(ε) of the chain satisfies

Total variation distance between μ and ν is defined byMixing time of a chain is defined byprob.

μνΩProof (by path coupling)11• Graph: G = (Ξ, E)• Edge: {X,Y} ∈ E⇔• Distance: dA (X,Y) shortest path between X and Y on G
• Joint process: (X,Y) |→ (X’,Y’) cumulative dist.

Claim

Proof: Let {X, Y}∈ E and {j1, j2} (j1 ≠ j2) be a supporting pair.
Suppose a pair {i1, i2} (i1 ≠ i2) is chosen.
Case 1. {i1, i2} ∩ {j1, j2} = ∅ (neither of j1, j2 are chosen)¾ dA(X ’, Y ’) = dA(X , Y ) ≡ 1
Case 2. {i1, i2} = {j1, j2} (both of j1, j2 are chosen)¾ dA(X ’, Y ’) = 0
Case 3. |{i1, i2} ∩ {j1, j2}| = 1 (exactly one of j1, j2 is chosen)¾ dA(X ’, Y ’) = dA(X , Y ) ≡ 1
Them. Path coupling [Bubley and Dyer ‘97]0 ≤ ∃β < 1, ∀{X, Y}∈ E, E[d (X ’, Y ’)] ≤ β ⋅ d(X , Y )⇒ τ(ε) ≤ (1– β )–1 ln (Dε –1).

12

Alternating inequalities
Joint process

Simulate the chain with random number λ ∈ [0,1)and cumulative distribution function

gijk(0)gijk(−1)fi(0) fj(k)————
A0

gijk(1)fi(1) fj(k−1)—————
A

gijk(k)gijk(k−1)··· ···

fi(k) fj(0)————
A··· ···

1

where A = ∑s=1k fi (s) fj (k − s) .

λLemmaA logarithmic separable concave function
satisfies alternating inequalities
for any k∈{0,…,K} and for any pair {i, j}.
gijk(0)gijk(−1)0fi(0) fj(k)————Afi(0) fj(k +1)
—————
A’

gijk+1(−1)

gijk(1)··· ···

fi(1) fj(k−1)—————
Afi(1) fj(k)————
A’

gijk+1(0)··· ···fi(2) fj(k−1)
—————
A’

gijk+1(1)gijk(k)gijk(k−1)··· ···

fi(k) fj(0)————A
fi(k+1) fj(0)
—————
A’

gijk+1(2) · · · · · · gijk+1(k)1

gijk+1(k+1)

Another chain - for perfect sampling
modificationconsecutive• Chose a pair of indices, u. a. r.

Them. 2The chain is monotone.

Equipments• Cumulative sum vector cx for x ∈ Ξ• Partial order on Ξ
• Max. and min.
Max.: xU = (K, 0, 0, …, 0, 0)
Min.: xL = (0, 0, 0, …, 0, K)• update function
cumulative distribution function

13

14

Cumulative sum vector
Examplex = ( 4, 11, 5, 3, 1, 6 )y = ( 4, 2, 2, 5, 11, 6 )30cx

15cy00Thus123456i

15monotone CFTP [Propp and Wilson ‘96]
monotone Markov chain¾ The state space of a chain has a poset.
¾ Any transitions preserve partial order¾ The poset has a unique max and min.
monotone CFTP
+1

–2

0

–2

λ+2

+1

s1

s1

s1

s1

s1

s1

s1

s2

s2

s2

s2

s3

s2

s2

s3

s3

s3

s3

s3

s3

s4

s4

s4

s4

s4

s4

s4

s5

s5

s5

s5

s5

s5

s5

–6

–5

–4

–3

–2

–10⋅ ⋅ ⋅ s3

outputperiodThem. monotone CFTP
monotone CFTP algorithm returns a sample
in probabilistic finite time, exactly
according to the stationary distribution.

Concluding remarks

16

Future works• Is the mixing time (or expectedcoalescence time) of our monotone chain
bounded by polynomial time?
• Extension to log-concave (not separable)¾ application: universal portfolio.
• Extension to integer points on moregeneral polytopes?
¾ application: loss networks.
¾ base polytope of submodular function.

Technical reports are available fromhttp://www.keisu.t.u-tokyo.ac.jp/Research/techrep.0.html