Random遊戲的期望次數分析

遊戲規則：首先取一個上界x（一般取x=1e9），然後在計算器上不斷取x=random（0，x），直到x=0。在這個過程中調用random次數多的人獲勝。

由於要分析期望次數，可假設計算器每次都在[0，x]間取一真隨機數。

分析過程：如我們假設，對於某一初始值x，其期望次數為ax 。我們會得到這樣的關係：（由於我們知道，調用random（0，n），會以的概率產生（0，n）間的每個數，因此每個期望的概率要除以（n+1），至於分子上的這個+1，是因為為達此狀態已進行了一步操作）。另外，顯然等於0（此處補充：有人計算出=1+，zhszhzh，無法在O(1)時間內進行求和）。

將上式進一步化簡，若令，則可化簡為，在此以後我們就可以以O(n)的時間複雜度計算出()。

另外，如果列舉一些結果:

很容易發現，當n>10000後，兩項間的差距總為2.3026（即為In10）。這表示可以將其擬合為一個對數函數。經過計算，得到f(n)=In(n)+1.5772。此函數在n>10000時可以擬合的很好，但n若較小則會有較大偏差。

另外，關於上界x取n時的概率分布，依然可以這樣遞推地構造。若令f(n)為上界取n時的概率圖像，且假設我們已知道f(0),f(1),f(2)……,f(n-1)，則f(n)的圖像可以這麼構造：

①將f(0),f(1),f(2)……,f(n-1)的圖像縱坐標除以(n+1)，並向右平移一。

②將n個圖像合成為一個總圖像。

③將總圖像無限進行如下操作：

①縱坐標除以(n+1)

②向右平移一

以上。

推薦閱讀：