應該如何處理 Project Euler 問題 213（“跳蚤馬戲團”）？

我想解決Project Euler 213但不知道從哪裡開始，因為我是統計學領域的外行，請注意需要準確的答案，因此蒙特卡洛方法不起作用。您能推荐一些統計主題供我繼續閱讀嗎？請不要在此處發布解決方案。

跳蚤馬戲團

一個 30×30 的方格包含 900 只跳蚤，最初每方格有一隻跳蚤。當鈴聲響起時，每隻跳蚤都會隨機跳到相鄰的方格（通常有 4 種可能性，除了在網格邊緣或角落的跳蚤）。

鈴響 50 次後，預期的空置格子數是多少？將您的答案四捨五入到小數點後六位。

你說得對; 蒙特卡洛是行不通的。（在一個簡單的模擬中——也就是說，在沒有任何簡化的情況下準確再現問題情況——每次迭代將涉及 900 次跳蚤動作。對空單元比例的粗略估計是, 暗示蒙特卡洛估計的方差這樣的迭代大約是. 要將答案確定到小數點後六位，您需要將其估計在 5.E-7 以內，並且要達到 95+%（例如）的置信度，您必須將該精度大約減半至 2.5E-7 . 求解給， 大約。那將是大約 3.6E15 次跳蚤動作，每個動作都佔用 CPU 的幾個滴答聲。有了一個可用的現代 CPU，您將需要一整年的（高效）計算。而且我有些錯誤和過於樂觀地假設答案是作為比例而不是計數給出的：作為計數，它需要三個更有效的數字，計算量增加一百萬倍……你能等很長時間嗎？）

就分析解決方案而言，可以進行一些簡化。（這些也可以用來縮短蒙特卡洛計算。）空單元的預期數量是所有單元的空概率之和。要找到這一點，您可以計算每個單元格的入住人數的概率分佈。這些分佈是通過對每個跳蚤的（獨立的！）貢獻求和獲得的。這將您的問題減少到在該網格上的任何給定單元格之間沿 30 x 30 網格查找長度為 50 的路徑的數量（一個是跳蚤的原點，另一個是您要計算概率的單元格跳蚤的佔用）。

引用自：https://stats.stackexchange.com/questions/2427