Re: [理工] 102 台大電機丙 離散

[waterman815 ()]

※ 引述《skybee (斯蓋比)》之銘言：
: 想問一下第二題怎麼解
: In an election with two candidate A and B,if candidate A receives p vote
: and candidate B receives q votes with p>q,what is the probability
: that A will be strictly ahead of throughout the count?
: 題目是說 A總得票p B得票q 然後在開票過程中A的票都是比B多的
: 麻煩大家了


看了之前大大貼的連結
連結在此http://www.sec.ntnu.edu.tw/Monthly/91(246-255)/247/28Catalan.pdf
寫的滿清楚的，但還是有些小疑問
想要尋求解答ＱＱ

這篇內容主要是將投票問題想像成路徑問題
然後藉由路徑問題的限制 轉換成1-1 , onto的函數
來求解

例如從（0,0）走到（10,10）
y座標永遠不會比x座標大的方法數是

   c(20,10) - c(20,9)

想法可看連結有詳細說明
----------------------------------------------

回歸此投票問題
給定p>q
且q不能超過p的機率

我的想法也是利用連結的想法
將問題轉成
[  c(p+q,p) - c(p+q,q-1) ] /  c(p+q,p)

但是去翻了大Ｘ的詳解
答案是

[  c(p+q-1,p-1) - c(p+q-1,q-1) ] /  c(p+q,p)

發現差了一些
覺得應該是轉換問題時想錯
（似乎有用到平移）
 所以想來這邊問問
該怎麼思考這題才是正確的

謝謝各位大大！！！！！！！！！！！！
---------------------------------------------------------


感謝harryron9提醒
稍微補充一下搞錯的點

其實「p永遠大於q」 與 「p永遠不小於q」 兩個問題是不等價的
詳情可以看連結的p31頁 ， 早上沒有看清楚。

謝謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.120.6
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1421901286.A.2D7.html
→ harryron9: 題目問的是strictly ahead 一定大於
→ harryron9: 你給的講義做法是可以等於
→ harryron9: 換到此題就是 符合的情況 第一票必為A 後面分開來看
→ waterman815: ！！！！！！！！了解了！！！！！！！！感謝大大說
※ 編輯: waterman815 (140.119.120.6), 01/22/2015 19:25:06
推 winnie48: 不好意思想借問一個問題：在轉換過程中，以第一個違反處
→ winnie48: ，到底是將前面元素反轉，還是將後面反轉呢？謝謝！
→ waterman815: 我的理解是將後面的東西全部反轉～
推 winnie48: 那為什麼答案的第二項c(p+q-1, q-1)裡面,是q-1而不是q+1
→ winnie48: 呢？後面全反轉不是q會多1嗎？想了好久～!!
推 sfriend: 我也覺得是q+1欸 有人可以告訴我到底是-1還是+1嗎
→ sfriend: 阿應該是q-1沒錯