MathLabs

Phương trình vi phân và Hệ động lực

Lý thuyết ergodic

Nghiên cứu hành vi trung bình dài hạn của hệ động lực, liên kết với phép biến đổi bảo toàn độ đo.

Trực giácNếu bạn xoay mãi mãi theo cùng một góc lẻ, cuối cùng bạn có ghé qua mọi nơi không?

Đánh dấu một điểm trên mặt số tròn và xoay nó, lặp đi lặp lại, theo một góc cố định là một phân số vô tỉ của một vòng tròn đầy đủ — chẳng hạn, góc vàng khoảng 137.5∘137.5^\circ, giống cách hạt hướng dương và vảy quả thông mọc lên. Vì góc là vô tỉ, điểm đó không bao giờ quay lại đúng chỗ ban đầu, và điều đáng chú ý là cuối cùng nó tiến gần tùy ý tới mọi điểm trên đường tròn, ghé qua mỗi cung nhỏ với tần suất tỉ lệ với độ dài cung đó. Không có chút ngẫu nhiên nào ở đây — quy tắc chỉ là một phép quay cứng duy nhất, lặp lại mãi mãi — nhưng thống kê dài hạn trông y hệt như thể điểm được chọn ngẫu nhiên đều. Hiện tượng phân bố đều này, và câu hỏi những tính chất trung bình nào một quy tắc tất định tạo ra trong thời gian vô hạn, chính là chủ đề của lý thuyết ergodic.

Đường tròn đơn vị tương tác cho thấy một điểm được xoay lặp lại theo góc vàng vô tỉ, minh họa tính phân bố đều.
Kéo thanh trượt theta nhiều lần qua góc vàng 137.5∘137.5^\circ: điểm được đánh dấu không bao giờ lặp lại chính xác, nhưng sau đủ số vòng, nó đã quét ra một tập điểm dày đặc, trải đều trên đường tròn — bức tranh hình học đằng sau tính phân bố đều và tính ergodic của phép quay vô tỉ T(x)=x+α(mod1)T(x)=x+\alpha \pmod 1.

Đại họcPhép biến đổi bảo toàn độ đo

Định nghĩa: Phép biến đổi bảo toàn độ đo

Cho (X,F,μ)(X,\mathcal F,\mu) là một không gian xác suất (một tập XX, một σ\sigma-đại số F\mathcal F gồm các tập con đo được, và một độ đo μ\mu với μ(X)=1\mu(X)=1). Một ánh xạ T:X→XT:X\to X bảo toàn độ đo nếu μ(T−1A)=μ(A)\mu(T^{-1}A) = \mu(A) với mọi A∈FA\in\mathcal F — độ đo của tập các điểm sẽ rơi vào AA bằng độ đo của chính AA. Trực giác: áp dụng TT không bao giờ tạo ra hay phá hủy khối lượng xác suất, chỉ sắp xếp lại vị trí của nó.

μ(T−1A)=μ(A)∀ A∈F\mu(T^{-1}A) = \mu(A) \quad \forall\, A \in \mathcal{F}

Ba ví dụ neo giữ lý thuyết này. Phép quay vô tỉ T(x)=x+α(mod1)T(x)=x+\alpha \pmod 1 trên đường tròn [0,1)[0,1) với α\alpha vô tỉ bảo toàn độ dài thông thường (Lebesgue), vì xoay một cung không làm thay đổi độ dài của nó. Ánh xạ nhân đôi T(x)=2x mod 1T(x)=2x\bmod 1 cũng bảo toàn độ đo Lebesgue — nó đúng là 2-1, và mỗi trong hai nhánh nghịch ảnh của một khoảng bị nén lại một hệ số 22, nên tổng độ dài của chúng khôi phục chính xác độ dài ban đầu. Và một dịch chuyển Bernoulli (tung đồng xu độc lập, dịch đi một bước mỗi lần) bảo toàn độ đo xác suất tích tự nhiên trên không gian các dãy tung đồng xu vô hạn, vì dịch một dãy các lần tung độc lập đi một bước vẫn để lại các lần tung độc lập, cùng phân bố.

T−1A=A  ⟹  μ(A)∈{0,1}T^{-1}A=A \;\Longrightarrow\; \mu(A)\in\{0,1\}

Một phép biến đổi bảo toàn độ đo TT là ergodic nếu mọi tập bất biến qua TT về cơ bản là tầm thường: T−1A=A  ⟹  μ(A)∈{0,1}T^{-1}A=A \;\Longrightarrow\; \mu(A)\in\{0,1\} với mọi AA đo được. Tương đương, hệ không thể tách thành hai mảnh có độ đo dương mà TT không bao giờ trộn lẫn với nhau — không có cách phân rã động lực học nào không tầm thường. Cả phép quay vô tỉ lẫn ánh xạ nhân đôi đều ergodic đối với độ đo Lebesgue, nhưng vì những lý do hoàn toàn khác nhau, như bảng dưới đây làm rõ.

Tính ergodic và tính trộn cho ba ví dụ điển hình
Phép biến đổiErgodic?Trộn?
Phép quay vô tỉ T(x)=x+α(mod1)T(x)=x+\alpha \pmod 1Có — mọi quỹ đạo đều phân bố đềuKhông — phép quay cứng không bao giờ trộn hai cung lại
Ánh xạ nhân đôi T(x)=2x mod 1T(x)=2x\bmod 1CóCó — tương quan giữa các thời điểm xa nhau suy giảm về không
Ánh xạ đồng nhất T(x)=xT(x)=xKhông (trừ khi XX chỉ có một điểm) — mọi tập đều bất biếnKhông

Đại họcĐịnh lý ergodic Birkhoff và định lý hồi quy Poincaré

Cho TT là một phép biến đổi bảo toàn độ đo của không gian xác suất (X,F,μ)(X,\mathcal F,\mu) và f∈L1(μ)f\in L^1(\mu). Khi đó các trung bình theo thời gian Snf(x)n\frac{S_nf(x)}{n} hội tụ với hầu hết xx theo μ\mu tới một giới hạn bất biến qua TT là fˉ(x)\bar f(x) với ∫Xfˉ dμ=∫Xf dμ\int_X \bar f\,d\mu = \int_X f\,d\mu. Hơn nữa nếu TT ergodic, thì fˉ(x)=∫Xf dμ a.e.\bar f(x)=\int_X f\,d\mu\ \text{a.e.} — trung bình theo thời gian dọc theo một quỹ đạo duy nhất bằng trung bình theo không gian.

Vì sao đúng?

Đây là phiên bản chặt chẽ của một trực giác mà các nhà vật lý đã dùng hàng thập kỷ mà không có chứng minh (giả thuyết ergodic của Boltzmann trong cơ học thống kê): để tính trung bình dài hạn của một đại lượng nào đó, bạn có thể hoặc theo dõi một hệ tiến triển trong thời gian rất dài, hoặc lấy trung bình trên toàn bộ một tập hợp các hệ tại một thời điểm — và với các hệ ergodic, hai phép tính nghe có vẻ rất khác nhau này cho ra chính xác cùng một kết quả.

Chứng minh

Bước 1 (limsup và liminf bất biến). Đặt f∗(x)=lim sup⁡n→∞Snf(x)nf^*(x)=\limsup_{n\to\infty}\frac{S_nf(x)}{n} và f∗(x)=lim inf⁡n→∞Snf(x)nf_*(x)=\liminf_{n\to\infty}\frac{S_nf(x)}{n}. Vì Sn+1f(x)=f(x)+Snf(Tx)S_{n+1}f(x) = f(x) + S_nf(Tx), chia cho n+1n+1 và cho n→∞n\to\infty cho thấy f∗(Tx)=f∗(x)f^*(Tx)=f^*(x) và f∗(Tx)=f∗(x)f_*(Tx)=f_*(x): cả hai đều là hàm bất biến qua TT.

Bước 2 (định lý ergodic cực đại). Với λ∈R\lambda\in\mathbb R, đặt Aλ={x:sup⁡nSnf(x)/n>λ}A_\lambda=\{x: \sup_n S_nf(x)/n>\lambda\} là tập nơi trung bình thời gian chạy từng vượt quá λ\lambda. Bổ đề kỹ thuật then chốt (chứng minh bằng cách xét g=f−λg=f-\lambda và cực đại của các tổng riêng Mn(x)=max⁡(0,S1g(x),…,Sng(x))M_n(x)=\max(0,S_1g(x),\dots,S_ng(x)), sau đó dùng Mn(Tx)≥Skg(Tx)M_n(Tx)\ge S_kg(Tx) theo từng số hạng và lấy tích phân trên tập nơi Mn>0M_n>0) cho ∫Aλf dμ≥λ μ(Aλ)\int_{A_\lambda} f\,d\mu \ge \lambda\,\mu(A_\lambda).

Bước 3 (ép f và f_ lại gần nhau). Giả sử phản chứng rằng f∗>f∗f^*>f_* trên một tập có độ đo dương; khi đó tồn tại các số hữu tỉ α<β\alpha<\beta với E={x:f∗(x)<α<β<f∗(x)}E=\{x: f_*(x)<\alpha<\beta<f^*(x)\} có độ đo dương. EE bất biến qua TT (vì f∗,f∗f^*,f_* bất biến), nên ta có thể chỉ xét trên EE. Áp dụng bất đẳng thức cực đại cho f−βf-\beta trên EE buộc ∫Ef dμ≥βμ(E)\int_E f\,d\mu\ge\beta\mu(E), và áp dụng cho α−f\alpha-f tương tự buộc ∫Ef dμ≤αμ(E)\int_E f\,d\mu\le\alpha\mu(E); vì α<β\alpha<\beta và μ(E)>0\mu(E)>0 hai điều này mâu thuẫn nhau. Vậy f∗=f∗f^*=f_* hầu khắp nơi, nên giới hạn fˉ(x)=lim⁡nSnf(x)/n\bar f(x)=\lim_n S_nf(x)/n tồn tại hầu khắp nơi và bất biến qua TT.

Bước 4 (khớp các tích phân, và trường hợp ergodic). Một lập luận hội tụ bị chặn (cắt cụt ff và kiểm soát các đuôi bằng bất đẳng thức cực đại lần nữa) cho ∫Xfˉ dμ=∫Xf dμ\int_X \bar f\,d\mu = \int_X f\,d\mu. Cuối cùng, nếu TT ergodic, hàm bất biến qua TT là fˉ\bar f phải là hằng số hầu khắp nơi (theo chính định nghĩa của tính ergodic áp dụng cho các tập mức {fˉ≤c}\{\bar f\le c\} của nó, mỗi tập này bất biến qua TT nên có độ đo 00 hoặc 11); kết hợp với sự bằng nhau của các tích phân, hằng số đó phải là ∫Xf dμ\int_X f\,d\mu, cho fˉ(x)=∫Xf dμ a.e.\bar f(x)=\int_X f\,d\mu\ \text{a.e.}.

Cho TT là một phép biến đổi bảo toàn độ đo của một không gian xác suất (hay tổng quát hơn, độ đo hữu hạn) (X,F,μ)(X,\mathcal F,\mu) và A∈FA\in\mathcal F với μ(A)>0\mu(A)>0. Khi đó hầu hết mọi điểm của AA đều quay trở lại AA vô hạn lần: với hầu hết x∈Ax\in A, Tnx∈AT^nx\in A với vô hạn n≥1n\ge1.

Vì sao đúng?

Nếu không gian hữu hạn và không có gì bị phá hủy (bảo toàn độ đo), một vùng không thể mãi mãi gửi các điểm tới lãnh thổ hoàn toàn mới, chưa từng ghé qua — cuối cùng hệ phải bắt đầu quay lại những nơi đã từng ở, đơn giản vì không còn chỗ mới nào để đặt độ đo quay trở lại.

Chứng minh

Bước 1 (các điểm không bao giờ quay lại). Đặt A0={x∈A:Tnx∉A ∀n≥1}A_0=\{x\in A: T^nx\notin A\ \forall n\ge1\} là các điểm của AA không bao giờ quay lại AA. Các tập A0,T−1A0,T−2A0,…A_0, T^{-1}A_0, T^{-2}A_0,\dots đôi một rời nhau: nếu x∈T−iA0∩T−jA0x\in T^{-i}A_0\cap T^{-j}A_0 với i<ji<j, thì Tix∈A0T^ix\in A_0 nhưng cũng Tjx=Tj−i(Tix)∈AT^j x = T^{j-i}(T^ix) \in A với j−i≥1j-i\ge1, mâu thuẫn với việc Tix∈A0T^ix\in A_0 không bao giờ quay lại AA. Vậy T−iA0∩T−jA0=∅ (i≠j)T^{-i}A_0 \cap T^{-j}A_0=\varnothing\ (i\ne j).

Bước 2 (tập không bao giờ quay lại có độ đo không). Vì TT bảo toàn độ đo, μ(A0)=μ(T−iA0)\mu(A_0)=\mu(T^{-i}A_0) với mọi ii. Nếu μ(A0)>0\mu(A_0)>0, các tập đếm được đôi một rời nhau T−iA0T^{-i}A_0 (i=0,1,2,…i=0,1,2,\dots) đều có cùng độ đo dương này, nên hợp của chúng sẽ có tổng độ đo vô hạn — điều không thể vì μ(X)<∞\mu(X)<\infty (thực ra μ(X)=1\mu(X)=1). Vậy μ(A0)=0\mu(A_0)=0.

Bước 3 (những điểm chỉ quay lại hữu hạn lần cũng có độ đo không). Đặt B={x∈A:x returns to A only finitely often}B=\{x\in A: x\ \text{returns to}\ A\ \text{only finitely often}\}. Viết BB như một hợp đếm được theo kk của (về cơ bản) tập không bao giờ quay lại của TkAT^kA dưới động lực đã dịch chuyển, B=⋃k≥0T−k{x∈TkA:x never returns to TkA}B=\bigcup_{k\ge0} T^{-k}\{x\in T^kA: x\ \text{never returns to}\ T^kA\}, mỗi số hạng có độ đo không theo đúng lập luận Bước 1–2 áp dụng cho TkAT^kA thay cho AA (dùng μ(TkA)=μ(A)\mu(T^kA)=\mu(A)). Theo tính cộng tính dưới đếm được, μ(B)=0\mu(B)=0.

Bước 4 (kết luận). Mọi x∈A∖Bx\in A\setminus B (có độ đo đầy đủ trong AA, vì μ(B)=0\mu(B)=0) quay lại AA vô hạn lần theo định nghĩa của BB. Đây chính xác là phát biểu của định lý.

Nâng caoTrộn: một dạng ergodic mạnh hơn

Định nghĩa: Trộn mạnh

Một phép biến đổi bảo toàn độ đo TT là trộn (mạnh) nếu lim⁡n→∞μ(T−nA∩B)=μ(A)μ(B)\lim_{n\to\infty}\mu(T^{-n}A\cap B)=\mu(A)\mu(B) với mọi A,BA,B đo được: tỉ lệ của BB rơi trở lại vào AA sau nn bước hội tụ tới giá trị nó sẽ có nếu AA và BB độc lập thống kê. Trộn kéo theo ergodic (lấy B=AB=A với T−1A=AT^{-1}A=A: khi đó μ(A)=μ(A∩A)→μ(A)2\mu(A)=\mu(A\cap A)\to\mu(A)^2, buộc μ(A)∈{0,1}\mu(A)\in\{0,1\}), nhưng chiều ngược lại không đúng.

Vì sao phép quay vô tỉ ergodic nhưng không trộn? Lấy A=BA=B là một cung nhỏ: xoay nó đi nαn\alpha chỉ di chuyển cứng cùng một cung nhỏ đó quanh đường tròn, nên T−nA∩AT^{-n}A\cap A hoặc rỗng hoặc (với vô hạn nn, vì phép quay phân bố đều) lại rất gần với toàn bộ AA — tỉ lệ chồng lấp không bao giờ ổn định về giá trị độc lập μ(A)2\mu(A)^2, nó cứ dao động trở lại gần μ(A)\mu(A). Ngược lại, ánh xạ nhân đôi kéo giãn và gấp mọi khoảng nhỏ trải khắp toàn bộ không gian theo cấp số mũ cực nhanh, thực sự xáo trộn nó — cơ chế chịu trách nhiệm cho tính trộn của nó, và cuối cùng cho việc coi các ánh xạ hỗn loạn như động lực học logistic r=4r=4 là "tốt như ngẫu nhiên" cho mục đích thống kê.

Đại họcỨng dụng thực tiễn và Ví dụ minh họa

Lý thuyết ergodic biến "hành vi trung bình trong thời gian vô hạn" thành một phát biểu tính được, chứng minh được, chính xác là điều cơ học thống kê cần để biện minh cho việc thay trung bình dài hạn của một hệ vật lý đơn lẻ bằng trung bình tập hợp (giả thuyết ergodic của Boltzmann), điều nén dữ liệu cần để định nghĩa tốc độ entropy giới hạn mức một nguồn có thể được nén (qua entropy Kolmogorov–Sinai của dịch chuyển tương ứng), điều các công cụ tìm kiếm như PageRank của Google cần để đảm bảo một tần suất ghé thăm dài hạn duy nhất cho một người lướt web ngẫu nhiên (độ đo bất biến của một xích Markov), và điều các bộ sinh giả ngẫu nhiên mật mã xây dựng từ các ánh xạ hỗn loạn cần để biện minh cho việc coi đầu ra của chúng là ngẫu nhiên về mặt thống kê. Trong mọi trường hợp, các tính chất ergodic và trộn chính là thứ cho phép coi một quỹ đạo tất định duy nhất như thể nó mang thông tin thống kê về toàn bộ hệ.

Ví dụ: Một phép quay vô tỉ ghé thăm một cung cho trước thường xuyên đến đâu?

Cho T(x)=x+α(mod1)T(x)=x+\alpha\pmod 1 với α\alpha vô tỉ tác động lên đường tròn [0,1)[0,1) với độ đo Lebesgue, và A=[0,0.3)A=[0,0.3). Với một điểm xuất phát x0x_0 điển hình, tỉ lệ các lần lặp đầu nn tiên x0,x1,…,xn−1x_0,x_1,\dots,x_{n-1} rơi vào AA là bao nhiêu, khi n→∞n\to\infty?

Lời giải

Đây chính xác là một phép tính định lý ergodic Birkhoff với f=1Af=\mathbf 1_A, hàm chỉ thị của AA: trung bình theo thời gian 1n∑k=0n−11A(xk)\frac1n\sum_{k=0}^{n-1}\mathbf 1_A(x_k) chính là tỉ lệ các lần lặp đầu nn tiên rơi vào AA.

Các phép quay vô tỉ là một ví dụ cổ điển của phép biến đổi ergodic đối với độ đo Lebesgue (đây thực chất là định lý phân bố đều Weyl: bất kỳ tập bất biến qua TT nào, khi khai triển thành chuỗi Fourier, buộc mọi hệ số Fourier khác không phải triệt tiêu vì phép quay nhân chúng với e2πikα≠1e^{2\pi i k\alpha}\ne1, chỉ để lại hàm hằng).

Vì TT ergodic, định lý Birkhoff áp dụng ở dạng mạnh nhất: trung bình theo thời gian bằng trung bình theo không gian với mọi điểm xuất phát điển hình, không chỉ trung bình trên các điểm xuất phát. Trung bình theo không gian là ∫X1A dμ=μ(A)=0.3−0=0.3\int_X \mathbf 1_A\,d\mu = \mu(A) = 0.3-0 = 0.3.

Vậy tỉ lệ thời gian dài hạn quỹ đạo dành ở AA chính xác bằng 0.30.3, bất kể x0x_0 nào bạn xuất phát (ngoài một tập ngoại lệ có độ đo không) — một phiên bản chặt chẽ của "phép quay tất định hành xử, về mặt thống kê, y hệt như việc chọn một điểm ngẫu nhiên đều trong AA mỗi lần."

Ví dụ: Một nguồn dữ liệu thiên lệch có thể được nén tới đâu? Entropy Kolmogorov–Sinai của một dịch chuyển Bernoulli

Một nguồn dữ liệu phát ra các bit độc lập, mỗi bit là 11 với xác suất p=0.3p=0.3 và 00 với xác suất 0.70.7 — được mô hình hóa theo nghĩa ergodic như dịch chuyển Bernoulli trên các dãy với độ đo tích (0.3,0.7)(0.3,0.7). Hãy tính tốc độ entropy của nó (entropy Kolmogorov–Sinai của dịch chuyển, ở đây bằng entropy Shannon của một ký hiệu duy nhất), mà theo định lý mã hóa nguồn của Shannon chính là số bit tối thiểu trên mỗi ký hiệu, trung bình, cần để nén nguồn này không mất mát.

Lời giải

Với một nguồn i.i.d. (Bernoulli), entropy Kolmogorov–Sinai của ánh xạ dịch chuyển rút gọn về entropy Shannon thông thường của một ký hiệu duy nhất: h=−∑ipilog⁡2pih=-\sum_i p_i\log_2 p_i.

Thay p1=0.3p_1=0.3, p0=0.7p_0=0.7: h=−0.3log⁡20.3−0.7log⁡20.7h=-0.3\log_2 0.3-0.7\log_2 0.7.

Tính từng số hạng: −0.3log⁡20.3=0.3×1.737=0.521-0.3\log_2 0.3 = 0.3\times1.737=0.521 bit, và −0.7log⁡20.7=0.7×0.515=0.361-0.7\log_2 0.7=0.7\times0.515=0.361 bit (dùng log⁡20.3≈−1.737\log_2 0.3\approx-1.737 và log⁡20.7≈−0.515\log_2 0.7\approx-0.515).

Cộng lại, h≈0.881 bitsh\approx0.881\ \text{bits}. Vậy trung bình, không có mã không mất mát nào có thể nén nguồn này xuống dưới khoảng 0.8810.881 bit mỗi ký hiệu (thấp hơn đáng kể so với 11 bit/ký hiệu cần cho một đồng xu công bằng, chính vì sự thiên lệch làm nguồn dễ đoán hơn, do đó nén được nhiều hơn) — và định lý Shannon đảm bảo chặn này đạt được.

Một phép biến đổi T:X→XT:X\to X bảo toàn độ đo xác suất μ\mu, nghĩa là μ(T−1A)=μ(A)\mu(T^{-1}A) = \mu(A). Đẳng thức này phải đúng với những tập AA nào?

Theo định lý ergodic Birkhoff, với phép quay vô tỉ ergodic T(x)=x+α(mod1)T(x)=x+\alpha \pmod 1 và A=[0,0.3)A=[0,0.3), tỉ lệ thời gian dài hạn một quỹ đạo điển hình dành trong AA là bao nhiêu?

Theo định lý hồi quy Poincaré, với một hệ bảo toàn độ đo trên không gian độ đo hữu hạn có μ(A)>0\mu(A)>0, hầu hết mọi điểm của AA...

Một nguồn phát ra các bit i.i.d. với P(1)=0.3P(1)=0.3. Tốc độ entropy của nó (entropy Kolmogorov–Sinai của dịch chuyển Bernoulli tương ứng), làm tròn tới hai chữ số thập phân theo bit, gần nhất với:

Tài liệu tham khảo

  1. Peter Walters (1982). An Introduction to Ergodic Theory
  2. George D. Birkhoff (1931). Proof of the Ergodic Theorem
  3. John von Neumann (1932). Proof of the Quasi-Ergodic Hypothesis
  4. Hillel Furstenberg (1981). Recurrence in Ergodic Theory and Combinatorial Number Theory