solution

Tung một đồng xu cân đối (mặt Sấp/Ngửa đồng khả năng) độc lập $n$ lần liên tiếp, tạo thành một dãy nhị phân độ dài $n$ trong không gian mẫu gồm $2^n$ dãy đồng khả năng. Tính xác suất để không có $k$ lần liên tiếp ra cùng một mặt ở bất kỳ vị trí nào trong dãy (tức là mọi "run" — đoạn con gồm các lần tung liên tiếp ra cùng mặt — đều có độ dài nhỏ hơn $k$).

Gợi ý: dùng quy hoạch động theo (mặt hiện tại, độ dài run hiện tại) để đếm số dãy hợp lệ, sau đó chia cho $2^n$.

Quy ước đặc biệt: nếu $n = 0$ (không tung lần nào), xác suất bằng $1$. Nếu $k = 1$ và $n \ge 1$, không thể tránh một run độ dài $\ge 1$ nên xác suất bằng $0$.

Ví dụ: $n=3, k=2$ (không có 2 lần liên tiếp giống nhau, tức dãy phải xen kẽ tuyệt đối): chỉ có 2 dãy hợp lệ là SNS và NSN trong 8 dãy, xác suất $= 2/8 = 1/4$.