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 , 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.
Đạ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 là một không gian xác suất (một tập , một -đại số gồm các tập con đo được, và một độ đo với ). Một ánh xạ bảo toàn độ đo nếu với mọi — độ đo của tập các điểm sẽ rơi vào bằng độ đo của chính . Trực giác: áp dụng 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ó.
Ba ví dụ neo giữ lý thuyết này. Phép quay vô tỉ trên đường tròn với 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 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ố , 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ố.
Một phép biến đổi bảo toàn độ đo là ergodic nếu mọi tập bất biến qua về cơ bản là tầm thường: với mọi đo được. Tương đương, hệ không thể tách thành hai mảnh có độ đo dương mà 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õ.
| Phép biến đổi | Ergodic? | Trộn? |
|---|---|---|
| Phép quay vô tỉ | Có — mọi quỹ đạo đều phân bố đều | Không — phép quay cứng không bao giờ trộn hai cung lại |
| Ánh xạ nhân đôi | Có | 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 | Không (trừ khi chỉ có một điểm) — mọi tập đều bất biến | Không |
Đại họcĐịnh lý ergodic Birkhoff và định lý hồi quy Poincaré
Cho là một phép biến đổi bảo toàn độ đo của không gian xác suất và . Khi đó các trung bình theo thời gian hội tụ với hầu hết theo tới một giới hạn bất biến qua là với . Hơn nữa nếu ergodic, thì — 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 và . Vì , chia cho và cho cho thấy và : cả hai đều là hàm bất biến qua .
Bước 2 (định lý ergodic cực đại). Với , đặt là tập nơi trung bình thời gian chạy từng vượt quá . Bổ đề kỹ thuật then chốt (chứng minh bằng cách xét và cực đại của các tổng riêng , sau đó dùng theo từng số hạng và lấy tích phân trên tập nơi ) cho .
Bước 3 (ép f và f_ lại gần nhau). Giả sử phản chứng rằng trên một tập có độ đo dương; khi đó tồn tại các số hữu tỉ với có độ đo dương. bất biến qua (vì bất biến), nên ta có thể chỉ xét trên . Áp dụng bất đẳng thức cực đại cho trên buộc , và áp dụng cho tương tự buộc ; vì và hai điều này mâu thuẫn nhau. Vậy hầu khắp nơi, nên giới hạn tồn tại hầu khắp nơi và bất biến qua .
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 và kiểm soát các đuôi bằng bất đẳng thức cực đại lần nữa) cho . Cuối cùng, nếu ergodic, hàm bất biến qua là 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 của nó, mỗi tập này bất biến qua nên có độ đo hoặc ); kết hợp với sự bằng nhau của các tích phân, hằng số đó phải là , cho .
Cho 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) và với . Khi đó hầu hết mọi điểm của đều quay trở lại vô hạn lần: với hầu hết , với vô hạn .
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 là các điểm của không bao giờ quay lại . Các tập đôi một rời nhau: nếu với , thì nhưng cũng với , mâu thuẫn với việc không bao giờ quay lại . Vậy .
Bước 2 (tập không bao giờ quay lại có độ đo không). Vì bảo toàn độ đo, với mọi . Nếu , các tập đếm được đôi một rời nhau () đề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ì (thực ra ). Vậy .
Bước 3 (những điểm chỉ quay lại hữu hạn lần cũng có độ đo không). Đặt . Viết như một hợp đếm được theo của (về cơ bản) tập không bao giờ quay lại của dưới động lực đã dịch chuyển, , mỗi số hạng có độ đo không theo đúng lập luận Bước 1–2 áp dụng cho thay cho (dùng ). Theo tính cộng tính dưới đếm được, .
Bước 4 (kết luận). Mọi (có độ đo đầy đủ trong , vì ) quay lại vô hạn lần theo định nghĩa của . Đâ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 là trộn (mạnh) nếu với mọi đo được: tỉ lệ của rơi trở lại vào sau bước hội tụ tới giá trị nó sẽ có nếu và độc lập thống kê. Trộn kéo theo ergodic (lấy với : khi đó , buộc ), 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 là một cung nhỏ: xoay nó đi chỉ di chuyển cứng cùng một cung nhỏ đó quanh đường tròn, nên hoặc rỗng hoặc (với vô hạn , vì phép quay phân bố đều) lại rất gần với toàn bộ — tỉ lệ chồng lấp không bao giờ ổn định về giá trị độc lập , nó cứ dao động trở lại gần . 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 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 với vô tỉ tác động lên đường tròn với độ đo Lebesgue, và . Với một điểm xuất phát điển hình, tỉ lệ các lần lặp đầu tiên rơi vào là bao nhiêu, khi ?
Lời giải
Đây chính xác là một phép tính định lý ergodic Birkhoff với , hàm chỉ thị của : trung bình theo thời gian chính là tỉ lệ các lần lặp đầu tiên rơi vào .
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 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 , chỉ để lại hàm hằng).
Vì 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à .
Vậy tỉ lệ thời gian dài hạn quỹ đạo dành ở chính xác bằng , bất kể 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 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à với xác suất và với xác suất — đượ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 . 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: .
Thay , : .
Tính từng số hạng: bit, và bit (dùng và ).
Cộng lại, . 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 bit mỗi ký hiệu (thấp hơn đáng kể so với 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 bảo toàn độ đo xác suất , nghĩa là . Đẳng thức này phải đúng với những tập nào?
Theo định lý ergodic Birkhoff, với phép quay vô tỉ ergodic và , tỉ lệ thời gian dài hạn một quỹ đạo điển hình dành trong 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ó , hầu hết mọi điểm của ...
Một nguồn phát ra các bit i.i.d. với . 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
- Peter Walters (1982). An Introduction to Ergodic Theory
- George D. Birkhoff (1931). Proof of the Ergodic Theorem
- John von Neumann (1932). Proof of the Quasi-Ergodic Hypothesis
- Hillel Furstenberg (1981). Recurrence in Ergodic Theory and Combinatorial Number Theory