2008 1 8–11 1 “52 77 , 1990 New York Times [9]:  “In Shuffling Cards, 7 Is Winning Number”. 7 , 52 ) , P. Diaconis (Stanford Harvard , "The mathematical proof, discovered after studies of results from . elaborate computer calculations and careful observation of card games, confirms the intuition of many gamblers, bridge enthusiasts and casual players that most shuffling is inadequate." riffle shuffle Diaconis . , 52! Markov , , . ,
,
cut-off
2
1
X
= P(X ∈ A),    A ∈ S,
px ∈ P(S) 2.1. Ω = [0, 1], F = B([0, 1]), P    [0, 1]        Lebesuge (Ω, F, P) , B([0, 1])     [0, 1]         Borel σ .  X 1 (ω) = ω, X 2 (ω) = 1 − ω, X 3 (ω) = . pX1, pX2, pX3 S 1 – | 2ω – 1 | S = [0, 1] .  Lebsgue 2.3 ( , X ≒ Y
2.4 (
[0, 1]
X , f : RanX → R
X
.

3
Markov
S , S Markov T (
, x E S S' Markov , Markov 3.1.  S = {1,2,3,4} . , S 1 P T y (x,y ∈ S) ( x, y ) .  4 × 4
1: 3.1 (
Ax E S,
P(x,y) ≥ 0,   ∀x,y ∈ S, P
P(x,●) T P 3.1. 1
1
: 1 ). S { X t } t =0,1,2,... S 3.2 ( P = (P(x,y))x,yES 3.1. μ ∈ P(S) {Xt}t=0,1,2,... 3 S' 1. X 0 μ . pXo = μ. 2. t ≥ 0, x, y, x 0, . . . , x t − 1 ∈ S           , P( X t +1 = y | X 0 = x 0, X 1 = x 1, . . . , X t − 1 = xt-1, Xt = x) = P(x,y). 3.3 (Markov Markov ( Markov
3.1.
Markov
, S = V 3.3 (Simple Random Walk on a Graph). G = (V, E) deg( x ) =     x
P = (P(x,y)) simple random walk (SRW)
. . Markov 2:  |S| = 4 SRW Markov 3.4 (Simple Random Walk on Hypercube). S = {0,1}"      , ρ : S × S → R , ρ(x, y) = !{1 ≤ i ≤ n : x i ≠ yi}. x = (x 1 , x 2 , . . . , x n ), y = (y 1 , y 2 , . . . , y n ) ∈ S ′ . . n = 4 , Hamming , (S, ρ) ρ(x,y) = 1         , xy ∈ E ( ) hypercube x = (x1, x2, . . . , xn)
1. 1/n i 2. i , x ε → 1 − x ε SRW 3.5 (Markov Chain on q-coloring). G = (V, E) , x xy ∈ E y x ～ y c ∈ S [q] = {1, 2, . . . ,q} : c(x) ≠ c(y), x ~ y} , q . x, y ∈ V , S = {c : V → proper c
v G proper Markov 3.2 (Chapman-Kolmogorov ). (Xt,Pz) Markov
∀ x, y ∈ S, ∀ t ≥ 0. Chapman-Kolmogorov x, y ∈ S
●
4
Markov
, Markov 4.1
x ∈ S , π
4.2 S Markov P = (P(x,y)) 4.3 ( ). t > 0 x,y ∈ S , Pt(x,y) > 0 , Markov . 4.2. 5 S = {1,2,3} . Markov 1 5: 4.3 (Random Knight Move).  S Markov (   )     1 500 ( (8 × 8 ）     , .  ). 2 , Markov 4.4 (     )  x ∈ S             , Per(x) = {t ≥ 1 : Pt(x,x) > 0}       , dz = G.C.D(Per(x)) (G.C.D ) x 4.2. Markov d x ≡ 1 d x     x , SRW 4.4 (Simple Random Walk on Z n ). Z n = {0, 1, . . . , n − 1} (modulo n ) i ∈ Zn        , i → i + 1 → i ● n , i → i + 1 → · · → i − 1 → i   , n 1, ● n (
, 2 
. V = { G = (V, E) 4.5. 8 x ∈ V 3 d x . , - 7: Zn 8: 4.4
, Markov version Markov 4.5 (Lazy Version Markov Chain). x ∈ V T G = (V, E) 2い1
Markov Markov lazy version
) Plazy P元
Plazy 77 1911
9: Lazy version
Markov lazy version lazy P Markov 4.3.
T x
T
S [6, Theorem 1.8.2] . 4.1. x ∈ S 1 A A C S
π(y)
, Markov (X t , P z )
5
μ ∈ P(S × S)
fu T 5.1 ( μ1 8 μ2) (μ 1 & μ 2 )( x, y ) = μ 1 (x)μ 2 (x),    x, y ∈ S. 5.1. μι,μ2 ∈ P(S) PX = μ 1 , PY = μ 2 (
( μ 1 , μ 2 )
P(X = x)P(Y = y) 5.2 ( (X,Y) (μ, μ)
μ(i,j) = P(X = i,Y = j),   i,j = 0,1,
( 1
2ラー B

10
). S = {0,1}     , S Х ~ μ, Y ~ μ), 6
(total variation)
6.1. μ   ν    S
6.1. 0 ≤ ∥ • ∥ τν ≤ 1 6.1. (6.1)
(6.3) A . S (6.2) μ(Α) − ν(Α) = μ(Α ∩ Β) − ν(Α ∩ Β) + μ(Α ∩ Β c ) – ν(Α ∩ Β c ) μ(Α) − ν(Α) ≤ μ(Α∩ Β) − ν(Α∩ Β) ≤ μ(Β) − ν(Β). μ V
, A
μ(A) − ν(A) = P ×(A) − P ×(A) = P(X ∈ A) − P(Y ∈ A) = P(X ∈ A,Y ∈ Ac) + P(X ∈ A,Y ∈ A) − P(Y ∈ A) ≤ P(X ∈ A,Y ∈ Ac) < P(X ≠ Y).
11
, max ACS |μ(A) − ν(A)| ≤ P(X ≠ Y)           . ||µ − ν||τν ≤ inf{P(X ≠ Y) : X ～ µ,Y ～ ν}
, S 71, 72, 73
p Y

7
, Markov
r δ
Pr = δΠ + (1 − δ)Q Π( x, y ) = π( y )
Q РП = ПР = П, QП = П, П² = П
pi
x
□ 7.1. Markov version
8 S'
Pr (x,y) ≥ δπ(y) 8.1. t = 0,1,2,...
8.1. 1.  0 ≤ ∥ • ∥ TV ≤ 1 8.3). (
t 2. Pt (x,●)
Markov
汗t 8.2 ( ). 0 < c ≤ 1 t mix(c) = inf { t ≥ 0 : d(t) ≤ c}, tmix = tmix(1/4) (mixing time) t mix . 8.2. 1. n Markov n " si , 0 < ε < 1/2 2. tmix c tmix(c) . | Sn | n t (n)
t mix S n Markov t (n)
t mix . n → ∞ 8.1. n hypercube S n = {0, 1} n n , n . ,
1p.20 9.1 lazy simple random walk ¹ , d(t) cut-off t (n)
t mix = O(n log n) 8.1. d,d
π = πPt
ທ x ∈ S || Pt (x, ●) − Pt (y, ●)|| TV ≤ || Pt (x, ●) − π || TV + || Pt (y, ●) − π || TV x, y ∈ S
8.2. d,d
. x ∈ S
y
. μ ∈ P(S)
8.3. μ,ν ∈ P(S) ||μP — νP||τν ≤ ||μ — ν||τν d(t), d(t)
8.1.  d .  Chapman-Kolmogorov
8.2.  0 < ε < 1/2 tmix(c) ≤ [log₂ c−1] tmix 9 S' .  S = {0,1,2,...,n}        , S 12: lazy SRW , S SRW lazy S Markov , x ≤ y x,y ∈ S P = (P(x,y))z,yES Pt (x, n) ≤ Pt (y, n), ∀t ≥ 0 (9.1) , Markov 9.1. (9.1)  , y n – 1 n , n .  x, y ∈ S x ≤ y Markov x, y .. .
. ,  X t, Y t , .
●  ∑ t ≤  ∑ t, t ≥ 0 •  Y t – X t { X t = n} ⊂ { Y t = n}
□ S' Markov X ε , Y ε Markov ( , , , , ) S × S Markov ( X t , Y t ) ( X t , Y t ) S × S Markov X t = Y t Tcouple = inf { t ≥ 0 :                                                            } . {Xt}t>0,{Yt}t>0 . ({X t }, {Y t })
n n
|Pt(x,w) − Pt(y,w)| = |P(x,y)(Xt = W,Tcouple > t) − P(x,y)(Yt = W,Tcouple > t)| < P(x,y)(X t = W, Tcouple > t) + P(x,y)(Y t = W, Tcouple > t) . w Markov 9.1 (Lazy Simple Random Walk on Hypercube). Sn = {0,1}" Hamming ρ(x,y) = i{1 ≤ i ≤ n : x i ≠ y i},    x = (x 1 , . . , x n ), y = (y 1 , . . , y n ) ∈ S, Markov Markov hypercube S n lazy simple random walk (LSRW) LSRW t (n)
t mix S n 9.1. x, y ∈ S Pt (x,w) − Pt (y,w) = P(x,y)(Xt = w) − P(x,y)(Yt = w) ( (X t , Y t ) 1. 1/n 27 , 2.
0 1
n ) Tcoupon
T;
≤ n(1 + log n) 0
LSRW E(x,y)[Tcoupon] ≥ E(x,y)[Tcouple] > E (x,y)[Tcouple, Tcouple > t] ≥ tP(x,y)(Tcouple > t) , P(x,y)(Tcouple > t) ≤ t − 1 n(1 + log n) x,y ∈ S 9.1
9.1
9.2.
10
diam( S ) = max ( ρ ( x, y )) 10.1 10.1. 0 < ε < 1/2
B(x,r) . ρ( x 0, y 0) = diam( S ) x, T xo, Yo , to = [(diam(S') − 1)/2] supp[Pto(xo, ●)] ⊂ B(xo, to), supp[Pto(yo, ●)] ⊂ . supp[P to (x 0, ●)] ∩ supp[P to (y 0, ●)] ⊂ B (x 0, t 0) ∩ B (y 0, t 0) = ∅ B(yo,to) d(to) ≥ |Pto(xo, B(xo, to)) − Pto(yo, B(xo, to))| = 1, d(to) = 1. , 1 = d(to) ≥ 2d(to)       , d(to) ≥ 1/2 , 0 < ε < 1/2 ● tmix(c) ≥ to 10.1 (Lazy Simple Random Walk on Hypercube). S n hypercube {0, 1} n , , Markov S n LSRW , diam( S n ) = n
10.2
(Bottleneck ratio)
;
.元
S
10.2 (Simple Random Walk on a Graph). SRW, (Р, π)
Markov
. Markov 10.2. S
10.2 . D ⊂ S, π(D) ≤ 1/2        . supp[μD] ⊂ D , ||μd - π||τν ≥ 10.1 |μd(Dc) − π(Dc)| ≥ 1/2
10.3 (Simple Random Walk on Binary Tree). G = (V, E)    binary tree (   13), (P,π) D binary tree SRW
proper
( 14), S G 10.4 (q-coloring on Star Graph). G    star graph K 1 ,n–1 = (V, E) . proper : c ∈ S Markov .
, w
w , 1
(1,c(x 1 ),c(x 2 ),...,c(x n − 1 )) → (1,2,c(x 2 ),...,c(x n − 1 )) → (1, c(x1), c(x2), . . . , c(xn-1)) 2
3 {2, . . . , q}}
.

11
Kantorovich
mixing Kantorovich PK 11.1. ρκ P(S) n ( ). } , r(x, z) ( μ 1 , μ 3 ) μ2(y) > 0 y ∈ S
に
3. Kantorovich T
μ q(x,y) S'レ
11.2. , Markov

29
. x,y ∈ S (11.2) , 1 . ρ(x,y) = k , x = x0x1x2 · · · xk = y , vP PK
Po
♂ (11.6)
ρκ (μ,ν) ≤ E[ρ(X,Y)] , d(t) ≤ d(t) ≤ e−αt diam(S)
Markov
11.1 (Markov Chain on q-coloring). G = (V, E) ）  . S proper Sproper Markov , △ = max x ∈ G deg( x ) ( S = {c : V → [q]}       , S Markov
);
Sproper Sproper
q ≥ △ + 2 [5, p.115, Theorem 5.2.4] n (
n 11.2 (Brooks [2]). G )
12 [1] D. Aldous and P. Diaconis, Shuffling cards and stopping times, Amer. Math'l Monthly 93, 333-348, 1986, available at http://www-stat.stanford.edu/~cgates/PERSI [2] R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37, 194– 197, 1941. [3] R. Bubley, M. Dyer, Path coupling: A technique for proving rapid mixing in Markov chains, Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 223–231, 1997. [4] P. Diaconis, The cutoff phenomenon in finite Markov chains , Proc. Natl. Acad. Sci. USA 93 , 1659–1664, 1996.ムS' Markov n ( mixing rapid mixing) . ● [5] R. Diestel, Graph Theory , Electronic Edition 2005, available at http://www.math. uni-hamburg.de/home/diestel/books/graph.theory [6] R. Durrett, Essentials of Stochastic Processes, Springer, 1999. [7] A. Frieze, E. Vigoda, A survey on the use of Markov chains to randomly sample colorings, in Combinatorics, Complexity and Chance, A tribute to Dominic Welsh (G. Grimmett, C. McDiarmid eds.), 53-71, Oxford University Press, 2007, available at http://www.math. cmu.edu/~af1p [8] M. Jerrum, A very simple algorithm for estimating the number of k-colourings of a low-degree available at http://www.lfcs.inf.ed.ac.uk/reports/94/ECS-LFCS-94-290/ graph, index.html [9] G. Kolata, In Shuffling Cards, 7 Is Winning Number, The New York Times, 1990, available at http://query.nytimes.com/gst/fullpage.html?res= Jan. 9, 9C0CE0DC103AF93AA35752C0A966958260 [10] T. Lindvall, Lectures on the Coupling Method , Dover, Mineola, New York, 2002. [11] Y. Peres, Mixing for Markov Chains and Spin Systems, DRAFT Lecture notes for summer school at UBC on Mixing for Markov chains and spin systems, 2005, available at http: //www.stat.berkeley.edu/~peres [12] A. M. Vershik, Kantorovich metric: initial history and little-known applications , J. Math. Sci. 133 , 1410–1417, 2006. [13] E. Vigoda, Improved bounds for sampling colorings, J. Math. Phys. 41 , 1555–1569, 2000. [14] C. Villani, Topics in Optimal Transportation , Graduate Studies in Mathematics 58 , Amer. Math. Soc., 2003. [15] C. Villani, Optimal Transport, Old and New, version of Feb. 25, 2008, available at http: //www.umpa.ens-lyon.fr/~cvillani/surveys.html