2011-02-16

離散-著色多項式&機率

用聯集的方法 ,算出來為λ*(λ-1)*((λ-2)^3)

但覺得怪怪的
想請問著色多項式是唯一嗎?

因為自己對圖上λ
先對右上角上λ
最上面λ-1
左下角λ-1
其他兩點λ-2 , λ-2
結果為λ*((λ-1)^2)*((λ-2)^2)
是我哪邊搞錯了嗎


6. (10%) A pair of fair dice is continuously rolled until either a 1 or a G
appears at which point the experiment stops. What is the probability
that the experiment was stopped not because of 1's appearance?

結束的情形可能為 (1,x), (x,1),(6,x) (x,6) 其中x=1,2,3,4,5,6 總共有20種可能
其中去掉包含1的可能 (1.1) (1.2) (1.3) (1.4) (1.5) (1.6) (2.1) (3.1) (4.1) (5.1) (6.1)等11種
所以1不出現的情況下結束的機率為 9/20


7. (10%) Suppose P balls are distributed at uniformly random into N
boxes. Let Xi be a random variable defined by Xi = 1 if box i is
einpty and Xi = 0 otherwise. Compute E(Xi), the mean of Xi. What
is expectation of the number of einpty boxes after these P balls were
distributed.
請這題的機率要怎麼設呢?


請各位高手 與助教指點迷津




2 則留言:

線代離散助教(wynne) 提到...

1. (著色多項式) 因為上色的順序有誤導致算出來的著色多項式有問題, 在對最上面的點上色之後, 如果這時要先標左下的那個點, 你必須要分別考慮此點與最上方點著同色或不同色的情形, 這樣左上那個點才有辦法討論; 如果你將考慮的順序改成: 1.右上 2.最上, 3.左上, 4.左下, 5.右下, 這樣做出來就不會有問題了

所以算的時候要小心一點, 否則可能還是利用定理來分解會是比較保險一點的算法

6. 這樣算應該是沒什麼問題, 這題我個人是覺得不用太在意它, 因為題目的敘述有點不夠清楚, 常常造成大家對題目會有不同的解讀方式

7. 對 box i 而言, 每一次將球丟進該箱子的機率會是 1/n, 那麼在丟了 p 個球之後, 最終 box i 會是 empty 的機率為 ((n-1)/n)^p, 所以空箱的期望值為 ((n-1)/n)^p * 1 = (1-1/n)^p

Lulu Hung 提到...

我比較瞭解了
謝謝助教的答覆