Bài 5

Ngân hàng Bath phát hành các đồng xu có mặt ở một phía và mặt ở phía kia. Harry có đồng xu này, xếp thành một hàng từ trái sang phải. Anh lặp lại thao tác sau: nếu có đúng đồng xu ngửa mặt , anh lật đồng xu thứ từ trái sang; nếu không thì tất cả đồng xu đều là và anh dừng lại. Chẳng hạn, khi , quá trình bắt đầu từ là , dừng sau ba thao tác. (a) Chứng minh rằng với mỗi cấu hình ban đầu, Harry dừng sau hữu hạn thao tác. (b) Với mỗi cấu hình ban đầu , gọi là số thao tác trước khi dừng. Hãy xác định giá trị trung bình của trên tất cả cấu hình ban đầu.

H

T

n

k>0

H

k

T

n=3

THT

THT\to HHT\to HTT\to TTT

C

L(C)

L(C)

2^n

Bước 1 trên 6: Đặt giá trị kỳ vọng

Bước trước Bước tiếp

Hiểu nôm na

Ta chứng minh tính dừng và tính trung bình cùng lúc.

E_n=\mathbb E[L(C)]

Phân tích chi tiết

Gọi là số thao tác trung bình với đồng xu. Ta quy nạp theo . Với , hai cấu hình và lần lượt cần và thao tác, nên quá trình dừng và . $E_n$ $n$ $n$ $n=1$ $T$ $H$ $0$ $1$ $E_1=\frac12$