2009 77 31 (random) CD ) ( ) onvqrkgockprtvwwvetkdxktrdkfrbikdvbrakxskcvd dvwtkpikurbkcvcdrbkxwkdurkpowmkowakxskuofvwt kwxduvwtkdxkaxkxwqrkxbkdgvqrkcurkuoakyrryrak vwdxkdurkpxxmkurbkcvcdrbkgockbroavwtkkpedkvd kuoakwxkyvqdebrckxbkqxwfrbcodvxwckvwkvdkkowa kguodkvckdurkecrkxskokpxxmkkkduxetudkonvqrkk gvduxedkyvqdebrckxbkqxwfrbcodvxwkk 11 2

 
 
 3 5 5 6 88 9 99 44
4.3 10 12 1 5
6 1 3 11 2 (P. de Fermat) (B. Pascal) 1933 (A. N. Kolmogorov) (Alea jacta est)   (J. Ceasar) ( .
 (Der Alte würfelt nicht) (A. Einstein) .
 2 ( ) 6 ( ●  ●  ●  ●  ●  ● 1: 6 1/6 11 6 11 1/6 1/2 22 Persi Diaconis .
 ) 11 1 ) 1 1 22
12
1. 1
1/12
6 12 11 2. 2 12 (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6) (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6) (5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6) (6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6) 36 1/36 33
11 12 3. b
2. 1 23 1/23 2
23
(4 24
) 33 {1,2,. . ,n} 4.
1: log6 n n 1, 2, . . ,, n ( 1/nして) k: 1 [ x ] ● [[x] [ x ] r [log6 n] ♠♠ n 1/n
k [ x ] 4. 1/8, 2 11 3/8, 3 1/3, 4 1          24 n = 24 1  3 1 4 12 2  13  20 44 3　21　24 1/6 3 22 0 k – 1 ls k + 1 1 2: {0, 1, 2, . . , n } 2 k: n 3. k 0 n 1 ( 0 3.1 . n = 6 0 3 2 44 6 3: n = 6 {1 2 3 4 5} .
 1, 3, 5 ) 2, 4, 6 6 ● 0 6 ● 0 0 6 0 1 ) n ( （         )
11
6 2:  100 100 2 6
6
(state space) ( ) 3.2 4.
k n n Pk tk n = 6
0 3
Po, P1, . . , P5, P6 6 ) 1°) ( 6 Po
P6 = 1 Po = 0,
6 11
t k 3°) 1 n n/2 9 39 7
3: n = 6 3.3 tk n k: t k
tk = k(n − k) 5 2
UK, UK
2
CT
uo = vo = 0, un = vn = 0, uk = vk (k = 1, . . . ,n − 1) 4 4.1 y = x² 4: G = (V, E) V = {0, 1, 2, 3, 4, 5, 6},  E = {01, 12, 15, 23, 34, 45, 46} E v (P6) VO, V1   . . , V5 deg(v 0 ) = deg(v 5 ) = 1,    deg(v 1 ) = deg(v 2 ) = deg(v 3 ) = deg(v 4 ) = 2 V = {0,1,2,3,4,5,6}, E = {01,12,15,23,34,45,46}, ∂ = {0,6} 0 4 G = (V, E) v v deg(v) v (G, ∂) 5 0 6 5:
Po = 0, p1 =
1 5. 4.2 9 6.
1
4g = 2 + d + h 4h = e + g + i 4c = 1 + b + f
4r = 1 + c + e + i
4r = 1 + f + h
1 6 6
6: ( ) 100
1 100 k: k: 4
4: ( 5 )
11
6 100000000 100000000 v v v 1940 4.3 1
k: V
vo = 0 V6 = 1 V6 — V5 = V5 — V4 = V4 — V3 = V3 — V2 = V2 — V1 = V1 — V0 = ri 2 — V4 V6 — V5 = V5 V5
7 T
k: k: k + 1 R
I 2 5 ( ri )
V k
G T
Pz
( 8)
8: 6 13 5 5.1 8 × 8 9: ( ) 64 64 ( ） 7. 5.2 15 10 4 × 4 1 15
10:  15 6 10
1/4 64 16! = 2092278988800
11: 8. 11 5.3 ♠A
) 51 ( 1/52 1/52 1
12 52 52 52! = 8065817517094387857166063685640376697528950544088327782400000000000 6http://www.afsgames.com/15puzzle.htm 12: 1 15 1 10 10 10! = 3628800
7 n = 10 23.0529
6
5
1
fyeaxjqfzjoxceddedcjbujcxbjhxgpjbegxrjukjzeb bedcjopjsxgjzezbxgjudjbsxjofdljjfdrjukjsfhed cjdubsedcjbujrujudaxjugjbqeaxjzsxjsfrjnxxnxr jedbujbsxjouuljsxgjzezbxgjqfzjgxfredcjjotbje bjsfrjdujneabtgxzjugjaudhxgzfbeudzjedjebjjfd rjqsfbjezjbsxjtzxjukjfjouuljjjbsutcsbjfyeaxj jqebsutbjneabtgxzjugjaudhxgzfbeudjj 5: 6.1 (J. Ceaser) a, b, c, d, . . . , x, y, z 7 [1]
↑ 8 9 9 10 2 6 7 5 1
外
4 [ 6 ] ↑ 13:  10 a → d, b → e, c → f,...,x → a, y → b,z → c σ Before a b c d e f g h i k l m n o p q r s t u v w x y z j After d e f g h i j k l m n o p q r s t u v w x y Z a b c 6: σ this is a pen σ this is a pen ⇒ wklv lv d shq a σ wklv lv d shq = σ(this is a pen) σ(this is a pen) = wklv lv d shq σ−1 x
σ−1 [ 8 ] σ y = σ(x) σ− (σ(x)) l (y) = σ−1 (wklv lv d shq) = this is a pen Z σ Z Z σ 26 8 “wklv lv d shq” 26 η η(wklv lv d shq) σ−1 6.2 2 a a 2 5 ◇ 8 σ 8 5 σ−1 a
a Before a b c d e f k 1 g h i m n o p q r u v j S t W X ◇ Z S   Z After ｃｔｇｎｉａｒｖｘ◇ f k m p b y w d h u o e j q 8: σ σ−1 9. σ 27! = 108886945041835216076800000 81 25 6.3 10. S ) f : S → R f ( S' T T y f f (y) T f
S y f (y) 27! ( ) S' f T f (y) (i) f(x) < f(y) (ii) f(x) ≥ f(y) y (v) Pxy < 1 f(x) y y 1 – Px,y z ,f T r T f f(x) f ( ) T .f f ( x ) (case (ii)) 6.4 9 50 17 ( ) 50¹ 7 = 7629394531250000000000000000 ( ) 17 ( ) NHK 50 26 1°) ?, ! ◇ this is a pen. 50 9 5
� 9: (t, h),  (h, i),  (i, s),  (s, o),  (o, i),  (i, s),  (s, o),  (o, a),  (a, o),  (o, p),  (p, e),  (e, n),  (n, o) 27 × 27 23 X = X1X2 - 5 3°) 4°)
9 σ T η
d η′
m i
y
S'
η =
η′
y S'
y
f : S → R 5°) 2122 . . . 2n
.f ,f 10 ( 10 f (η) = MznMnoMoy = 0 × 19 × 0 = 0 Mzn, Mno, Moy this f(σ−1) = Mth Mhi Mis = 134 × 33 × 57 = 252054 ,f 0 7 0: 1: 2: 3: 4: 5: 6: 7: fyeaxjqfzjoxceddedcjbujcxbjhxgpjbegxrjukjzebbedcjopjsxgjzezbxgjudjbsxjofdljfdrjukjsfhedcj ugado cut bohassash ie hoi ponm ianol ek taiiash bm fon tation es ifo busy usl ek fupash upico fut bodissisd re dor hong rinol ek tirrisd bg mon titron es rmo busy usl ek muhisd avico wat bohissish re hor pong rinol ed tirrish bg mon titron es rmo basy asl ed mapish avice wat mepirrirp so pes leny sined ob tissirp my hen titsen or she mark ard ob halirp apice was beginning to get dery tirel of sitting by her sister on the bank anl of hading alice was beginning to get very tired of sitting by her sister on the bank and of having alice was beginning to get very tired of sitting by her sister on the bank and of having amice was beginning to get very tired of sitting by her sister on the banl and of having alice was beginning to get very tired of sitting by her sister on the bank and of having 8: 9:
) 11 ) j
(i) 6.5 5 Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it, "and what is the use of a book," thought Alice, "without pictures or conversation? — Lewis Carroll, "Alice's Adventures in Wonderland" “Down the rabbit-hole” 1 Charles Lutwidge Dodgson [1] [2] [3] 1988 [4] L. Carroll: Alice's Adventures in Wonderland, Project Gutenberg, available at http://www. gutenberg.org/etext/11 [5] P. Diaconis: The Markov Chain Monte Carlo Revolution, Bull. Amer. Math. Soc. 46(2009) 179–205. Available at Prof. Diaconis's homepage. [6] P. G. Doyle and J. L. Snell: Random Walks and Electoric Networks, available at http: //front.math.ucdavis.edu/0001.5057 [7] A. N. Kolmogorov: Grundbegriffe der Wahrscheinlichkeitsrechnung. Berlin: Julius Springer, 1933. (Translation) Foundations of the Theory of Probability (2nd ed.). New York:  Chelsea 1956. English version is available at http://www.mathematik.com/Kolmogorov/index. html [8] D. Levin, Y. Peres and E. Wilmer: Markov Chains and Mixing Times, A.M.S., 2008.