Kullback-Leibler

Kullback-Leibler 206 6 6 http://www.math.tohoku.ac.jp/~kuroki/latex/206066kullbackleibler.pdf 0 2 Kullback-Leibler 3. q i.......................... 3.2........... 3.3 Kullback-Leibler.............. 4.4 Kullback-Leibler...................... 4.5............................ 5.6 max-plus Laplace.............. 6 2 Boltzmann 7 2.................................... 7 2.2 Boltzmann............................. 8 2.3....... 9 2.4............................. 3 Sanov 3. Sanov............................... 3.2 Sanov........................... 3 3.3 Sanov............................... 4 4 6 4. KL........ 6 URL.. 6 6 Ver.0.0. 0. 6 7 Ver.0.26. 4. Sanov 3. Stirling. 6 8 Ver.0.2...

2 0 : Stirling http://www.math.tohoku.ac.jp/~kuroki/latex/206050stirlingformula.pdf Stirling. Kullback-Leibler Boltzmann exp ν β νf ν k... [] Csiszar, Imre. A simple proof of Sanov s theorem. Bull Braz Math Soc, New Series 374, 453 459, 2006. http://www.emis.ams.org/journals/em/docs/boletim/vol374/v37-4-a2-2006.pdf [2] Dembo, Amir and Zeitouni, Ofer. Large Deviations Techniques and Applications. Stochastic Modelling and Applied Probability formerly: Applications of Mathematics, 38, Second Edition, Springer, 998, 396 pages. Google [3] Ellis, Richard, S. The theory of large deviations and applications to statistical mechanics. Lecture notes for École de Physique Les Houches, August 5 8, 2008, 23 pages. http://people.math.umass.edu/~rsellis/pdf-files/les-houches-lectures.pdf [4] Sanov, I. N. On the probability of large deviations of random variables. English translation of Matematicheskii Sbornik, 4284:, pp. 44. Institute of Statistics Mimeograph Series No. 92, March, 958. http://www.stat.ncsu.edu/information/library/mimeo.archive/isms 958 92.pdf [5]. I., 2008/2, 284. https://www.amazon.co.jp/dp/4563024376 [6] Ramon van Handel. Lecture 3: Sanov s theorem. Stochas Analytic Seminar Princeton University, Blog Article, 0 October 203. https://blogs.princeton.edu/sas/203/0/0/lecture-3-sanovs-theorem/ [7] Vasicek, Oldrich Alfonso. A conditional law of large numbers. Ann. Probab., Volume 8, Number 980, 42 47. http://projecteuclid.org/euclid.aop/76994830 Sanov 3.

3 Kullback-Leibler Stirling Kullback-Leibler.. q i q i 0, r i= q i =. i q i. q,..., q r. n, i k i k i. i k i /n n., n i n. n k i /n q i,. 2 Boltzmann. q,..., q n, k /n,..., k r /n, n. n i k i, r i= k i = n k! k r! qk qr kr, 0. p i 0, r i= p i =. n i k i /n p i, p i..2 n p i. n, k i log n k i = np i + Olog n = np i + O n,. logk i /n = log p i + Olog n/n 2. Stirling r i= k i = n log = n log n n + Olog n = k i log n i= k i + Olog n, log k i! = k i log k i k i + Olog k i = k i log k i k i + Olog n, log q k i i = k i log q i. 2 Taylor log + x = x x 2 /2 + x 3 /3 x 4 /4 +. i=

4. Kullback-Leibler k i. : log k! k r! qk q k r r = n = n = n k i log k i n n log q i + Olog n p i log p i log q i + Olog n i= i= i= p i log p i q i + Olog n. 4...3 Kullback-Leibler D[p q] = i= p i log p i q i : log k! k r! qk q k r r = nd[p q] + Olog n. p i. D[p q] Kullback-Leibler Kullback-Leibler divergence. Kullback-Leibler S[p q] = D[p q] = i= p i log p i q i. n q i p i n. : n p i = exp nd[p q] + Olog n. D[p q] > 0, n Olog n nd[p q], exp nd[p q]..4 Kullback-Leibler Kullback-Leibler D[p q] p = p,..., p r fx = x logx/q = xlog x log q x > 0. f x = log x log q +, f x = /x > 0 fx. fx x = q

.5. 5 x. fx fq + f qx = x q x = q. D[p q] = i= p i log p i q i p i q i = 0, i= p i = q i i =,..., r. Kullback-Leibler 0, 0 p i q i., p i q i, D[p q] > 0, p i n n 0., n k i /n q i.. Kullback-Leibler q i p i. n Kullback- Leibler n. Kullback-Leibler, Kullback-Leibler., p i, Kullback-Leibler. Kullback-Leibler. n, Kullback-Leibler. Kullback-Leibler, p i.. n.. B A., A B, B A.., n,...5 r = 2, q = q, q 2 = q.., p = p, p 2 = p, Kullback-Leibler : D[p q] = p log p q + p log p q. p = q 0, p q. Kullback- Leibler q p. p n exp nd[p q] + Olog n., p, D[p q] p

6. Kullback-Leibler n 0.. n. n a.?, n q. 0 a < q, a n., 0 a < q, a, n q. q < a., n, a 0. a p. Kullback-Leibler. p a D[p q] p = a., n p = a. q < a, a, n a. : { D[q q] = 0 0 a q, n n log k/n a n q k q n k = inf D[p q] = k p a, n k k/n a q k q n k = exp D[a q] q < a. n inf D[p q] + Olog n. p a a. n D[p q]..6 max-plus Laplace a, b a, b max{a, b}, a, b a + b semiring, semifiled max-plus. max-plus tropical mathematics.,.., max 0, +,. log., : n n logena + e nb = max{a, b}, n n logena e nb = a + b.

7.. a b, b a 0, e nb a, n logean + e nb = n log e na + e nb a = a + n log + e nb a a n.. : n n log expna i + Olog n = max{a,..., a r }. i= expna i + Olog n /n n a i., expna i + Olog n = expn max{a,..., a r } + Olog n i= n. Laplace. : β exp nfx + Olog n dx = exp n inf fx + Olog n α x β α fx x = x 0, f x 0 > 0, β e nfx gx dx = e nfx0 2π gx 0 + o nf x 0 α Laplace. n. n. 2 Boltzmann Kullback-Leibler, Boltzmann. 2. q = q,..., q r. n i i k i /n p i, p = p,..., p r. n p = exp nd[p q] + Olog n n. : p = p,..., p r f ν,i p i = c ν ν =, 2,..., s i=

8 2. Boltzmann., R r,,...,, f ν,,..., f ν,r ν =,..., s. p, n?, i E i E i p i = U i=, U, n., i, E i, E i p i = U i=, U, n. 2 s =. s >. 2.2 Boltzmann n, r i= p i = Kullback-Leibler K[p q] = r i= p i logp i /q i p = p,..., p r. Lagrange. Kullback- Leibler p. L = p i log p s i + λ p i + β ν f ν,i p i c ν q i= i i= ν= i=. λ, β ν. p i L 0 0 = L λ = 0 = L β ν = p i, i= f ν,i p i c ν ν =,..., s, 2 i= 0 = L p i = log p i q i + λ + s β ν f ν,i i =,..., r 3 ν=. 3, s p i = exp λ β ν f ν,i q i ν=

2.3. 9, Z := e λ = i= e s ν= β νf ν,i q i, p i = Z e s ν= β νf ν,i q i 4. Z. p i Z = e λ β ν. β ν 4 2. exp s ν= β νf ν,i Boltsmann. Boltzmann q i p i. p i Gibbs., n p = p,..., p r. n p i Gibbs. s =, f,i = E i, c = U, β = β, p i = Z e βe i q i, Z = e βe i q i, i= log Z β = Z E i e βe i q i = U. i= q i Boltzmann. Gibbs S[p q] = K[p q] = r i= p i logp i /q i : logp i /q i = s ν= β νf ν,i log Z, r i= p i =, r i= f ν,ip i = c ν S[p q] = s β ν c ν + log Z. ν= s =, f,i = E i, c = U, β = β S[p q] = βu + log Z., Boltzmann,. 2.3 qx. n px /n n S[p q] = K[p q] = px log px qx dx. px : f ν xpx dx = c ν ν =,..., s.

0 2. Boltzmann, K[p q] px : px = s Z e ν= β νf ν x qx, Z = e s ν= β νf ν x qx dx, log Z = f ν xe s ν= β νf ν x qx dx = c ν. β ν Z... k + + k r = n, β i = log q i p k,...,k r = q k,...,k r = k! k r! qk q k r r k! k r! r n, Z = r = e i= β ik i q k,...,k r, Z r n px = Z e x µ2 /2σ 2, Z = 2πσ 2. Gamma x > 0 px = e x/τ x α τ α Γα = e x/τ+α log x Z, Z = τ α Γα. Beta px = x > 0 x α Bα, β + x = eα log x α+β log+x, Z = Bα, β. α+β Z t Cauchy px = π + x Z 2 = e log+x2, Z = π. Beta 0 < x < px = xα x β Bα, β = eα log x+β log x Z, Z = Bα, β. Poisson p k = e λ λ k k! = e log λk q k, q k = e Z k!, Z = eλ+.

2.4. 2.4 s =, f x = x 2, c =, qx = 3., n x 2 x 2 + + x 2 n/n x 2 + + x 2 n = n, n x. px = Z e βx2, Z = R e βx2 dx = πβ /2, log Z β = 2β =. β = /2, Z = 2π, px = e x2 /2 / 2π. n. R n 2 n n n. : n n S n fx µ n dx = R fx e x2 /2 2π dx. n S n n n, µ n, fx x x x,..., x n. 4.,. 3 Sanov Sanov. Stirling. [6].. 3. Sanov {, 2,..., r} P : P = { p = p,..., p r R r p,..., p r 0, p + + p r = }. P r. q = q,..., q r P. X, X 2,... {, 2,..., r}, q = q,..., q r. q = q,..., q r. 3 qx = qx.,. 4 Maxwell-Boltzmann. http://www.math.tohoku.ac.jp/~kuroki/latex/206050stirlingformula.pdf

2 3. Sanov A #A, A P A. i =,..., r X,..., X n i k i P #{ k =, 2,..., n X k = i } = k i for each i =,..., r = k! k r! qk qr kr. k,..., k r k i = 0,,..., n, k + + k r = n. k,..., k r k /n,..., k r /n P n P : { k P n = n,..., k } r k i = 0,,..., n, k + + k r = n. n P n n + r. #P n n + r. X,..., X n P n P n, P n. P n P n. p, q P 2 D[p q] : D[p q] = i= p i log p i q i. p i q i 0 0 log 0 = 0, log 0 =. D[p q] Kullback-Leibler. 3. Sanov. : A P inf n 2 A P 5 sup n n log P P n A inf p A D[p q]. n log P P n A inf p A D[p q]. 3 P A A n n log P P n A = inf D[p q]. p A n Kullback-Leibler D[p q] inf. 3.2. r = 2, q = q, q 2 = q, p = p, p 2 = p, D[p q] = p log p q + p log p q. 5 P A., A.

3.2. Sanov 3 p = q 0, p q. 0 a < b, A = a, b. P P n A = n q k q n k k n n log α<k/n<β a<k/n<b n q k q n k = inf k D[p q] = a<p<b. Sanov. D[b q] b < q, D[q q] = 0 a q b, D[a q] q < a 3.2 Sanov Stirling. 3.3. k, l. l k l k. l! k! kl k. l! k! = k + k + 2 l kl k. l! k! = l + l + 2 k = k l k. k k l Sanov. Stirling. 3.4. p P n n + r e nd[p q] P P n = p e nd[p q].. p = p,..., p r = k /n,..., k r /n P n, nd[p q] = e nd[p q] = P P n = p = k i log p i + i= p k p kr r k i log q i, i= q k q k r r, k! k r! qk q kr r.

4 3. Sanov, : n + r k!... k r! pk p k r r... l i = 0,,..., n, l + + l r = n., p i = k i /n l!... l r! pl p lr r., 3.3, k!... k r! pk p kr r = l! k! lr! k r! kk l k k r l r r k l k k l r k r r k k l k k r l r r =., = l + +l r=n n + r. l!... l r! pl p lr r n + r k!... k r! pk p kr r 3.3 Sanov 3... A {, 2,..., r} P. n= P n = P Q r {, 2,..., r} P. A P p n P n A. P P n A = p P n A D[p n q] = inf D[p q] n p A P P n = p P P n = p n 3.4.. n log P P n A D[p n q] r logn + n inf n n log P P n A inf p A D[p q]. n + r e nd[p n q].. 2. A {, 2,..., r} P. P P n A = P P n = p e nd[p q] n + r e n inf p A D[p q]. p P n A p P n A

3.3. Sanov 5 3.4.. n log P P n A inf D[p q] + r logn + p A n sup n n log P P n A inf p A D[p q]. 2. 3. A B, B C, A C. B A C inf p B D[p q] inf p A D[p q] inf p C D[p q]. C B D[p q] p, inf p C D[p q] = inf p B D[p q]. inf p B D[p q] = inf p A D[p q] = inf p C D[p q].,2 3. 3.. 3.5. Sirling.. : q i 0, q + + q r = k! k r! qk q k r r k i Z 0, k + + k r = n.., k i,. 2 : k i Z 0, k + + k r = n, k i /n = q i, l! l r! ql q l r r k! q r! qk q k r r l i Z 0, l + + l r = n. : l! k! kl k k, l Z 0. k, l. 2. Sanov.

6 4. 4 4. KL n,. q i 0, r i= q i =, a, b i r i= b i = a, p i = b i a = Nb i Na. N Na log Na! Nb! Nb r! qnb qr Nbr = i= p i log p i q i. Kullback-Leibler. /Na Na! N Nb! Nb r! qnb q Nb r r = p /q p pr /q r pr... N Na log Na! Nb! Nb r! qnb q Nb r r = Na Nb i log k log k + Nb i log q i Na k= i= k= i= = Na log k Nb i Na Na log k Na + Nb i log q i k= = Na Na k= 0 log k Na log x dx = [x log x x] 0 = i= p i log p i q i. i= i= i= pi i= 0 k= Na Nb i k= log x dx + i= log k Na + p i log q i i= p i log q i i= [x log x x] p i 0 + p i log q i 2 Na logna r i= Nb i logna = 0.. : N Na p i = b i /a /Na i= p /q p pr /q r p r.