Re: [機統] 連續為1的機率怎麼求
※ 引述《qqq04737084 (qqq332)》之銘言：
: 各位好
: 小弟目前在研究上遇到一個問題，如標題所示想要找在n個bit內連續N個bit都是1的
: 機率。(N小於等於n)
: 舉例來說，四個位元(n=4)的所有可能性為:
: 0:0000
: 1:0001
: 2:0010
: 3:0011
: 4:0100
: 5:0101
: 6:0110
: 7:0111
: 8:1000
: 9:1001
: 10:1010
: 11:1011
: 12:1100
: 13:1101
: 14:1110
: 15:1111
: 假設想找N=2(連續兩個bit都為1的機率)，因此滿足的有:
: 3:0011
: 6:0110
: 7:0111
: 11:1011
: 12:1100
: 13:1101
: 14:1110
: 15:1111
: 總共8個case
: 換算成機率即為:8/16
: 如果N=3，那麼滿足的只剩下:
: 7:0111
: 14:1110
: 15:1111
: 總共3個case
: 換算成機率即為:3/16
: 想請問有辦法將機率用變數n與N表示嗎?
: PS:我有寫程式算出n與N較大時的情況，為了讓大家驗證推導出的公式是否正確，因此在
: 此列出一個N=16，n=1~16的所有機率
: N=16
: n=1, P=0.99998
: n=2, P=0.96057
: n=3, P=0.70226
: n=4, P=0.39502
: n=5, P=0.19653
: n=6, P=0.092896
: n=7, P=0.042892
: n=8, P=0.019531
: n=9, P=0.0087891
: n=10, P=0.0039063
: n=11, P=0.001709
: n=12, P=0.00073242
: n=13, P=0.00030518
: n=14, P=0.00012207
: n=15, P=4.5776e-05
: n=16, P=1.5259e-05
你的符號有點亂掉了
設在 n 個 bits 中,不出現連續 k 個 1 的機率為 q_k(n)=q(n) (k固定)
q(0)=q(1)=..=q(k-1)=1,q(k)=1-2^{-k}
1-q(n)=2^{-k}+2^{-k-1}(q(0)+q(1)+..+q(n-k-1)),其中 n≧k+1
設 Q(x)=Σ q(n) x^n
n≧0
1 2^{-k} x^{k+1} 1-x^k
=> ----- - Q(x) = -------- + 2^{-k-1}*---------*Q(x)-2^{-k}*-------
1-x 1-x 1-x 1-x
1-2^{-k}x^k
=> Q(x)=---------------------
1-x+2^{-k-1}x^{k+1}
1-y^k 1 1-y^k
令y=x/2 => q(n)=[x^n]Q(x)=[(2y)^n] -------------- = -----[y^n] -------------
1-2y+y^{k+1} 2^n 1-2y+y^{k+1}
所求 = 1-q(n)
eg. k=3,n=16
1 1-y^3
q_3(16)= ------ [y^16] ----------
2^16 1-2y+y^4
用綜合除法
1 0 0 -1
----
+2 2 4 8 14 26 48 88 162 298 548 1008 1854 3410 6272 11536 21218
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1 -1 -2 -4 -7 -13 -24 -44 -81 -149 -274 -504 -927 -1705
----------------------------------------------------------------------------
1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513
19513
=> q_3(16)= -------
2^16
19513
=> 1- ------- ~ 0.702255
2^16
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.109.16.69
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1426756691.A.64E.html
推
03/20 10:00, , 1F
03/20 10:00, 1F
推
03/20 10:07, , 2F
03/20 10:07, 2F
→
03/20 10:23, , 3F
03/20 10:23, 3F
討論串 (同標題文章)