推 Binomial5566: 有點像 Bernstein inequality? 06/04 21:55
→ thr3ee : 好像就是這個不等式沒錯 謝謝你 06/05 11:40
轉貼昌爸工作坊20170530有人發問的一道問題
原文如下:
假設現在箱子內有兩顆球 一顆球上面寫+1 一顆球上面寫-1
現在有一個人做抽樣實驗 假設他心中有一個初始數字0
然後隨機從箱子內抽出一顆球
只要上面寫+1 就讓心中的數字+1
只要上面寫-1 就讓心中的數字-1
之後再將球放回去 然後繼續隨機抽一顆球 一直循環這個過程
問題: 給定一個數字n
請問至少要持續這個過程多少次
才會有大於(1-1/n)的機率使得心中數字的絕對值曾經大於n?
(答案用n表達 不一定要最佳解 可以給出一個上界)
---------------------------------
目前有一個人回答:
有一個遞迴關係 不知道有沒有用
假設k次抽球 心中數字絕對值大於n的機率是P(n,k)
則P(n,k+1)=P(n,k)+0.5*P(n-1,k)
我猜應該可以暴力展開做出來
原作者回答:
暴力展開似乎非常難做 因此應該沒辦法輕易得到最佳解
所以只能用一些不等式 像是markov inequation 或是 chernoff bound
來求得他必會小於某個用n表達的式子
--------------------------------
想跟大家聊聊這個問題
這道問題應該是大學以上程度
--
http://imgur.com/QTIXoZQ
取自萌娘百科-Niconiconi*20.gif( zh.moegirl.org/zh-tw/File:Niconiconi*20.gif )
http://imgur.com/WiJ9BQl
取自萌娘百科-妮可顏藝.jpg( zh.moegirl.org/zh-tw/File:妮可顏藝.jpg )
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.217.39
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1496383496.A.5CB.html