扔骰子遊戲，將之前投的點數全部相加，恰好能在某一次後等於 2015 的概率是多少？

12-15

這是一道阿里巴巴的筆試題：

這個是更新過程。參見Blackwell renewal theorem的lattice情形。
如果隨機變數X_i有lattice d，即X_i的所有取值可以寫成n*d,數學期望為mu
則序列Sm=X1+X2+...+Xm在nd處更新次數的期望收斂於d/mu當n趨於無窮

此題目的d就是1，所以是期望的倒數
不知有人能否通俗的講一下？
Blackwell renewal theorem

我也給個思路：
事實上，到2011、2012、2013、2014、2015、2016的概率都是一樣的，記為P。

超過2015的概率是：1-P
超過2015的概率也是：
在2014時投出「2,3,4,5,6」，或在2013時投出「3,4,5,6」，或在2012時投出。。。即：
$Pcdot frac{5}{6}+Pcdot frac{4}{6}+Pcdot frac{3}{6}+Pcdot frac{2}{6}+Pcdot frac{1}{6}$

綜合公式： $1-P=Pcdot frac{5}{6}+Pcdot frac{4}{6}+Pcdot frac{3}{6}+Pcdot frac{2}{6}+Pcdot frac{1}{6}$
解出： $P=frac{2}{7}$

謝邀。

這題給我做，不考慮投機的方法，只要 1 分鐘就能得到正確答案。

首先，如果這道題出現在阿里的筆試題上，那麼一定是限時間的。
這個時候，不要想什麼嚴格的演算法，儘快把題目做出來且 確保正確性 是王道啊！

怎麼辦呢？

我靈機一動：

第一步，打開 Excel
第二步：輸入以下幾行：

（其中 N 為到達的數，prob 為到達該數的可能性）

第三步：輸入以下公式
（這個遞歸式很容易理解吧？出現一個值的概率是前面 6 個值的平均數，因為它可能是前面的值投了 1、2、3、4、5、6 而到的這個數）

第四步：下拉

第五步：向下觀察

很明顯「看出」，答案收斂於 2/7

你看，真的只要 1 分鐘就做出來了。

所以啊，最強大的編程工具，其實是 Excel 啊！

********************

如果要嚴格證明的話……

先證明收斂性（以下應該是高中理科數學的知識）

這個遞歸數列是： $p_{n+6} =frac{1}{6} (p_{n+5} +p_{n+4} +p_{n+3} +p_{n+2}+ p_{n+1} +p_{n} )$
特徵方程是： $x^{6} =frac{1}{6} (x^{5} +x^{4} +x^{3} +x^{2}+ x +1 )$

用手算求出所有根有點難度。

但易見，

這個方程所有根的模都不大於1

證：

若 $left| x ight| geq 1$ , 則 $left |x^{6} ight|geq left |x^{5} ight|geqleft |x^{4} ight| geqleft |x^{3} ight| geqleft |x^{2} ight| geqleft |x ight| geq1$ ，

於是，有條件，有
$left| x^{6} ight| =frac{1}{6} left| x^{5} +x^{4} +x^{3} +x^{2}+ x +1 ight|$
$leq frac{1}{6}( left| x^{5} ight| +left| x^{4} ight|+ left| x^{3} ight|+ left| x^{2} ight|+ left| x ight| +1) leq left| x^{6} ight|$

等號當且僅當 x=1 時成立

故模不小於 1 的根僅有 x=1 ，其他根的模都小於 1；
進一步可知， x=1 不是重根（余式為： $6x^{5}+ 5x^{4} +4x^{3}+ 3x^{2}+ 2x+1$ ），

假如方程沒有重根，通項公式可以寫為： $p_{n}=sum_{i=1}^{6}{a_{i}x_{i}^{n} }$
有重根時，k 維重根在 $a_{i}x_{i}^{n}$ 這一項表達式變為 $x_{i}^{n}sum_{j=0}^{k}{b_{j} n^{j} }$ ，如果 $left|x_{i} ight|<1$ , 這一項會隨著 n 的增大而趨於 0 （指數增長比多項式增長快，這一點的嚴格證明可用洛必達法則）；

故綜合以上兩點，數列必然是收斂的，且收斂於 x=1 這個根對應的常數項係數。

證明收斂以後，方法就有很多了，比如期望 3.5 的倒數（但這個方法並不嚴格）

一個比較好的方法是：

令恰好到達 2015 概率為 p，則超過 2015 的概率為 1-p

而超過 2015 可能是

到 2014 時投了 2~6
到 2013 時投了 3~6
到 2012 時投了 4~6
到 2011 時投了 5、6
到 2010 時投了 6

則有 $1-papprox frac{5+4+3+2+1}{6} p$

則 $papprox frac{2}{7}$

********************

直接用平均期望 3.5 取倒數的方法么……算比較投機的演算法。
在這道題上恰好是對的，但是這種方法比較危險，因為數列的收斂性常常並不是顯然的。

********************

P.S. 這個回答好像被點了幾個反對？所以請問它哪裡錯了呢 o(^▽^)o

來個暴力模擬的方法吧：
代碼與注釋如下：

/** 模擬一個持續擲篩子的過程，返回這個過程中篩子之和是否恰好出現過total */ def simulate(total: Int, dice: Int): Boolean = { //itr為一個Iterator，其值由1,2,...,dice中隨機生成 val itr = Iterator.fill(total)(util.Random.nextInt(dice) + 1) //返回itr的累加和中是否出現過total itr.scanLeft(0)(_+_).find(_ &>= total).get == total }

//simCnt為模擬的次數，此處模擬100萬次，在我的電腦上大約需要10秒 val simCnt = 1000000 //成功的概率 Iterator.fill(simCnt)(simulate(2015, 6)).filter(_ == true).size / simCnt.toDouble

程序運行結果如下：

scala&> def simulate(total: Int, dice: Int): Boolean = { | val itr = Iterator.fill(total)(util.Random.nextInt(dice) + 1) | itr.scanLeft(0)(_+_).find(_ &>= total).get == total | } simulate: (total: Int, dice: Int)Boolean


scala&> 
scala&> val simCnt = 1000000

simCnt: Int = 1000000
scala&> 
scala&> Iterator.fill(simCnt)(simulate(2015, 6)).filter(_ == true).size / simCnt.toDouble

res1: Double = 0.286336

scala&> res1 * 7 res2: Double = 2.004352

一秒搞定啊。期望3.5，取倒數就行。

4月3日補充:感謝大家的贊同、評論和質疑，也感謝商隱知友給出的專業解釋，我只是知道她說的定理的結論而已。

感謝王贇知友的解釋（一直不知道怎麼說）:在足夠長時間之後，平均每次前進3.5步，因此平均停留次數就是1/3.5。

碼農是不懂數學了，不過上面可以歸結為遞推式。
假設設f(n) = 扔骰子遊戲，將之前投的點數全部相加，恰好能在某一次後等於 N 的概率.
得到N之前假設最後一次扔骰子是1-6.每一種可能都是1.0/6
那麼f(n) = f(n-1) * p + f(n-2) * p + f(n-3) * p + ...
明顯f(0) = 1.
那麼上面就是個遞推式，用程序跑一下就可以了，
時間複雜度O(n).
對於時間複雜度，似乎有誤，如果骰子有M面，那麼時間複雜度應當為O(M*N)--&>O(N*N).
所以還是比較慢的，如果可以用數學方法還是用數學方法為好。

js代碼如下。

function f(n){ var i, j, res, p = 1.0 / 6, tmp_ls = [1]; for (i = 1; i &<= n; i++) { res = 0; for(j = 1; j &<= 6; j ++){ if(i &>= j){ res += tmp_ls[i-j] * p; } } tmp_ls.push(res); } return tmp_ls[n]; }

然後結果是。0.2857142857142852 差不多等於2/7.然後所有大於10的數的結果都近似到得這個結果，應該有數學公式可以證明(碼農無力)。

10秒搞定，每次投擲的均值是3.5，也就是每擲骰子十次的求和平均數學期望是35。顯然超過一定量以後每個數字出現的概率一樣，2015和2016沒有概率上的分別，那概率就是10除以35。
早起想了幾分鐘，其實只要證明隨機函數的均值收斂就可以了，這個很簡單，直接套用伊普西隆方法就行，所以這個問題條件可以更絕對一點的。這樣嚴密性就沒有問題了。
這問題大概10秒鐘就可以猜個答案，嚴格證明的話受過大學數學訓練的估計十分鐘吧。

實在不行可以直接蒙啊……
答案中出現兩次二，兩次七，就選二和七都有的……

我也提供一種思路吧，對於任意一個N（例如2015），在最後一步達成N或超過N共有這樣的可能性：
①達成N有6種：（N-6）至（N-1）各1種。
②超過N有15種：（N-5）1種、（N-4）2種、（N-3）3種、（N-2）4種、（N-1）5種。
所以達成N的可能性為6/（6+15）=2/7.

投完後還不足N是不用考慮的，那就說明還不是最後一投，還是會歸入上面的情況中。

我的程序計算顯示答案是2/7
測試100000次，結果2015，其中達到目標28554次，比例0.28554
測試100000次，結果2015，其中達到目標28388次，比例0.28388
測試100000次，結果2015，其中達到目標28730次，比例0.2873
測試100000次，結果2015，其中達到目標28622次，比例0.28622
測試100000次，結果2015，其中達到目標28639次，比例0.28639
測試100000次，結果2015，其中達到目標28451次，比例0.28451
測試100000次，結果2015，其中達到目標28512次，比例0.28512
測試100000次，結果2015，其中達到目標28566次，比例0.28566
測試100000次，結果2015，其中達到目標28701次，比例0.28701
測試100000次，結果2015，其中達到目標28561次，比例0.28561
測試100000次，結果2015，其中達到目標28767次，比例0.28767

一次能到2015有6種可能（2009+6）,（2010+5）,（2011+4）,（2012+3),(2013+2),(2014+1).
一次超過2015的15種可能
5(2014+2/3/4/5/6)+
4（2013+3/4/5/6）+
3（2012+4/5/6）+
2（2011+5/6）+
1（2010+6）=15
成功的的概率=6/（6（成功）+15（失敗））=6/21=2/7。
就醬~

大家都回答得好快啊…我只能看看收斂性了…

可以從基礎的數學歸納法來想，很像跨樓梯，就是一次可以選擇跨1/2/3個台階，……那個問的問題我忘記了，不過方法是一樣的！
假設對於1和n之間的所有整數，都存在f（n），表示恰好能加出n的概率，則f（n+1）可以表示為簡單的線性組合：
f（n+1）=（f（n-5）加到f（n））/6

…………
這樣好像就能證出它收斂了吧…？
至於數值…………我明天再來答…先睡覺了…=_=

難道不是六分之一么？投最後一次之前肯定和2015還差不到6啊，那麼投出想要的數字不是六分之一么？笨方法，哈哈

//點反對的人啊……拿衣服！

噫，數學什麼的我都不知道啊但我寫個代碼分分鐘搞定嘛，我投個十萬次統計一下頻率不就行了？
來。

#include & #include & #include & #define N 100000 int main() { int S = 0, sum, i; srand(time(NULL)); for(i = 0; i &< N; ++i) { sum = 0; while(sum &< 2015) { sum += rand() % 6 + 1; } if(sum == 2015) { ++S; } } printf("%f ", S*1.0/N); printf("%f ", 2/7.0); return 0; }

嗯。。好像差不多？那就是2/7沒錯了！
蒙特卡洛大法好
//下面是正常的解法 (DP)

#include & #include &

double P(int); int main() { printf("%f ", P(2015)); return 0; } double P(int n) { int i, j; double *p; p = (double*)malloc(sizeof(double)*(n+1)); p[0] = 1;//和是0的概率為1 for(i = 1; i &< n+1; ++i) { p[i] = 0; for(j = 1; j &<= 6; ++j) { if(i-j &>= 0) { p[i] += p[i - j] * (1.0 / 6); //p[i]的解依賴於前六項中的非負項 } } } return p[n]; }

如果不寫代碼的話。。我可能一時半會兒做不出來這道題。