→ oNeChanPhile:我還以為是一般管院學生所適應的習題難度.... 09/19 05:14
→ oNeChanPhile:done(補了平行四邊形圖) 09/19 12:31
※ 編輯: oNeChanPhile 來自: 114.27.8.196 (10/21 17:05)
....這題真夠麻煩的！（對於非數學系的我來說 @@）
文長請耐心閱讀
※ 引述《ndc24075 (歡喜作，甘願受)》之銘言：
: 因為想了很久實在不知道從何下手,想請各位幫忙解答
「完全剩餘系」用很大....
這個一般(非數學系的)機率或統計課應該不會教吧
我是在高中玩數學競賽時恰巧學到的....
: 4.12
: Let K≧3 be a prime and let X and Y independent r.v that are uniformly distri-
: buted on {0,1...,K-1}. For 0≦n≦K, let Zn= X+nY mod K. Show that Zo, Z1,...,
我假設這裡是指 (X+nY) mod K。
: Z(K-1) are pairwise independent, i.e., each pair is independent, but if we
: know the values of two of the variables then we know the values of all the
: others.
lemma：
考慮 0≦n≦K-1 的整數n，排除 n=K（題目沒問），K為質數。
則 {nY mod K | Y=0,1,2,...K-1} 是 K 的完全剩餘系
亦即 {0, n*1 mod K, n*2 mod K, ...,n*(K-1) mod K} = {0,1,2,....,K-1}。
pf：
假設 n*i 與 n*j 除以 K 的餘數相同，則 n*i-n*j = n(i-j) ≡ 0 (mod K)
∵ K 為質數
∴ K 要嗎整除 n ，要嗎整除 (i-j) ，但是顯然都不可能
因為 n≦K-1，|i-j|≦(K-1)-0 = K-1，都不可能有質因數 K。矛盾！
故 n*i 與 n*j 除以 K 的餘數必兩兩不同。
對同一個n來說，nY 之值共有 K 個 (Y=0,1,...,K-1)，
但是 mod K 所有可能的取值也只有 K 個（即0,1,2,...,K-1）
所以 K 個 (nY mod K) 之值，必被不重複的分配至 {0,1,2,...,K-1}
＃
令 W_n = nY mod K。
因為 {W_n | Y=0,1,2,...K-1} 與 {Y | Y=0,1,2,....,K-1} 為一一對應
且已知 Y 為均勻分配
故 W_n 亦為取值在 {0,1,...,K-1} 的均勻分配
注意 Z_n 可以寫成 Z_n = (X + W_n) mod K。
將數對 (X, W_n) 可能的取值作圖如下
W_n = (0,1,...K-1), 均勻分配
↑
K-1 ┼．．．．．．．．
┼╲．．．．．．．
┼．╲．．．．．．
┼．．╲．．．．．
┼．．．╲．．．．
┼．．．．╲ 分界線：X+W_n = K-1
┼．．．．．╲．．
┼．．．．．．╲．
0 ┼┼┼┼┼┼┼┼┼─→ X = (0,1,...K-1), 均勻分配
0 K-1
把分界線 X+W_n = K-1 上方(不含線上)的那些點往下平移 K 單位，
拼成一個平行四邊形如下圖
（作用：X+W_n≧K的，將之減少K。也就是取 mod K）。
W_n = (0,1,...K-1), 均勻分配
↑
K-1 ┼
┼╲
┼．╲
┼．．╲
┼．．．╲
┼．．．．╲ W_n + X = K-1
┼．．．．．╲
┼．．．．．．╲
0 ┼┼┼┼┼┼┼┼┼─→ X = (0,1,...K-1), 均勻分配
0 ．．．．．．．．
．．．．．．．
．．．．．．
．．．．．
．．．．
．．．
．．
．
注意到
1.斜直線 X+W_n = A（0≦A≦K-1），無論A值，都會通過的平行四邊形上的 K 個點。
這 K 個點平移前的位置，
正是滿足 Z_n = (X+W_n) mod K = A 的 K 個解。由圖亦知 W_n 之值不會重複。
2.因為 X 與 W_n 皆為均勻分配，所以每個點 (X, W_n) 出現的機率均等。
又因 W_n 與 Y 為一一對應，
故每組滿足 Z_n = A 的解 (X,Y) 出現的機率亦均等，且Y值不重複。
故得到下列推論：
Cor.(1)：Z_n 的取值為 {0,1,...,K-1}，且機率為均勻分配。(by 1.)
Cor.(2)：對每個整數 0≦A≦K-1，皆有 K 組滿足 Z_n = A 的數對 (X,Y)，
且每組 (X,Y) 出現的機率均等。(by 2.)
所以繞了一大圈，Z_n (n=0,1,...,K-1) 其實就是均勻分配 by Cor.(1).
考慮 Z_n 與 Z_m， 0≦n＜m≦K-1，
則 Z_m = (Z_n + (m-n)Y) mod K
by Cor.(2)，對於任何 Z_n = A = const.，
構成 Z_n 的 Y 值的確可以取遍 {0,1,...K-1}，且每個 Y 值出現的機率均等。
又 by lemma， {(m-n)Y | Y=0,1,...K-1} 為 K 的完全剩餘系
故 by Cor.(2) and lemma,
{Z_m|Z_n=A} = {(A+r) mod K | r=0,1,...K-1} = {0,1,...K-1} ，
為完全剩餘系，且出現機率為均勻分配。
換言之，Z_m 的期望值與 Z_n 無關
直接計算可得
E(Z_m|Z_n) = [0+1+2+...+(K-1)]/K = (K-1)/2 = E(Z_m)
↑ ↑
均勻分配的完全剩餘系 也是均勻分配的完全剩餘系
故 Z_m, Z_n 兩兩獨立
qed
--
小的唸商之後成天只知唬爛，嚴謹的東西早就不行了，
太囉唆 or 語法奇怪請多包涵 有錯請告知 謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.18.217