k-制限最小値独立置換族,その他k-wise独立性のサンプルサイズ下界

概要

論文の詳細を見る
集合{0,1,...,n-1}上の置換族Fがk-制限最小値独立であるとは,置換πをFからランダムにサンプルするとき,|X|≤kを満たす任意のX⊆{0,1,_,n-1}と任意のx∈Xに対して,Pr[min{π(X)}=π(x)]=1/|X|を満たすことをいう.本稿では,k-制限最小値独立置換族Fに対して|F|≥m(n-1,k-1)が成り立つことを示す.ただし,m(n,d)=Σ^<d/2>_<i=0>( ^n_i)(d:偶数);m(n,d)=Σ^<(d-i)/2>_i=0 ( ^n_i) + ( ^<n-1>_(d-1)/2)(d:奇数)・この下界は,F上の分布と無関係に成立する.これは,既知の事実-確率変数X_1,X_2,...,X.:Ω→{0,1}のどのd個も独立でかつPr[X_i=1]≠0,1であるとき,|Ω|≥m(n,d)-を一般化し,以下のように導出される.確率変数X_1,X_2,...,X_n:Ω→{0,1}が,任意のd個組みにおいて,確率変数Y_1,Y_2,...,Y_nと同一の分布に従い,さらにn個組み(Y_1,Y_2,...,Y_n)が2^n個の全ての値において正の確率を持つとき,|Ω|≥m(n,d)が成り立つ.k-制限最小値独立置換族Fから誘導される確率変数X_1,X_2,...,X_n:F→{0,1}に関して,このような確率変数Y_1,Y_2,...,Y_nの存在は明らかである.
社団法人電子情報通信学会の論文
2002-09-23