Phân tích

Nói chung, không thể chỉ dịch chuyển tức thời đến mọi phòng vì \(N\) có thể lớn hơn \(K\) rất nhiều. Ta có thể dịch chuyển đến một tập con phòng được chọn ngẫu nhiên, tính bậc trung bình — số lối đi kề — của các phòng đã thăm, rồi giả sử đây là một ước lượng tốt cho bậc trung bình của mọi phòng. Số lối đi bằng một nửa tổng bậc các phòng, vì mỗi lối đi nối hai phòng.

Khi nào cách này cho ước lượng tệ? Nếu một tập nhỏ các phòng có bậc cao hơn hoặc thấp hơn trung vị rất nhiều, ta có thể không ghé phòng nào trong số đó, khiến ước lượng quá cao hoặc quá thấp.

Trường hợp phần lớn phòng có bậc cao còn một số ít có bậc thấp không phải vấn đề, vì bài được chấm theo sai số tương đối và sai số tương đối khi ấy nhỏ. Nếu bậc trung bình là \(100\) nhưng ta ước lượng \(103\), sai số chỉ \(3\%\). Nhưng nếu bậc trung bình là \(5\) mà ta ước lượng \(2\), sai số lên tới \(60\%\).

Vì vậy, hãy xét trường hợp khó: phần lớn phòng có bậc thấp, còn một tập nhỏ phòng có bậc cao — ít đến mức khó gặp chúng bằng cách dịch chuyển ngẫu nhiên. Nếu các phòng bậc cao đóng góp một phần đáng kể trong tổng số lối đi, chúng phải nối đến một phần đáng kể của toàn bộ tập phòng. Do đó, ta có xác suất cao tìm được chúng bằng cách liên tục dịch chuyển đến một phòng ngẫu nhiên rồi đi qua một lối ngẫu nhiên bằng lệnh W.

Xét một chuỗi vòng, trong đó ta xen kẽ lệnh T để dịch chuyển đến một phòng ngẫu nhiên và lệnh W để đi qua một lối ngẫu nhiên. Không thể đơn thuần lấy bậc trung bình của mọi phòng đã thấy để suy ra bậc trung bình toàn hang, vì các phòng đến được bằng W không phải mẫu đều. Tuy nhiên, ta có thể dùng bậc trung bình chỉ của các phòng đã thăm bằng T làm ước lượng cho mọi phòng chưa thăm, rồi cộng thêm các bậc đã biết. Như vậy là đủ để giải bài.

Một lời giải khác cũng xen kẽ T và W, nhưng dùng kỹ thuật importance sampling. Mỗi lần ghé một phòng cho ta một mẫu của bậc trung bình, nhưng các phòng không có cùng xác suất xuất hiện trong mỗi mẫu. Bằng cách gán trọng số phù hợp cho từng mẫu, ta tính được trung bình có trọng số, là một ước lượng không chệch của tổng. Các trọng số bù lại xác suất ghé phòng không đồng đều.

Khi chọn ngẫu nhiên một phòng và ghé bằng lệnh T, mọi phòng có xác suất được chọn như nhau; gán mẫu này trọng số \(1\). Khi ghé phòng bằng lệnh W, xác suất không còn đều. Ta cần chọn trọng số sao cho trọng số kỳ vọng của mỗi phòng — xác suất ghé phòng đó bằng W nhân với trọng số kỳ vọng gán cho những lần ghé như vậy — bằng \(1/N\). Khi đó, ước lượng cuối cùng có đúng giá trị kỳ vọng.

Xét một mẫu mà trước đó ta ở phòng \(R_1\) có bậc \(A\), rồi dùng W và đi vào phòng \(R_2\) có bậc \(B\). Xác suất ở \(R_1\) sau lệnh T trước đó là \(1/N\). Xác suất chọn đúng lối dẫn đến \(R_2\) là \(1/A\), vì \(R_1\) có \(A\) lối đi. Do đó xác suất tổng là \(1/(AN)\). Gán mẫu này trọng số \(A/B\), nên đóng góp của nó vào trọng số kỳ vọng của \(R_2\) là \(1/(BN)\). Cộng trên cả \(B\) cách có thể đi vào \(R_2\), tổng trọng số kỳ vọng của \(R_2\) bằng \(1/N\), đúng như yêu cầu.

Ví dụ, xét tương tác sau:

T 1
1 1
W
3 2
T 2
2 1
W
3 2
T 3
3 2
W
1 1

Ta thu được các mẫu bậc \(1,2,1,2,2,1\) với trọng số tương ứng \(1,1/2,1,1/2,1,2\), và bậc trung bình có trọng số là \(8/6\).

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2022, Qualification Round.