CÁC KIẾN THỨC CHUẨN BỊ
Xích Markov hữu hạn
Xích Markov hữu hạn là một quá trình chuyển động giữa các phần tử trong một tập hữu hạn, trong đó vị trí tiếp theo được chọn dựa trên một phân phối xác suất xác định Định nghĩa này nhấn mạnh cách thức hoạt động của xích Markov trong việc xác định trạng thái tiếp theo.
1.1.1 Định nghĩa Định nghĩa này có ý nghĩa rằng :xác suất có điều kiện của việc thay đổi từ trạng thái x tới trạng thái y, không phụ thuộc mà chỉ phụ thuộc trạng thái x
Dòng thứ x của P sẽ được ký hiệu là Ma trận P như vậy được gọi là ma trận ngẫu nhiên, các phần tử của dòng này không âm và
Chú ý rằng, xích Markov được định nghĩa với tính thuần nhất, có nghĩa là xác suất chuyển trạng thái từ thời điểm này sang thời điểm tiếp theo không phụ thuộc vào chính thời điểm hiện tại.
Một con ếch sống trong một cái ao giữa hai lá sen, một ở phía đông và một ở phía tây Một ngày, nó tìm thấy hai đồng xu ở đáy ao và đặt mỗi đồng xu lên một lá sen Mỗi buổi sáng, con ếch quyết định có nhảy sang lá sen kia hay không bằng cách tung đồng xu trên lá sen hiện tại Nếu đồng xu rơi xuống mặt sấp, nó sẽ nhảy sang lá sen kia; nếu là mặt ngửa, nó sẽ ở lại lá sen cũ.
Hãy xem xét các lá sen được đánh dấu bằng { } và ( ) mà con ếch nhảy qua vào các ngày Chủ Nhật, Thứ Hai, v.v Giả sử rằng đồng xu ở lá sen phía đông có xác suất p để rơi xuống mặt sấp, trong khi đồng xu ở lá sen phía tây có xác suất q để rơi xuống mặt sấp Quy tắc nhảy của con ếch diễn ra theo cách đơn giản như đã mô tả.
Xích Markov được định nghĩa bởi ma trận chuyển P, trong đó dòng đầu tiên của P biểu thị phân phối có điều kiện của trạng thái khi cho trạng thái trước đó, còn dòng thứ hai của P thể hiện phân phối có điều kiện của trạng thái khi cho một trạng thái khác.
Giả sử con ếch nằm trên lá sen phía đông vào Chủ Nhật, khi thức dậy vào sáng Thứ Hai, nó có xác suất p để chuyển sang lá sen phía tây và xác suất để ở lại lá sen phía đông.
{ | } { | } (1.3) Cái gì sẽ xảy ra ở ngày Thứ Ba? Bằng việc xét hai khả năng cho , ta sẽthấy
Hình 1.1 Một bước nhảy của con ếch
Cho tới khi được mặt sấp, nó sẽ nhảy từ lá này sang lá kia rằng
Ta có thể lưu thông tin về phân phối của ta trong một véc tơ dòng
Giả thiết con ếch bắt đầu ở lá sen phía đông thì bây giờ có thể được viết như là
, và khi đó (1.3) có thể trở thành Bằng việc nhân P vào bên phải ta có thể cập nhật phân phối một bước nữa
(1.6) và thay thế đối với phân phối ban đầu bất kỳ nào đó ta có
Hình 1.2 chỉ ra rằng có thể tồn tại một giới hạn trong phân phối theo thời gian, với giá trị phụ thuộc vào các tham số p và q Bất kỳ phân phối giới hạn nào như vậy đều đáp ứng điều kiện nhất định, cho thấy rằng giới hạn này có ý nghĩa quan trọng trong việc hình dung về phân phối.
Thật vậy, Nếu bây giờ ta định nghĩa với mọi thì
Hình 1.2 Xác suất theo từng thời điểm
(a) p=q=1/2; (b) p=0.2, q=0.1; (c) p=0.95, q=0.7 Các xác suất giới hạn tương ứng là 1/2, 1/3, 14/33 bằng định nghĩa của dãy cần thỏa mãn
( ) (1.8) vì nên do đó ta kết luận rằng khi thì Vậy
(1.9) đối với phân phối ban đầu bất kỳ Như vậy
Các tính toán vừa thực hiện áp dụng cho xích Markov với hai trạng thái có thể mở rộng cho bất kỳ xích Markov hữu hạn trạng thái nào Cụ thể, phân phối tại một thời điểm có thể được xác định thông qua phép nhân ma trận Đối với xích Markov hữu hạn trạng thái với không gian trạng thái và ma trận chuyển trạng thái P, giả sử véc tơ dòng là phân phối của hệ thống.
{ }, với mọi Từ điều kiện phụ thuộc vào các kết quả có thể có thể có ở các bước trước bước thứ , ta thấy rằng
Viết lại điều này dưới dạng véc tơ, đưa đến và vì vậy
Chúng tôi sẽ xem xét các chuỗi Markov có cùng ma trận chuyển trạng thái nhưng khác nhau ở trạng thái ban đầu Để làm rõ, chúng tôi sẽ giới thiệu các ký hiệu cho xác suất và kỳ vọng tương ứng với trạng thái ban đầu.
Như thế, xác suất để chuyển t bước từ x đến y được cho bởi phần tử ở dòng của ma trận , ta gọi các phần tử ấy là xác suất chuyển t bước
Để xây dựng ma trận P, chúng ta cần xem các phân phối dưới dạng véc tơ dòng Nếu xích có phân phối tại thời điểm t, thì nó cũng sẽ có phân phối tại thời điểm sau đó Việc nhân véc tơ dòng với ma trận P sẽ chuyển đổi từ phân phối hiện tại sang phân phối trong tương lai.
Phần tử thứ x của Pf đại diện cho giá trị kỳ vọng của hàm f tại trạng thái tiếp theo, dựa trên thông tin hiện có ở trạng thái x Việc nhân véc tơ cột với ma trận P từ bên trái giúp chuyển đổi từ một hàm trong không gian trạng thái sang giá trị kỳ vọng của hàm đó trong tương lai.
1.1.2 Biểu diễn ánh xạ ngẫu nhiên Định nghĩa Một biểu diễn ánh xạ ngẫu nhiên của một ma trận chuyển trên không gian trạng thái là một hàm , với một biến ngẫu nhiên – giá trị Z, thỏa mãn
Nếu có một dãy các biến ngẫu nhiên độc lập với phân phối giống như Z, và X0 có phân phối xác định, thì dãy này sẽ tạo thành một chuỗi Markov với ma trận chuyển P và phân phối ban đầu xác định.
Với ví dụ về di động ngẫu nhiên đơn giản trên chu trình, đặt { }, mỗi có phân phối đều trên , và cho một biểu diễn ánh xạ ngẫu nhiên
Mọi ma trận chuyển trong không gian trạng thái hữu hạn đều có thể được biểu diễn bằng ánh xạ ngẫu nhiên Tuy nhiên, cần lưu ý rằng biểu diễn ánh xạ ngẫu nhiên không phải là duy nhất, khác với các ma trận chuyển.
Tính tối giản và tính không tuần hoàn
Một xích Markov được coi là tối giản nếu với bất kỳ hai trạng thái nào, luôn tồn tại một số nguyên t (có thể phụ thuộc vào x và y) để đảm bảo khả năng quay trở lại trạng thái ban đầu Tập hợp các thời điểm khả dĩ để xích Markov quay về điểm xuất phát được gọi là { } Chu kỳ của mỗi trạng thái được xác định bởi ước chung lớn nhất của các thời điểm này.
Nếu P là tối giản, thì
Xích tối giản có chu kỳ được xác định là chu kỳ chung của tất cả các trạng thái Nếu mọi trạng thái trong xích đều có chu kỳ 1, xích đó được xem là không tuần hoàn Ngược lại, nếu xích có chu kỳ khác 1, nó sẽ được gọi là tuần hoàn.
Nếu P là tuần hoàn và tối giản thì có một số nguyên không âm r sao cho với mọi
Giả định một xích tối giản với chu kỳ 2 di chuyển ngẫu nhiên trên chu trình có độ dài chẵn, không gian trạng thái được chia thành hai lớp: lớp chẵn và lớp lẻ Xích chỉ chuyển đổi giữa hai lớp này, tạo ra sự tương tác đặc biệt trong quá trình di chuyển.
Giả sử P có chu kỳ 2 và là một trạng thái chẵn, phân phối xác suất của xích sau bước sẽ có giá trị trên các trạng thái chẵn, trong khi phân phối của xích sau bước sẽ có giá trị trên các trạng thái lẻ Do đó, rõ ràng là không thể mong đợi phân phối hội tụ khi điều kiện này xảy ra.
Một điều chỉnh đơn giản có thể giải quyết các vấn đề về tuần hoàn Đối với một ma trận chuyển ngẫu nhiên, giả sử có ma trận đơn vị I Hình ảnh minh họa có thể được tưởng tượng như việc lật một đồng xu ở mỗi bước.
Nếu kết quả trả về là sấp, thực hiện một bước trong ma trận; còn nếu là ngửa, giữ nguyên trạng thái hiện tại Điều này là do ma trận chuyển không tuần hoàn Chúng ta gọi đây là phiên bản lười của ma trận.
Ví dụ Trở lại Ví dụ ở đầu Mục 1.1.2 về di động ngẫu nhiên trên -chu trình Với mỗi , di động ngẫu nhiên trên -chu trình là tối giản
Di động ngẫu nhiên trên một chu trình có độ dài chẵn là tuần hoàn, trong khi đó, di động ngẫu nhiên trên một chu trình có độ dài lẻ lại không tuần hoàn.
Ma trận chuyển đối với một di động ngẫu nhiên lười trên n-chu trình là
Di động ngẫu nhiên lười trên n-chu trình có cả hai tính chất tối giản và không tuần hoàn với mọi n
1.2.3 Di động ngẫu nhiên trên đồ thị
Một đồ thị gồm có một tập các đỉnh và một tập các cạnh ,
Một đồ thị có thể được hình dung như một tập hợp các điểm, trong đó hai điểm được nối với nhau bởi một đường nếu và chỉ nếu chúng là phần tử của tập các cạnh Khi hai điểm được nối, ta nói rằng chúng là kề của nhau Bậc của một đỉnh, ký hiệu là , là số lượng các đỉnh kề với đỉnh đó.
Khi cho một đồ thị , ta có thể định nghĩa di động ngẫu nhiên đơn giản trên là xích Markov với không gian trạng thái và ma trận chuyển
Khi xích ở trạng thái đỉnh, nó có khả năng di chuyển đến tất cả các đỉnh kề với một phân phối đều, đảm bảo rằng mỗi đỉnh kề được chọn đều có cơ hội được tiếp cận.
Ví dụ Xét đồ thị được chỉ ra trong Hình 1.4
Ma trận chuyển của di động ngẫu nhiên đơn giản trên là
Các phân phối dừng
Ta đã thấy trong Ví dụ ở Mục 1.1.1 rằng phân phối π trên thỏa mãn
Phân phối giới hạn của xích Markov được định nghĩa qua công thức (1.14), và một phân phối xác suất π thỏa mãn điều này được gọi là phân phối dừng Nếu π là một phân phối dừng và xích bắt đầu tại phân phối dừng, thì điều này áp dụng cho mọi trạng thái Ngoài ra, công thức (1.14) cũng có thể được diễn đạt dưới dạng từng phần tử, dẫn đến một phát biểu tương đương.
Hình 1.4 Ví dụ về một đồ thị có 5 đỉnh và 6 cạnh
Ví dụ Xét di động ngẫu nhiên đơn giản trên một đồ thị Với đỉnh bất kỳ ,
(1.16) Để nhận một xác suất, vì một tính chất của đồ thị là ∑ | | Ta kết luận rằng độ đo xác suất
| | là tỷ lệ đối với bậc, luôn là một phân phối dừng đối với di động Với đồ thị trong Hình 1.4,
Nếu mọi đỉnh trong đồ thị đều có bậc d, thì đồ thị được gọi là d-chính quy Trong trường hợp này, phân phối đều với mọi đỉnh là một phân phối dừng.
Một mục đích chính của chương này và chương 2 là chứng minh rằng các xích Markov hữu hạn hội tụ tới các phân phối dừng của chúng Để phân tích thời gian cần thiết để đạt được tính dừng, chúng ta cần xác nhận rằng nó là hữu hạn Trong mục này, chúng ta sẽ chỉ ra rằng dưới một số điều kiện nhẹ, các phân phối dừng tồn tại và là duy nhất Chiến lược của chúng ta là xây dựng một phân phối nào đó và kiểm tra các thuộc tính cần thiết Những công cụ được phát triển ở đây sẽ được áp dụng ở nhiều nơi khác Trong mục 2.2, chúng ta sẽ chứng minh rằng các xích tối giản và không tuần hoàn thực sự hội tụ tới các phân phối dừng của chúng một cách chính xác.
1.3.2 Các thời điểm chạm và quay lại đầu tiên
Trong bài viết này, chúng ta giả định rằng xích Markov có không gian trạng thái hữu hạn và ma trận chuyển P Đối với mỗi trạng thái, chúng ta sẽ định nghĩa thời điểm chạm liên quan đến trạng thái đó.
{ } đó là thời điểm đầu tiên xích đạt trạng thái x Với các tính huống chỉ có một lần đạt đến x ở một thời điểm dương, ta cũng định nghĩa
Khi , ta gọi là thời điểm quay lại đầu tiên
Bổ đề Với các trạng thái bất kỳ x và y của một xích tối giản, ( )
Định nghĩa xích tối giản khẳng định rằng tồn tại các số nguyên dương r và số thực dương ε, với tính chất rằng cho bất kỳ trạng thái nào, luôn có một trạng thái tồn tại với xác suất chạm y tại một thời điểm giữa Điều này dẫn đến việc xác định giá trị xác suất cho trạng thái này, đảm bảo tính nhất quán trong mô hình xích tối giản.
{ } { } (1.17) Lặp lại (1.17) cho xác suất ở vế phải nhiều lần, suy ra
Khi là một biến ngẫu nhiên giá trị nguyên không âm, ta có
Vì { } là một hàm giảm của , (1.18) đủ để chặn mọi số hạng của biểu thức tương ứng đối với ( ):
1.3.3 Sự tồn tại của một phân phối dừng Định lý hội tụ dưới đây nói rằng những phần đuôi theo thời gian của một xích Markov không tuần hoàn tối giản ở trong mỗi trạng thái phù hợp với phân phối dừng của xích Tuy vậy ta chưa thể chứng minh các phân phối dừng là tồn tại! Để xây dựng một phân phối dừng, ta xét một sự lưu lại của xích từ một trạng thái tùy ý nào đó quay về Vì những lần đạt tới qua ngắt qũy đạo của một xích thành các đoạn có phân phối đồng nhất, không ngạc nhiên rằng sự phân tán trung bình của thời điểm (gian) trên khoảng lưu lại trong mỗi trạng thái là phù hợp với phân bố đuôi của thời điểm tồn tại trong
Mệnh đề Giả sử là ma trận chuyển của một xích Markov tối giản Thế thì
(i) Tồn tại một phân phối xác suất trên sao cho và với mọi và hơn nữa
Giả sử xích Markov ở một trạng thái tùy ý, chúng ta sẽ kiểm tra thời gian trung bình mà xích đạt tới mỗi trạng thái qua các lần đi qua Điều này giúp xác định rõ ràng các đặc điểm của quá trình Markov.
Với trạng thái bất kỳ, ta có ̃ Vì vậy Bổ đề ở Mục 1.3.2 bảo đảm rằng ̃ với mọi Ta sẽ kiểm tra rằng ̃ là dừng, từ định nghĩa:
Vì biến cố { } { } được xác định bởi ,
{ } { } (1.21) Đảo thứ tự của tổng (1.20) và sử dụng đồng nhất thức (1.21) để có
Biểu thức trong (1.22) rất giống với (1.19), vì vậy ta hoàn toàn có thể đạt được Thực tế,
∑ { } ̃ { } { } (1.23) ̃ { } ∑ { } ̃ (1.24) Phương trình (1.24) kéo theo việc xét hai trường hợp:
: Vì và , cả hai số hạng cuối cùng của (1.23) bằng
1, và triệt tiêu lẫn nhau
: Cả hai số hạng của (1.23) bằng 0
Do đó kết hợp (1.22) và (1.24) chỉ ra rằng ̃ ̃
Cuối cùng, để nhận được một độ đo xác suất, ta chuẩn hóa bởi ∑ ̃ : ̃
( ) (1.25) Trong thực tế, với bất kỳ ,
Chú ý Ta sẽ thấy trong Mục 1.4 rằng sự tồn tại của là không cần cho tính tối giản, nhưng cần cho tính dương
Việc tính toán ở đầu chứng minh mệnh đề có thể được mở rộng Một thời điểm dừng là một biến ngẫu nhiên nhận giá trị từ tập { } sao cho với mỗi t, biến cố được xác định bởi Nếu thay thế một thời điểm dừng vào định nghĩa (1.19) của ̃, thì việc chứng minh rằng ̃ thỏa mãn ̃ ̃ sẽ đảm bảo rằng cả hai đẳng thức { } và { } đều được thỏa mãn.
Nếu là một thời điểm dừng thì một hệ quả tức thời của định nghĩa và tính chất Markov là
Tính chất Markov mạnh cho phép xích tái khởi động tại một thời điểm dừng Mặc dù điều này dễ dàng áp dụng cho không gian trạng thái đếm được, nhưng việc thiết lập cho các xích Markov với thời gian rời rạc trong tập không đếm được lại phức tạp hơn nhiều.
1.3.4 Tính duy nhất của phân phối dừng Đầu chương này ta đã nêu lên sự khác nhau giữa phép nhân một véc tơ dòng với vào bên phải và nhân một véc tơ cột với vào bên trái: cái trước đưa ra một phân phối bởi một bước của xích, trong khi phép sau đưa lại kỳ vọng của một hàm trên các trạng thái, một bước sau đó của xích Ta gọi các phân phối bất biến qua phép nhân phải với là dừng Câu hỏi đặt ra là những hàm như thế nào sẽ bất biến đối với các phép nhân trái?
Gọi một hàm là điều hòa tại nếu
Một hàm là điều hòa trên nếu nó là điều hòa tại mọi trạng thái
Nếu được coi như là một vec tơ cột, thì một hàm là điều hòa trên toàn bộ thỏa mãn phương trình ma trận
Bổ đề Giả sử rằng P là tối giản, Một hàm h điều hòa tại mọi điểm của là hằng số
Chứng minh Vì là hữu hạn, cần có một trạng thái sao cho là cực đại Nêu đối với trạng thái z nào đó sao cho ta có , thì
∑ (1.29) mâu thuẫn! Điều đó suy ra rằng với mọi trạng thái mà
Với bất kỳ , tính tối giản nghĩa là có một dãy với Lặp lại như trên sẽ cho ta
Thế thì là hằng số
Hệ quả Giá sử P là một ma trận chuyển của một xích Markov tối giản Khi đó tồn tại duy nhất một phân phối thỏa mãn
Mệnh đề 1.14 khẳng định sự tồn tại ít nhất một độ đo nhất định Theo bổ đề 1.16, hạt nhân Ker có số chiều 1, do đó, cột hạng của nó cũng được xác định.
Hạng dòng của ma trận vuông bất kỳ luôn bằng hạng cột của nó, và phương trình vector tương ứng có tập nghiệm là không gian con một chiều Không gian này chỉ chứa một vector duy nhất, trong đó tổng các thành phần bằng 1.
Chú ý Một chứng minh khác của hệ quả trên cũng được suy ra từ định lý hội tụ (Định lý 2.3.1, trong chương sau)
1.3.5 Tính khả nghịch và những sự đảo ngược thời gian
Giả sử một xác suất trên thỏa mãn
Phương trình (1.30) được gọi là phương trình cân bằng chi tiết Một xích thỏa mãn (1.30) được gọi là khả nghịch
Giả sử có ma trận chuyển của một xích Markov với không gian trạng thái Một phân phối bất kỳ thỏa mãn phương trình cân bằng chi tiết (1.30) được xem là dừng đối với xích Markov này.
Chứng minh Lấy tổng cả hai về của (1.30) trên tất cả các y:
Kiểm tra tính cân bằng chi tiết là phương pháp đơn giản để chứng minh một phân phối cụ thể là dừng Hơn nữa, khi điều kiện (1.30) được thỏa mãn, điều này càng củng cố thêm cho kết luận đó.
Ta có thể viết (1.31) dưới dạng sau:
Nói cách khác, nếu một xích thỏa mãn (1.30) và có phân phối ban đầu là dừng, thì phân phối của cũng như phân phối của
Vì lý do này, một xích thỏa mãn (1.30) được gọi là khả nghịch
Ví dụ Xét di động ngẫu nhiên đơn giản trên một đồ thị G trong ví dụ ở mục 1.3.1, phân phối | | là dừng
Nên xích là khả nghịch, có nghĩa là ký hiệu biểu diễn hàm chỉ tiêu của tập A chỉ đúng khi và chỉ khi thỏa mãn điều kiện nhất định.
XÍCH MARKOV VÀ PHÂN PHỐI DỪNG
Khoảng cách biến thiên toàn phần và sự ghép đôi
2.1.1 Khoảng cách biến thiên toàn phần giữa hai phân phối Định nghĩa Khoảng cách biến thiên toàn phần (total variation distance), sau này sẽ gọi tắt là khoảng cách toàn phần, giữa hai phân phối xác suất trên là lượng được xác định bởi
Định nghĩa này thể hiện rõ tính xác suất, trong đó khoảng cách giữa hai phân phối xác suất phản ánh sự khác biệt tối đa giữa các xác suất của cùng một biến cố.
Trong ví dụ về câu chuyện con ếch ném đồng xu, xác suất con ếch nhảy từ hướng đông sang tây và từ tây sang đông được thể hiện qua ma trận chuyển trạng thái.
) và phân phối dừng của nó là
Giả thiết con ếch bắt đầu từ lá ở phía đông, do đó và định nghĩa t = t (
Vì chỉ có hai trạng thái nên chỉ có bốn biến cố xảy ra do đó dễ dàng kiểm tra rằng
Chúng ta đã chỉ ra ở Ví dụ trong Mục 1.1.1 là Do đó với xích hai trạng thái này, khoảng cách sẽ giảm nhanh theo hàm mũ khi tăng
Định nghĩa khoảng cách (2.1) là cực đại trên tất cả các tập con của một giá trị riêng, tuy nhiên, nó không phải là cách thuận tiện nhất để ước lượng khoảng cách Chúng ta sẽ giới thiệu ba đặc trưng thay thế hữu ích Mệnh đề 1 quy khoảng cách giữa hai phân phối thành một tổng đơn giản trên không gian trạng thái Trong mục 2.1.2, mệnh đề sử dụng sự ghép đôi để cung cấp một giải thích xác suất khác, cho thấy ‖ ‖ đo lường sự phân biệt giữa hai biến ngẫu nhiên như thế nào.
Mệnh đề 1 Giả sử là hai phân phối xác suất trên Khi đó
‖ ‖ ∑ | | (2.2) Chứng minh: Giả sử { } Khi đó
(2.3) Bất đẳng thức đầu tiên là đúng vì nên
Với bất đẳng thức thứ hai, để ý rằng việc gộp thêm các phần tử của không thể giảm bớt sự sai khác của xác suất Vậy
Hình 2.1 𝐵 {𝑥 𝜇 𝑥 𝜈 𝑥 } Vùng I có diện tích
𝜇 𝐵 𝜈 𝐵 Vùng II có diện tích 𝜈 𝐵 𝑐 𝜇 𝐵 𝑐 Vì diện tích mỗi vùng của 𝜇 𝑣 𝜈 đều là 1, nên các vùng I và II phải có cùng diện tích là ‖𝜇 𝜈‖ 𝑇𝑉
Lập luận hoàn toàn tương tự,
Tuy nhiên, cận trên ở vế phải của (2.3) và (2.4) thực tế là giống nhau, như có thể thấy bằng Hình 2.1 Hơn nữa khi chúng ta lấy (hoặc bằng ), thì
| | bằng cận trên Như vậy
Chứng minh của Mệnh đề 1 cũng cho thấy rằng
(2.5) nó là một dấu hiệu có ích
Dựa vào Mệnh đề 1 và bất đẳng thức tam giác cho các số thực, có thể nhận thấy rằng khoảng cách biến thiên toàn phần tuân thủ bất đẳng thức tam giác Điều này cũng áp dụng cho các phân bố xác suất.
‖ ‖ ‖ ‖ ‖ ‖ (2.6) Mệnh đề 2 Giả sử là hai phân bố xác suất trên Ω Khi đó khoảng cách giữa chúng thỏa mãn:‖ ‖
(2.7) Chứng minh: Khi thỏa mãn | | , ta có
‖ ‖ Điều đó chỉ ra rằng vế phải của (2.7) không lớn hơn | | TV Đặt
Sử dụng (2.5) để thấy vế phải bằng ‖ ‖ TV Vì thế vế phải của (2.7) ít nhất là
2.1.2 Ghép hai phân phối xác suất và khoảng cách biến thiên toàn phần
Xét một cặp biến ngẫu nhiên trong không gian xác suất với phân phối xác suất biên duyên là a và v Điều này có nghĩa là cặp biến ngẫu nhiên này thỏa mãn điều kiện xác suất cụ thể.
Ghép hai biến ngẫu nhiên là một kỹ thuật hiệu quả với nhiều ứng dụng khác nhau Bài viết này sẽ làm rõ mối liên hệ chặt chẽ giữa việc ghép hai biến ngẫu nhiên và khoảng cách biến thiên toàn phần giữa chúng.
Ví dụ Giả sử cả hai và là các độ đo “gieo đồng xu” có cùng trọng số 1/2 trên tập các phần tử { }
(i) Một cỏch ghộp à và là xỏc định như là một cặp cỏc đồng xu độc lập, sao cho { } với mọi { }
(ii) Một cỏch khỏc nữa để ghộp à và là giả thiết là một kết quả gieo đồng xu và Trong trường hợp này { } , { } và { }
Cho một cặp của và , nếu q là phân phối kết hợp của trên
, nghĩa là nếu { }, thì q thỏa mãn
Ngược lại, cho một phân phối xác suất trên không gian tích thỏa mãn
Một cặp các biến ngẫu nhiên có thể được xem là phân phối kết hợp của chúng, tạo thành một sự ghép đôi giữa hai biến Thông thường, một cặp này được hiểu là các biến ngẫu nhiên được xác định trên một không gian xác suất chung hoặc thông qua một phân phối q trên không gian tích.
Trở lại ví dụ trên, cặp đôi trong phẩn (i) có thể tươmg đương với phân phối xác suất 1 trên {0,1} 2 được cho bởi
Cũng giống như vậy, cặp trong (ii) có thể được nhận diện với phân phối xác suất 2 được cho bởi
Hai phân phối có thể độc lập và không đồng nhất, nhưng nếu không đồng nhất thì chúng sẽ không thể nhận cùng một giá trị Tuy nhiên, trong mọi trường hợp, một cặp phân phối phải được coi là đồng nhất Khoảng cách giữa hai phân phối sẽ cung cấp câu trả lời cho vấn đề này.
Mệnh đề Giả sử à và là hai phõn phối xỏc suất trờn Khi đú
Chứng minh Đầu tiên chúng ta chú ý rằng với một cặp của và với một biến cố bất kỳ :
(Khi bỏ qua biến cố { } khỏi số hạng thứ hai của hiệu sẽ đưa đến bất đẳng thức thứ nhất) Ngay lập tức suy ra rằng
Để tạo một cặp, chúng ta sử dụng ký hiệu { } tương đương với ‖ ‖ Vùng III được giới hạn bởi { }, thể hiện vùng chồng lấn giữa hai phân phối Cặp ghép được xác định bằng cách chọn một điểm từ các vùng I, II, và III Tuy nhiên, vùng III không được chọn vì lý do cụ thể Đồng thời, chúng ta cần đảm bảo rằng điểm cần thuộc vùng I và điểm cần thuộc vùng II, vì hai vùng này thể hiện các giá trị không bằng nhau.
Một cách hình thức hơn, ta sẽ dùng thủ tục sau để sinh ra và Giả sử
Việc thêm và bớt ∑ vào vế phải ở trên chỉ ra rằng
∑ ∑ [ ] theo (2.5) và phương trình trên ta có
Hình 2.2 Vì mỗi vùng I và II có diện tích ‖𝜇 𝜈‖ 𝑇𝑉 nên vùng III có diện tích ‖𝜇 𝜈‖ 𝑇𝑉
(2.13) Tung một đồng tiền với xác suất mặt sấp bằng
(i) Nếu đồng xu trả về sấp thì chọn một giá trị , theo phân phối xác suất và đặt
(ii) Nếu đồng tiền trả về ngửa thì lấy theo phân phối xác suất
‖ ‖ và chọn một cách độc lập theo phân phối
Chú ý rằng (2.5) đảm bảo rằng I và II là các phân phối xác suất
Phân phối xác suất của biến ngẫu nhiên được xác định rõ ràng, với các giá trị dương trên các tập con rời nhau của không gian mẫu Ω Đặc biệt, trong trường hợp đồng tiền ngửa, chúng ta nhận thấy rằng xác suất chỉ xảy ra khi đồng tiền là sấp Do đó, kết luận rằng xác suất này chỉ có giá trị khi đồng tiền rơi vào trạng thái sấp.
Chú ý Chúng ta đã thấy có một cặp đạt infimum trong (2.8) Ta sẽ gọi những cặp như vậy là tối ưu
Chúng ta đã sẵn sàng để chứng minh rằng các xích Markov không tuần hoàn, tối giản hội tụ tới các phân phối dừng, đây là bước quan trọng để ước lượng tốc độ hội tụ Các giả thiết về tính không tuần hoàn là cần thiết, như đã được nêu trong ví dụ 1.2.1 với chu trình chẵn.
2.2.1 Định lý về sự hội tụ Định lý Giả sử P là tối giản và không tuần hoàn với phân phối dừng Khi đó tồn tại hằng số (0;1), sao cho
Chứng minh rằng, do tính tối giản và không tuần hoàn, theo mệnh đề 1.3.2, tồn tại một số giá trị dương thực sự Giả sử ma trận có | | hàng, trong đó mỗi hàng được biểu diễn dưới dạng vector dòng Với điều kiện đủ nhỏ, ta có thể đưa ra các kết luận cần thiết.
, với mọi Giả sử Phương trình
(2.15) xác định một ma trân nghẫu nhiên
Tính toán trực tiếp để kiểm tra rằng = với ma trận ngẫu nhiên M bất kỳ và với ma trận bất kỳ sao cho
Tiếp theo chúng ta sử dụng quy nạp để chứng tỏ rằng
(2.16) với Thật vậy, nếu , điều đó đúng do (2.15) Giả sử rằng (2.16) đúng với ,
Dùng tính phân phối và khai triển trong số hạng thứ hai (sử dụng (2.15)) dẫn đến
[ ] (2.18) Việc sử dụng và đã chỉ ra rằng
[ ] (2.19) Điều đó khẳng định (2.16) đúng với (giả sử nó đúng với ) và vì thế nó đúng với mọi k
Nhân với và sắp xếp lại các số hạng, ta có
Để hoàn thành chứng minh cho (2.20), ta cần tính tổng các giá trị tuyệt đối của phần tử trong dòng và chia cho 2 Ở vế phải, nhân tử thứ 2 có thể được xem là khoảng cách biến thiên toàn phần giữa các phân phối, và nó bằng 1 Do đó, với bất kỳ giá trị nào, ta có thể kết luận rằng
‖ ‖ (2.21) Chú ý Vì Định lý 2.2.1, phân phối còn được gọi là phân phối cân bằng
2.2.2 Chuẩn hóa khoảng cách tới tính dừng
Giả sử với và nguyên dương Việc đánh giá khoảng cách biến thiên toàn phần cực đại giữa và là mục tiêu chính của chúng ta Định nghĩa
Cực đại của tất cả các khoảng cách biến thiên toàn phần từ phân phối trên tập các trạng thái của một xích Markov được xác định sau khi đạt đến một phân phối dừng.
Mối liên hệ giữa d và thỏa mãn tính chất sau:
Bổ đề 1 Nếu d(t) và được xác định ở (2.22) và (2.23) tương ứng thì
Thời điểm hòa nhập và thời gian đảo ngược
Để xác định thời điểm hòa nhập trong một xích Markov, cần định nghĩa một tham số cho biết khi nào khoảng cách từ trạng thái hiện tại đến phân phối dừng là đủ nhỏ Thời điểm này sẽ giúp ích trong việc phân tích và hiểu rõ hơn về hành vi của xích Markov.
{ } (2.32) Thời điểm hòa nhập được xác định bởi công thức
Thời điểm hòa nhập đánh dấu lần đầu tiên mà khoảng cách giữa phân phối trên tập các trạng thái của một xích Markov và phân phối dừng không vượt quá 1/4.
Bổ đề 1 ở Mục 2.2.2 và (2.31) cho thấy rằng khi l là một số nguyên không âm, ̅ ̅ (2.34) Đặc biệt, với bất đẳng thức trên là đúng
Mặc dù việc chọn 1/4 là không bình thường theo định nghĩa của t mix, nhưng để đảm bảo rằng bất đẳng thức trong (2.34) không trở nên tầm thường và đạt được dạng bất đẳng thức (2.36), một giá trị nhỏ hơn 1/2 là cần thiết.
2.3.2 Thời điểm hòa nhập và thời gian đảo ngược
Ta nhớ rằng nhóm là một tập với một phép toán hai ngôi có tính kết hợp, cùng một phần tử trung hòa sao cho với mọi ,
(ii) Tồn tại phần tử nghịch đảo sao cho
Đối với một phân phối xác suất trên một nhóm, một động ngẫu nhiên được định nghĩa là một xích Markov với không gian trạng thái, trong đó trạng thái hiện tại được chuyển đổi bằng cách nhân bên trái với một phần tử ngẫu nhiên của nhóm, theo xác suất tương ứng Mỗi ma trận chuyển của xích này sẽ có các phần tử phản ánh quá trình chuyển đổi giữa các trạng thái.
Ví dụ ( -chu trình) Giả sử được xác định bới xác suất 1/2 cho 1, và (-
1) trong nhóm cộng xiclic { } Di động ngẫu nhiên đơn giản trên -chu trình đã được giới thiệu trong Ví dụ ở Mục 1.1.2 là di động ngẫu nhiên trên với phân phối tăng Tương tự, nếu phân phối xác định trọng số 1/4 cho cả hai phần tử 1 và , và trọng số 1/2 cho 0 thì di động ngẫu nhiên lười trên -chu trình được trình bày trong Ví dụ ở cuối Mục 1.2.2 là một di động ngẫu nhiên trên với phân phối tăng
Giả sử có một ma trận chuyển của di động ngẫu nhiên trên một nhóm hữu hạn và phân phối đều trên nhóm đó, thì phân phối này sẽ trở thành một phân phối dừng đối với ma trận chuyển.
Chứng minh Giả sử là phân phối tăng của di động ngẫu nhiên Với bất kỳ
(vì nếu đặt thì và do đó )
Ta gọi một phân phối xác suất trên nhóm là phân phối đối xứng nếu với mọi
Mệnh đề 2 Di động ngẫu nhiên trên một nhóm hữu hạn G với phân phối tăng là khả nghịch nếu là đối xứng
Chứng minh Giả sử là phân phối đều trên Với bất kỳ , ta có
| | bằng nhau khi và chỉ khi
Phân phối ngược ̂ trên một nhóm được định nghĩa thông qua ma trận chuyển của di động ngẫu nhiên với phân phối tăng Khi đó, di động ngẫu nhiên với phân phối tăng ̂ sẽ tạo thành xích với thời gian đảo ngược, sử dụng ma trận chuyển ̂ như đã được định nghĩa trong (1.33).
Giả sử P là ma trận chuyển của một di động ngẫu nhiên trên một nhóm với phân phối tăng, và ̂ là ma trận chuyển của di động ngẫu nhiên trên với phân phối tăng ̂ Nếu phân phối là đều trên, thì đối với bất kỳ , ta có mối quan hệ nhất định giữa các yếu tố này.
Giả sử chúng ta có một xích Markov với ma trận chuyển và trạng thái ban đầu id, trong đó các phần tử ngẫu nhiên được chọn độc lập theo phân phối Tương tự, với một xích khác có ma trận chuyển ̂, các mức tăng được chọn độc lập từ ̂ với các phần tử cố định bất kỳ Xác suất trong trường hợp này sẽ được xác định dựa trên các yếu tố này.
{ } { } theo định nghĩa của ̂, việc lấy tổng trên tất cả các chuỗi sao cho dẫn tới ̂
Và công thức đó cùng với Mệnh đề 1 Mục 2.1.1 khẳng định đẳng thức cần chứng minh
Hệ quả Nếu là thời điểm hòa nhập của di động ngẫu nhiên trên một nhóm và ̂ là thời điểm hòa nhập của di động ngược thì ̂
Việc đảo ngược một chuỗi Markov có thể ảnh hưởng đáng kể đến thời điểm hòa nhập, ví dụ như "khoảng thắng cuộc" Chúng ta sẽ chỉ xem xét thời điểm hòa nhập trong bối cảnh thời gian ngược của chuỗi này.
Hãy tưởng tượng việc lặp đi lặp lại việc tung một đồng xu cân đối và ghi lại kết quả của những lần gieo mặt sấp vào một thẻ nhớ có dung lượng hạn chế Nếu có nhiều lần sấp trên một dòng, thẻ nhớ chỉ lưu giữ số lần sấp ít hơn giữa hai số và độ dài tối đa của số lần sấp được chấp nhận.
Cửa sổ có chiều rộng được xem như một chuyển động sang bên phải qua một chuỗi hữu hạn các bit độc lập, với độ dài của khối các bit 1 bắt đầu từ điểm tận cùng bên phải Điều này tạo thành một chuỗi Markov với không gian trạng thái { } và các xác suất chuyển khác 0 được xác định bởi.
Thời điểm t 1 0 1 0 0 1 1 1 0 0 0 0 Thời điểm t+1 1 0 1 0 0 1 1 1 0 0 0 0 Thời điểm t+2 1 0 1 0 0 1 1 1 0 0 0 0
Thời điểm t 1 0 1 0 0 1 1 1 0 0 0 0 Thời điểm t+1 1 0 1 0 0 1 1 1 0 0 0 0 Thời điểm t+2 1 0 1 0 0 1 1 1 0 0 0 0
Khoảng thắng cuộc với n=5 Ở đây 𝑋 𝑡 𝑋 𝑡 𝑋 𝑡
Xem hình 2.3 và 2.5 Kiểm tra trực tiếp được rằng
(2.38) là dừng với và cũng kiểm tra trực tiếp được rằng thời gian đảo ngược của có các thành phần khác 0 ̂ ̂ ̂ (2.39)
Hình dung một cửa sổ rộng di chuyển sang trái, hiển thị một chuỗi các bit ngẫu nhiên độc lập Dãy bit 1 ở phía bên phải của cửa sổ, có độ dài ( ̂ ), chính là phiên bản ngược của "khoảng thắng cuộc" của xích Xem hình 2.4 và 2.5 để hiểu rõ hơn.
Thời gian ngược của khoảng hỗn hợp có những đặc điểm nổi bật, trong đó sau bước phân phối, nó sẽ dừng lại bất chấp phân phối ban đầu.
Hình 2.5 Các đồ thị của các chuyển động của
(a) Khoảng thắng cuộc của xích với n=5 (b) Khoảng thắng cuộc thời gian đảo ngược của nó
Thời gian ngược của khoảng thắng cuộc với n=5 cho thấy rằng nếu 𝑋̂ 𝑡 dừng đối với mọi t, thì phân phối của 𝑋̂ 𝑡 cũng sẽ dừng Khi 𝑋̂ không dừng, phép chuyển phụ thuộc vào thời gian và xích sẽ dừng đối với t > k Nếu 𝑋̂ phụ thuộc vào thời gian xích tồn tại trước khi hòa nhập, thì xích có xác suất chiếm thời điểm và chuyển sang thời điểm thứ n Trong trường hợp này, 𝑋̂ và 𝑋̂ đều liên quan đến nhau Nếu phân phối ban đầu không tập trung tại một trạng thái đơn, thì phân phối tại thời điểm n là sự hòa nhập của các phân phối từ mỗi trạng thái ban đầu và do đó cũng dừng Cuối cùng, nếu xích bắt đầu tại một trạng thái và ngay sau đó dịch chuyển, thì tại thời điểm đó nó cần đạt trạng thái 1, cho thấy mối liên hệ giữa 𝑋̂ và khoảng cách biến thiên toàn phần.
Ta kết luận rằng đối với xích “khoảng thắng cuộc” ngược, thì với số dương bất kỳ