Re: [機統] 不重複取球的機率

[LPH66 (信じる力 奇跡起こすこと)]

寫一下我的做法好了

※ 引述《xxxx9659 (嘎嘎嘎嘎嘎)》之銘言：
: 最近在算一個機率問題
: 有 n 顆球 編號 1 ~ n
: 每次取一顆球 取後放回
: 求取了 k 次 結果沒有任何一顆球的編號重複的機率
: 我覺得算式是這樣
:   C(n,k) / k!
:  -------------
:       n^k
: 或是這樣寫
:    P(n,k)
:  ----------
:     n^k
: 如果令 k = n^0.5 而且 n 超級大的情況下
: 我用 excel 算出來大約是 0.60649...
: 我想問的是 這個值最後會不會收斂成一個定值阿？
: 感覺是跟自然常數 e 有關 但是又說不出什麼有關係...
: 希望各位大大幫我解答 或是給我一些方向
: 感謝
先寫一個不很嚴謹的做法

這機率可以寫成 P = (n/n)*[(n-1)/n]*[(n-2)/n]*...*[(n-k+1)/n]

取對數得 ln P = ln(n/n) + ln[(n-1)/n] + ln[(n-2)/n] + ... + ln[(n-k+1)/n]

嘗試把右邊看成 ln x 由 x=(n-k)/n 到 1 的積分的黎曼和, 會發現需要補一個 1/n

                                1
補上去之後把右邊近似(!)成 n * ∫         ln x dx
                                1-1/√n

容易發現在 n→∞ 時這是 ∞*0 的不定型, 所以把 n 搬到分母後羅必達一次

        -ln(1-1/√n) * (-1)(-1/2)(n^(-3/2))
會得到 ------------------------------------- = ln(1-1/√n) * (1/2)√n
                      -n^(-2)

又是 0*∞, 所以一樣把 √n 搬到分母再羅必達一次

        (1/2)/(1-1/√n) * (-1)(-1/2)(n^(-3/2))
就得到 ---------------------------------------- = -(1/2)/(1-1/√n) → -1/2
                  (-1/2)(n^(-3/2))

所以 P → e^(-1/2) ≒ 0.606531

上面這個做法不嚴謹的地方在 (!) 那裡, 因為那裡把式子的一部份先取了極限

不過嚴謹的做法應該只需要稍微調整:

在 (!) 那裡把和式夾在兩個積分中間, 一個是上式 (原式是上式積分的黎曼上和)

另一個則是拿掉 ln(n/n) = ln 1 = 0 之後變成另一個積分的黎曼下和

這兩個積分只差在下限不一樣, 後一個積分下限是 (n-k+1)/n

所以求極限過程 (雖然稍微繁了些但) 大同小異, 最後一步的極限下去都逼近 -1/2

這樣就能嚴謹地夾出 ln P 的極限是 -1/2 了

--
1985/01/12 三嶋鳴海 1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町
つぐみ 歡迎來到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬
チサト 1998/06/18 守野くるみ 打越鋼太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遙
2002/12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 ∞與∫的世界 2011/04/02 茜崎空
啟動 2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞 2019/04/01~07 某大學合宿

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.3.123 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1572856897.A.2F7.html
※ 編輯: LPH66 (180.177.3.123 臺灣), 11/04/2019 16:43:56
※ 編輯: LPH66 (180.177.3.123 臺灣), 11/04/2019 16:46:46
推 xxxx9659    : 哇~~感謝簡單易懂的解說!! LPH大大好帥!!!!!
推 xxxx9659    : 找到泛用解了   e^( -k^2 / 2n )
→ wohtp       : 原po這個一般解顯然是錯的。k=1的時候機率必須是1。
推 xxxx9659    : k=1是錯的 但在 n, k 很大的情況下會趨近於這個解
推 wohtp       : n = k 的極限應該是 exp(-z) sqrt(2 pi / z)
→ wohtp       : 所以你大概還要補上 k << n 之類的條件
→ wohtp       : 啊，z=n=k，不好意思沒改名過來
推 xxxx9659    : 還要 k << n  感謝w大大