[機統] 抽數字問題
如果我有x1, ..., xn這些隨機變數, 每個的範圍都是uniformly從1~m之間挑出來,
我想算Pr[x1≠x2≠...≠xn]這個機率,
另外, 還想算Pr[x1≠x2≠...≠xn≠x1+x2≠x2+x3≠...≠xn+x1]這個機率,
請問有人知道怎麼算嗎?
我自己的想法如下:
考慮n=4, m=10的簡單例子來說明,
先想Pr[x1≠x2≠x3≠x4]好了,
4個隨機變數有10^4=1000種挑法,
而要剛好都不一樣則有10*9*8*7=5040種挑法, 所以Pr[x1≠x2≠x3≠x4]=0.504
再想一下Pr[x1+x2≠x2+x3≠x3+x4≠x4+x1]這個機率,
因為這些變數都是uniformly分布在1~10,
所以兩個相加的結果應該是uniformly分布在2~20,
所以可以想成是4個uniformly分布在2~20的隨機變數互相不相同的機率,
而這就又跟上面的case一樣了, 所以我套用一樣的思路,
共有(20-2+1)^4=19^4=130321種挑法,
但是要剛好都不一樣則有19*18*17*16=93024種挑法,
所以Pr[x1+x2≠x2+x3≠x3+4≠x4+x1]=93024/130321=0.7138
總算要看Pr[x1≠x2≠x3≠x4≠x1+x2≠x2+x3≠x3+4≠x4+x1]這個機率了,
這個機率寫仔細一點應該寫成
Pr[x1≠x2, x1≠x3, x1≠x4, x1≠x1+x2, x1≠x2+x3, x1≠x3+x4, x1≠x4+x1,
x2≠x3, x2≠x4, x2≠x1+x2, x2≠x2+x3, x2≠x3+x4, x2≠x4+x1,
x3≠x4, x3≠x1+x2, x3≠x2+x3, x3≠x3+x4, x3≠x4+x1,
x4≠x1+x2, x4≠x2+x3, x4≠x3+x4, x4≠x4+x1,
x1+x2≠x2+x3, x1+x2≠x3+x4 x1+x2≠x4+x1,
x2+x3≠x3+x4 x2+x3≠x4+x1,
x3+x4≠x4+x1]
令event A定義成x1≠x2, x1≠x3, x1≠x4, x2≠x3, x2≠x4, x3≠x4同時發生,
也就是說event A其實就是x1≠x2≠x3≠x4,
而event B是所有其他剩下的那些東西,
Pr[x1≠x2≠x3≠x4≠x1+x2≠x2+x3≠x3+4≠x4+x1]=Pr[B|A]Pr[A],
而其中的Pr[A]我們已經算出來了,
Pr[B|A]經過化簡,
可以變成Pr[x1≠x2+x3, x1≠x3+x4, x2≠x3+x4, x2≠x4+x1,
x3≠x1+x2, x3≠x4+x1, x4≠x1+x2, x4≠x2+x3],
由於每個隨機變數都是independently and uniformly從1~100中挑出來的,
且裡面共有8個term,
所以我把它想成是(Pr[z≠x+y])^8,
其中x, y, z都是independently and uniformly從1~100中挑出來的隨機變數,
我這裡定義w=x+y, 所以w是均勻分布於2~200之間的隨機變數,
有了w, 則Pr[z≠x+y]=Pr[z≠w]=1-99/(100*199),
(因為共有99種組合是形成z=w, 但是共有100*199種可能的挑法)
所以(Pr[z≠x+y])^8=1-(99/(100*199))^8≒1, 也就是Pr[B|A]≒1,
所以, Pr[x1≠x2≠x3≠x4≠x1+x2≠x2+x3≠x3+4≠x4+x1]=Pr[B|A]Pr[A]≒Pr[A]=0.504
不知道我這樣的想法是對的嗎?
然後要怎麼推廣到general case呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.83.202
→
11/24 08:02, , 1F
11/24 08:02, 1F