感覺很有意思的機率題，路過答一波。整個解題過程分兩步走，第一步說明極限存在，第二步說明極限是2/(k + 1).

令 表示踩到 的機率. 要證明的就是 。整個證明運用到的核心公式就是：

公式其實理解起來不難，第一次行動如果走1步，要想走到n+k,接下來需要走n + k - 1 步，相當於從0走到n + k - 1.這種情況發生的機率是 .類似地，第一次走兩步，三步，以此類推就能得到上面的公式。

為什麼先講這個公式呢，因為感覺接下來說明極限存在地話會好說清楚一點。令 , 。其實證明的核心思路就在於, 遞減， 遞增，並且兩者必須趨於同一個數。具體證明分三步走：

1.因為 是前k個數的均值，肯定不大於 , 肯定不小於 , 由此導致 遞減， 遞增。

2.單調收斂定理告訴我們，

3.假設 ， 當n很大時， , 於是從 開始， 最多隻有 ， 選取合是的 , 這玩意兒肯定小於U. 然後就導致 ,矛盾。

以上是極限存在性證明，然後就來算算極限具體是多少。假設 . 這裡演算法的核心思想就是，這個人一定會走過(n, n+1, n+2, ..., n + k - 1)中的某一步。換句話說，假設 ，這個人走到 中的機率是1。令 表示第一次走到 中時踩到的位置是 的機率。我們有

(第一次進入 踩到n + i的機率等於踩到n + i的機率減去從 中先踩到其它點，然後再走到n + i的機率)

由於 ， 當然在極限情況下也是1. 那把遞推公式中的 用 替換掉，並利用 , 則我們有：

.

.

全加起來和是1， 同時也是({k + 1}/{2})A, 解出來A=2/(k + 1)