数理解析研究所講究録
第 1894 巻 2014 年 1-91

フーリエ変換による置換族の独立性解析
長岡技術科学大学

鈴木孝*

NGUYEN THAI PHAT\dagger

由智 \dager

武井

Takashi Suzuki, NGUYEN THAI PHAT, Yoshinori Takei
Nagaoka University of Technology

1

2.1

はじめに
最小値独立性は文書類似性判定アルゴリズムなどに応用をもつ置換族の確率的対称性の一種である．ま$n$置換と対称群$[n]:=\{1,2, \ldots,n-1,n\}$ と個の対象の集合を，すると， 個の対象の置換の集合は，$n$た，置換の確率分布の対称性度合いを表す尺度として$S_{n}:=\{\sigma:[n]arrow[n]|$ラベル依存度がフーリエ解析の応用により提案され
ている．

全単射

$\}$

で定義される． は，写像の結合を演算とした群であり， 次対称群と呼ばれる．
$\sigma(j)=i_{j}$ を満たのサイズは , $|S_{n}|=n!$ である．の要素 は，two line notation によりすような$S_{n}$

本論文は，最小値独立置換族，その強化である Robust 置換族，あるいは 対独立性置換族のもつ確率的対称性をフーリエ解析の観点より特徴づけることを試みる．まずラベル依存度の基本性質である逆元
$k$

$n$

$S_{n}$$S_{n}$$\sigma$

操作，共役操作に対する不変性を示す．次に 4 次の最小値独立置換族でサイズが 12 であるものを全数調査し，そのラベル依存度の分布を特定する．特にラベル依存度が となる置換族が 4 次交代群およびその補$O$$\sigma=[Matrix]$(1)のように表記される．置換を構成する巡回置換の長集合として得られることを示す．また，同一サイズの さの組を巡回置換型 (cycle-type), あるいは単に型
最小値独立性を有さない置換族と比較して，最小値独 (type) と呼ぶ．
立置換族は平均的に小さいラベル依存度を持つこと後のため，$\sigma\in S_{n}$に対する別の表記法を導入する．

を示す．その他， 対独立性 ( -wise independence)
$k$

$k$

および Robust 性がそれぞれ Young 直交表現に基づ$\sigma^{-1}=[Matrix]$

くフーリエ係数の特定 (‘周波数” における値が 0 になることとして特徴づけられることを示す (定理 5,6).

であるとする$2,$2

準備
ここでは，対称群の表現と，対称群上の関数のフーリエ変換についての既知の事柄を述べる [2,3,7,8,9].

$\ldots,$と書く．この記法を

第 1 著者に同じ，dhphat@act-w.nagaokaut.ac.jp\ddagger 長岡技術科学大学電気系，takei@act-w.nagaokaut.ac.jp$\dagger$$\sigma$の逆像文字列表記と呼ぶ．

置換族，対称群上の関数の部分集合を置換族と呼ぶ．置換族が与えられると，その特性関数

対称群

長岡技術科学大学大学院工学研究科電気電子情報工学専攻，$\sigma$$\sigma=\langle a_{1},a_{2}, \ldots,a_{n}\rangle$$S_{n}$

tsuzuki@act-w.nagaokaut.ac jpが満たされるとする．このような

を

2.2

$*$

$\sigma(a_{1})=1,\sigma(a_{2})=$すなわち，$\sigma(a_{n})=n$$S_{n}$$F(\pi)=[Matrix]$$F\subseteq$

(2)

2

集合であるとする．このことをば，これは
図 $1:1,2,3,4,5$ を 5,1,2,3,4 とラベルを貼り替えた時の例
あるいは $F$ からの一様 ランダムな抽出に対する分布関数$\lambda\vdash n$$t^{\sim}t’$と書いたとすれに対する tablaux 間の同値関係となる．その同値類を$\{t\}=\{t’\}$と書いて tabloid であるという．ある tabloid を代表する tablaux として，各行が昇順にソートされた (右に行くにつれて要$f(\pi)=\{\begin{array}{l}素が増加する) (3)tablauxを取ることができる．また，\Pi^{1}F (\pi\in F)\end{array}$あるtabloidを図示するとき，列方向の並び順は重要$(\pi\not\in F)$$0$でないことを示すために列の要素間の区切りを省略来る．このことから，置換族は する．例えば，と同一視することが出
後述のフーリエ解析の 対象になり得る．

$t= \frac{12}{\overline{\fbox_{3}}}$に対して$\{t\}=\{F_{3}^{12}F_{3}^{21}\}=\overline{\frac{12}{\underline{3}}}$2.3

共役とラベルの貼り替え

対象 1,2,3,4,5 にそれぞれ 5,1,2,3,4 というラベルを貼る．すると置換の集合$\{\sigma_{1}, \sigma_{2}\}=\{(\begin{array}{lllll}1 2 3 4 52 3 1 5 4\end{array})$のようになる．また，$\overline{\frac{123}{\underline{4}}}=\overline{\frac{231}{\underline{4}}}$$(\begin{array}{lllll}l 2 3 4 52 1 3 5 4\end{array})\}$

は $\lambda=(3,1)\vdash 4$ に対する同一の tabloid の 2 通り
はの表示である．さらに，各数が一つの箱に必ず一回きり現れ，各行と列について数が昇順に並んでいるも$\{\pi_{1}, \pi_{2}\}=$$\{(\begin{array}{lllll}l 2 3 4 52 5 4 3 l\end{array})$$(\begin{array}{lllll}l 2 3 4 55 2 4 3 l\end{array})\}^{の\epsilon\dagger g^{i}\not\subset T^{r}\sqrt[\backslash ]{}ク^{}\backslash \mathfrak{B}Xlfstandardtab1aux と|\Psi\lambda.\check{\circ}}nlf,tab1auxt$と$\sigma\in S_{n}l_{\overline{L}}\hslash\backslash bTtab1aux\sigma(t)h^{\backslash }\backslash$のように見える．その様子を図 1 に示す．ここで， を 内の各数に作用させることで自然に得られる．
$\sigma$tabloids$i=1,2$ に対し，$\pi_{i}=\tau\sigma_{i}\tau^{-1},$ $\tau=(\begin{array}{lllll}1 2 3 4 55 1 2 3 4\end{array})$$\pi,$$\sigma\in S_{n}$

$t$

に対し，

$\exists_{\tau,\pi=\tau\sigma\tau^{-1}}$

のとき

.

2.5
と

に対する

$\sigma(\{t\})$

群の表現
$G$

$\sigma$$f(\sigma)=f(\tau\sigma\tau^{-1})$$\sigma$についても同様である．

は一般に群 の表現は $G$ からが成り立 の準同型写像すなわち，と互いに共役$\pi$

共役と呼び，つ関数を類関数と呼ぶ．また，ある元
な元を全て集めた集合を， の共役類と呼ぶ．
$\forall_{\tau,\sigma}\in S_{n},$$\{t\}$$d_{\rho}$次複素正則行列へ$\rho:Garrow \mathbb{C}^{d_{\rho}\cross d_{\rho}}$

であって，$\rho(xy)=\rho(x)\rho(y) , \forall_{x,y\in G}$(4)$p(x^{-1})=(\rho(x))^{-1}, \forall_{X\in G}$(5)$\sigma$

2.4$\lambda$$\lambda_{k},$tablaux
tablaux$=$&tabloid,$d_{\rho}$は表現の次数と呼ばれる．以下では行列であるような表現のみを考える．表現 に対して，$\rho(x)$,の分割と呼び$(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{k})$$\sum_{i=1}^{k}\lambda_{i}=n$standard を満たすものを言う．とくに $\rho(e)=I$ が成立する．

を $n$$\lambda_{1}$$\geq$$\lambda_{2}$$\geq$...

$\rho$$\geq$$d_{\rho}\cross d_{\rho}$$\lambda\vdash n$

と書

がユニタリ

$\langle.$

行列

$Q$

と．表現

$\rho_{i}=Garrow \mathbb{C}^{d_{\rho}}:^{xd_{\rho}}\cdot(i=1,2)$

3
が存在して

定義
$\forall_{g}\in G,\rho(g)=Q\{\begin{array}{ll}\rho_{1}(g) 00 \rho_{2}(g)\end{array}\}Q^{-1}$となるとき，と書き， は と の直和に分解されると言う． がより次数の低い表現の直$\rho^{\cong}\rho_{1}\oplus\rho_{2}$$\rho$$\rho_{1}$

$=$

$\mu$

’

$=(\mu_{1}, \mu_{2}, ., \mu_{m}),\mu,$$\rho_{2}$$\mu_{1}+\mu_{2}+\ldots+\mu_{i}\geq\lambda_{1}+\lambda_{2}+\ldots+\lambda_{i},$$\forall_{i\geq 1}$$\rho$

和に分解出来る時

は可約表現と呼ばれ，逆に分解 ただし，$i>m$ に対する， は と考える．$i>l$ にと書対する義も同様である．が成り立つ時，は一つ以上の既約表現の直和に分解する．き， は を支配すると言う．口できない時$\rho$$0$$\rho$$\mu_{i}$は既約表現と呼ばれる．一般に，表現$\mu\underline{\triangleright}\lambda$$\lambda$$\mu$

定理 1. [9] 各

2.6

Young 直交表現 $[2]$と tabloids 上の表現

対称群の場合，群の既約表現として Young 直交表$\lambda\vdash n$$\tau_{\lambda}$

Young 直交表現

に対し，正則行列$\rho_{\lambda}$$C_{\lambda}$が存在$\forall_{\sigma\in S_{n})}$

(10)

して，

は整数の分割が用いられる．YOR
に対する標準ヤング盤の数
よりラベル付けされる．

現 (YOR)に対する$\lambda\vdash n$に$C_{\lambda}^{-1} \tau_{\lambda}(\sigma)C_{\lambda}=\bigoplus_{\mu\underline{\triangleright}\lambda}\bigoplus_{l=1}^{K_{\lambda,\mu}}\rho_{\mu}(\sigma)$$\lambda$を$d_{\lambda}$とするとき YOR は既約表現と書かれる．行列ヤング盤:$\rho_{\lambda}$$[\rho_{\lambda}(k, k+1)]^{d_{\lambda}\cross d_{\lambda}}$$S_{n}arrow \mathbb{R}^{d_{\lambda}\cross d_{\lambda}}$となる．

$K_{\lambda,\mu}$は Kostka numberの要素は標準はでインデックスされ，隣接互換 $(k, k+1)$ すなわち，$\tau_{\lambda}$$t$$\mu\underline{\triangleright}\lambda$

なる

$\mu$

と呼ばれる．
$\square$に関する Young 直交表

現の (重複を含む) 直和に分解する．

に対し，$[\rho_{\lambda}((k, k+1))]_{t,t}=1/d_{t}(k, k+1)$

.

(6)

2.7

$(k, k+1)(t)$ も標準ヤング盤の場合，(6) に加また，対称群上のフーリエ解析$f,$ $g:S_{n}arrow \mathbb{R}$

えて非対角要素

に対し，これらの内積を(11)$\langle f|g\rangle=(n!)^{-1}\sum_{\sigma\in S_{n}}f(\sigma)g(\sigma)$$[\rho_{\lambda}((k, k+1))]_{t,(k,k+1)(t)}=\sqrt{1-1/d_{t}(k,k+1)^{2}}$(7)があらわれる．他のすべての行列要素はゼロである． で定義する．
の $(i, j)$ 成分と
ここで $d_{t}(i,j)=c(j)-c(i),$ $c(x)$ はの content と$\rho_{\lambda}$$\rho_{\lambda’}$$x$の $(k, l)$ 成分は$\lambda=\lambda’$

かつか呼ばれる量であり，ヤング盤の中に置かれた の列 $(i, j)=(k, l)$ の時を除き直交する．また，つ $(i, j)=(k, l)$ の時はとなる．すなわち，
インデックスと行インデックスの差で定義される．
すべての置換は隣接互換の積で表されることから，(12)
式 (6),(7) によって亀の表現が定義できる．こ$\lambda=\lambda’$$x$$1/d_{\lambda}$$\langle\rho_{\lambda,(i,j)}|\rho_{\lambda’,(k,l)}\rangle=\delta_{\lambda\lambda’}\delta_{ik}\delta_{jl}\frac{1}{d_{\lambda}}$$\forall_{\sigma\in}$

れにより定義された$\rho_{\lambda}(\sigma)$

は，が成立する． 上の関数
$S_{n}$( )$\rho_{\lambda}(\sigma)^{-1}=\rho_{\lambda}(\sigma)^{T}$を満たす．すなわち，$\rho_{\lambda}(\sigma)$$S$$f:S_{n}arrow \mathbb{R}$の Young 直交

表現に基づくフーリエ変換はは直交行列である．

$\hat{f}_{\rho_{\lambda}}=\sum_{\sigma\in S_{n}}f(\sigma)\rho_{\lambda}(\sigma), \lambda\vdash n$(13)とは別の自然な表現を考える．
また，ここでこの各に対して， 上の tabloids を基底とする線 で定義される．さらに，$\rho_{\lambda}$$\lambda\vdash n$$\lambda$形空間上の表現$\tau_{\lambda}$が$\chi_{\lambda}(\sigma)=$(9)$[\tau_{\lambda}(\sigma)]_{ij}=\{\begin{array}{l}1 \sigma(\{t_{j}\})=\{t_{i}\}0 otherwise\end{array}$を$\lambda$(14)$(\rho_{\lambda}(\sigma))$における指標と定義する．以下が成立する :$(n!)^{-1}$で定義される．この行列は， に対する各 tabloids

trace

trace

$(f(\lambda))=\langle f|$

trace$(\rho_{\lambda})\rangle$

,

(15)

$\lambda$$\{t_{i}\}$で添字付けられており，$\sigma(\{t_{j}\})=\{t_{i}\}$とは$\forall\tau, \sigma\chi_{\lambda}(\tau\sigma\tau^{-1})=\chi_{\lambda}(\sigma)$

.

(16)

$\{t_{j}\}$の各行を構成する集合を で写した像がの対 つまり指標は，共役ラベルの貼り替えで不変であ応行を構成する集合に一致することを表わす．
はで共役不変な関:る．さらに，と2 種類の表現は次のように結びっけられる． 数 (類関数) の空間の正規直交基底になっている．
$\sigma$$\{t_{i}\}$$=$$\{\chi_{\lambda}\}_{\lambda\vdash n}$$\rho_{\lambda}$$\tau_{\lambda}$$f$$S_{n}arrow \mathbb{R}$4
また，式 (10) より， を Young 直交表現
場で用いて，式 (13) と同様の Fourier 変換を$\rho_{\lambda}$$\tau_{\lambda}$

の立

(17)

$\hat{f}_{\tau_{\lambda}}=\sum_{\sigma\in S_{n}}f(\sigma)\tau_{\lambda}(\sigma)$

すなわち， は畳み込み $f*g$ となる．一般について，そのフーリエ変換は簡明な性質をもつ，つま$h$$f*g\}_{\overline{\llcorner}}$

り，畳み込み定理(20)$\overline{f*g}=\hat{f}\cdot\hat{g}$と同様に tabloids で添字で定義する．これは，が成立する．
成分は式 (9) から付けられた行列であり，$\tau_{\lambda}(\sigma)$$\{t\},$ $\{t’\}$$[\hat{f}_{\tau_{\lambda}}]_{\{t\},\{t’\}}=P_{\Gamma}[\sigma(\{t’\})=\{t\}]\sigma\in {}_{f}S_{n}$(18)2.9 最小値独立置換族 (MWIPF) [1]をランダムに抽集合間の類似度を復元できるハッシュ値の構成法にが最小値独立置
出することを表す) であることに注意する．関連して Broder ら [1] により換族 (Min-Wise Independent Parmutation Family,
例 1. Diaconis $[2, Chap. 3D],$ Huang $et al. [9].)$MWIPF) であることが，次の通り定義されている．
2-wise(Pair-wise) の場合，分割 $\lambda=(n-2,1,1)$ に$x_{2}\in[n]$ に対が最小値独立であることは次が成
定義 2.
対する tabloid は互いに異なるは分布 $Pr[\sigma]=f(\sigma)$ で$(\sigma\in fS_{n}$$\sigma$$F\subseteq S_{n}$$($$F\subseteq S_{n}$$x_{1},$

立することをいう．

$[n]\backslash \{x_{1}, x_{2}\}$

する $\{t’\}=$の形となる．同様に，$\underline{x_{1}}$$\forall X\neq\emptyset\subseteq[n], x\in X,Pr[\min\pi(X)\pi\in F=\pi(x)]=|X|^{-1}$$\frac{\underline{x_{2}}}{[n]\backslash \{y_{1},y_{2}\}}$$(21)\square$$\{t\}=$とおくと，式 (18) から，$\underline{y_{1}}$

これについては次の特徴付けが与えられている [1,5,$\ovalbox{\tt\small REJECT}$

6

$].$

定理 2.

$[\hat{f}_{\tau_{\lambda}}]_{\{t\}},\{t’\}_{\sigma}=Pr[\sigma(\{t’\})=\{t\}]$$F\subseteq S_{n}$が最小値独立であることと，次は同値である;$= Pr_{S_{n}}[\bigwedge_{i=1}^{2}\sigma(x_{i})=y_{i}]\sigma\in J$$\forall_{k}(0\leq k<n), X\in(\begin{array}{l}[n]k\end{array}),x\in[n]\backslash X$となり，順序対$(x_{1}, x_{2})$が $(y_{1}, y_{2})$ に写像される確率を表す．

$[Pr[\pi(X)=\{1,2, \ldots, k\}\wedge\pi(x)=k+1]$

2.8

畳み込み

関数 $f,$$g$:$= \frac{1}{(n-k)(\begin{array}{l}nk\end{array})}]$$S_{n}arrow \mathbb{R}$はそれぞれランダム置換$\sigma,$.

(22)$\tau$

口の分布とする．つまり $f(\sigma)=Pr[\sigma],$ $g(\tau)=Pr[\tau]$ とこの特徴づけを利用した最小値独立置換族の一般
する．2 つのランダム置換が独立であるとき，2つの合成( が先， が後に作用する) がいか 的構成法が [5] で与えられ，それにより特に $n=4$ の$h(\pi)=Pr[\pi|$ とおときサイズが lcm(4,3,2,1) $=12$ を達成する最小値なる確率分布に従うかを考える．
$\sigma,$$\pi=\sigma\tau$$\tau$

くとき，$[AJ$ で事象$\tau$$\sigma$$A$のインジケータ変数 $(A$ が真の独立置換族は全部で 64 個存在することがわかる．

とき 1, 偽のとき ) で表せば
$O$$h(\pi)$

2.10$=$$\sum_{\sigma,\tau\in S_{n}}f(\sigma)g(\tau)[\pi=\sigma\tau I$

最小値独立性より更に強い置換族の確率的対称性として，次の Robustness が定義されている [6].

$= \sum_{\mathcal{T}\in s_{n}}f(\pi\tau^{-1})g(\tau)$$= f*g(\pi)$ .

Robust Permutation Family

(19)

5
定義 3.

$F\subseteq S_{n}$が Robust であるとは，次が成立することを言う;$\forall\sigma\in S_{n},$および，第 2.3 節のラベルの貼り替えに対する関数の安定性の尺度としてラベル依存度 $LD$ が，$x\in X$

$X\subseteq[n](X\neq\emptyset),$$LD(f);=\frac{\langle f-P(f)|f-P(f)\rangle}{\langle f1f\rangle}$$\pi\in FPr[\min\sigma\circ\pi(X)=\sigma\circ\pi(x)]=\frac{1}{|X|}.$(23)$\square$$=1- \frac{\langle P(f)|P(f)\rangle}{\langle f1f\rangle}$

すなわち，任意の$[n]$の全順序に関して $F$ が最小

値独立であるとき， は Robust であると呼ばれる．
$F$

この Robustness についても，定理 2 と類似の特徴付けが与えられている;
定理 3. [6]同値である;$F\subseteq S_{n}$$f$が Robust であることと，次は(27)として定義されている．ラベル依存度は $0\leq LD(f)\leq$
1 の範囲で値をとる．特に がラベルの貼り替えで$f$こ
値が不変であることと

3

$LD$

$(f)=0$ は同値である．

ラベル依存度を変化ざせない関数操作$\forall k(0\leq k<n),$ $X,$

$Y\in(\begin{array}{l}[n]k\end{array}),$関数$f:S_{n}arrow \mathbb{R}$に対し，$\overline{f},$$f^{\tau}$を$x\in[n]\backslash X, y\in[n]\backslash Y$

,

(28)

$f^{\tau}(\sigma)=f(\tau^{-1}\sigma\tau)(\tau\in S_{n})$(29)$\overline{f}(\sigma)=f(\sigma^{-1})$$[ Pr[\pi(X)=Y\wedge\pi(x)=y]=\frac{1}{(n-k)(_{k}^{n})}]$

.

(24)
口

として定義する．すると，これらの操作$f^{\tau})$-wise Independent Permutation Family

2.11

$k$

換族の確率的対称性として$f\mapsto$

はラベル依存度を変えないことが示せる．

命題 4.
$LD$

最小値独立性や Robustness の他，よく知られた置$k$$(f\mapsto\overline{f},$$(f)=$ $LD$$(\overline{f})$$LD$ $(f^{\tau})=$ $LD$ $(f)$

,

(30)

(31)

対独立性がある．
口

定義 4.

上の確率分布

$S_{n}$

wise independent であるとは$[n],$ $x_{i}\neq Xj$$y_{j}$

for

for$i\neq j$$i\neq j$

)

$f$

:

$S_{n}$$arrow$$\mathbb{R}$が k-$\forall(x_{1}, x_{2}, \ldots, x_{k})(x_{i}\in$$\forall(y_{1}, y_{2}, \ldots, y_{k})(y_{i}\in[n],$ $y_{i}\neq$

4

小ざい $n(n=4,5)$ における最小)$\sigma\in {}_{f}S_{n}Pr[\bigwedge_{i=1}^{k}\sigma(x_{i})=y_{i}]=\frac{(n-k)!}{n!}$サイズの最小値独立置換族のラベル依存度調査(25)

4.1を満すことを言う．ただし，$\sigma\in f$

に従って$\sigma\in S_{n}$は，確率分布$f$のラベル依存度分布

がランダムに抽出されることを表す

口

4 次の最小サイズの最小値独立置換族$S_{4}$(4 次対称群) の部分集合で，最小サイズ $|F|=$$lcm(4,3,2,1)=12$ の最小値独立置換族は全 $2^{6}=64$

2.12通り存在する．この全 64 通りのラベル依存度抽出を

ラベル依存度 [4]$f$ :
文献 [4] で，$S_{n}arrow \mathbb{R}$行う．また，その結果から，最小値独立置換族が持つに対し， の共役不変成分 性質について考察する．
$f$$(P(f))( \sigma)=\sum_{\lambda\vdash n}\langle f|\chi_{\lambda}\rangle\chi_{\lambda}(\sigma)$

(26)

6
表 1: $n=4$ の最小値独立置換族のラベル依存度分布

表 2: $n=4$ の最小値独立置換族と重複元のないサイズ 12 の置
換族のラベル依存度平均と分散比較の分布を拡大した図を右上に示す．この図を見て分かる通り，ラベル依存度が小さい置換族は，非常に少ない特別な存在であることが分かる．
サイズ 12 の最小値独立置換族の $LD$ の中で最頻である $LD=0.375$ 以下の $LD$ を持つ置換族の比率は，サイ

ズ 12 の最小値独立置換族の場合，$40/64=0.625$ , で，$546616/{}_{24}C_{12}=$
サイズ 12 の一般の置換族の場合は，

図 2: $n=4$ の最小値独立置換族のラベル依存度分布

4.1.1$n=4$ のとき，最もサイズの小さい $lcm(4,3,2,1)=$示す．

特に $LD(F)=0$ である $F$ が 2 個存在するが，その 1 つは偶置換の集合$A_{4}$

, 他方は

であった．

$S_{4}\backslash A_{4}$の正規部分群で，$LD(A_{4})=0$ であり，このことにより成立するため，は$\forall\tau\in S_{4},$$S_{4}$$LD(S_{4}\backslash A_{4})=0$$\tau A_{4}\tau^{-1}=A_{4}$

が

も出る．

$n\geq 4$ に対する交代群
また [6] により，5 次の最小値独立置換族のラベル依存

43

度調査

は最小

5 に対するサイズが最小値 $(|F|$

$=$

$n$

$=$

$lcm(5,4,3,2,1)=60)$ の最小値独立置換族について個存在すると調査した．このような $F$ はおよそ
$7^{20}$

見積もられ，全数探索は難しいため，6$\cdot$$10^{4}$個の $F$ をランダムに抽出して $LD(F)$ を計算した．
その結果の平均は，0.50, 最大は 0.62, 分散は 6.5$10^{-4}$$A_{n}$

値独立置換族であることが証明されている．

4.2

ベル依存度は同じサイズの置換族の中で小さい側に偏っているといえる．

結果

12 の最小値独立置換族は文献 [5] により全 64 通り存在することが知られている．その 64 通りそれぞれに対してラベル依存度を計算した．その結果を表 1 に$A_{4}$

0.202 となった．この事実も，最小値独立置換族のラであった．なお，標本にはかからなかったものの，5 次の最小サイズの最小値独立置換族の $LD(F)$$F=A_{5}$ とその補集合が $LD(F)=0$ をの最小値は，

達成する．同じサイズの必ずしも最小値独立でない
4 次の重複元の無いサイズ 12 の全置 置換族の 103 個のランダム標本 $LD$ の平均は 0.64, 分

換族とのラベル依存度の比較において，重複元のないサイズ 12 の置換族全個の平均と分散，最小値独立置換族

散は 1. $2\cdot 10^{-3}$ であるから，最小値独立置換族はその対称性により，小さい $LD$ を持つと考えられる．

$n=5$ に対して，サイズが $lcm(5,4,3,2,1)=$
なお，$LD(F)=0$ を満たす最小値独立置換族
であり，全 64 個の平均と分散を表 (3) に示す．この結果より， は，だけであることがわかる．また，$n=6$
ラベル依存度の観点からは，最小値独立置換族は同サ に対する最小値独立置換族の最も小さいサイズは，
イズの重複元を持たない置換族よりも高い対称性を $lcm(6,5,4, \ldots, 1)$ $=60$ だが，このサイズの置換族持っていることがわかる．
$LD(F)=0$ を達
で重複元を含まないものは，の共役類のサイズの考察から
また，重複元のないサイズ 12 の置換族全 $2412$
成できないことが，$S_{4}$${}_{24}C_{12}=2704156$$60$$A_{5},$$A_{5}^{c}$$F\subseteq S_{6}$$S_{6}$

2704156 個の分布を図 3 と図 3 の $LD=0.28125$ 以下

わかる．

7

図 3: $n=4$ の最小値独立置換族と重複元のないサイズ 12 の置換族のラベル依存度分布 (右上の図は $LD=0.28125$ 以
下の拡大)

表 $3:n=5$ の最小値独立置換族とランダムにサンプリングした
重複元のないサイズ 60 の置換族のラベル依存度平均と分散比較とは同値である．

定理 6.

を $F$ から, に対し， :$F$ がの一様ランダム抽出を表す分布関数とする．
$F\subseteq S_{n}$$f$$S_{n}arrow \mathbb{R}$

Robust Permutation Family であることと，各$\mu\neq(n)$ に対する bung 直交表$\mu\underline{\triangleright}$$( r\frac{n-1}{2}\rceil, \lfloor\frac{n-1}{2}\rfloor, 1),$

現に基づくフーリエ係数行列ん

が

$0$

$\mu$

であることは同値である．

これらの定理の証明はほぼ同じようにでき，ここで5

確率的独立性のフーリエ係数による特徴付け-wise 独立性および Robust 独立性の定義 3, 4 を
例 1 にあるような tabloid 相互の写り合い確率でとらえることで，Young 直交表現に基づくフーリエ解
析の言葉で特徴づけられることを示す．

は定理 6 に対する証明を示す．

5.1

Robust Family と Young 直交表現$k$

以下，Robustness が $\lambda=(n-k-1, k, 1)$ に対する$\hat{f}_{\tau_{\lambda}}$の言葉で自然に特徴付けられることを示す．

に基づくフー
さらに，Young 直交表現
は (自明な表現 $\mu=(n)$ に対するもの
リエ係数
を分布関数とするとき， を除き) 消えることを示す．
$(\mu\underline{\triangleright}\lambda)$$\rho_{\lambda}$$\hat{f}_{\rho_{\mu}}$

定理 5.

:
が $k,wise$ independent であることと，各$-$$(1$$\mu\neq(n)$
は
個
に対する
,1
,
Young 直 証明．定理 2 より，$f$$S_{n}arrow \mathbb{R}$$f$$\mu\underline{\triangleright}(n$$k,$ $1,$$\ldots$$)$$k$$F\subseteq S_{n}$$)$交表現に基づくフーリエ係数行列$\hat{f}_{\rho_{\mu}}$

が

$0$

であるこ

が Robust になることは，

8$1\leq k<n$ に対して，$\forall_{X},$が成立する．ここで$=$$\hat{f}_{\tau_{\lambda}}$$\pi\in FPr[\pi(X)=Y\wedge\pi(x)=y]=\frac{1}{(n-k)(\begin{array}{l}nk\end{array})}$となることであるが，$X$ と$\{y\}$と置くと，$y\in[n]\backslash Y$$x\in[n]\backslash X,$$Y\subseteq(\begin{array}{l}[n]k\end{array}),$$\hat{f}’=\{\begin{array}{lll}\bigoplus_{\mu\underline{\triangleright}\lambda} K_{\lambda\mu,\oplus} \hat{f}_{\rho_{\mu}}\mu\neq(n) l=1 \end{array}\}$$[n]\backslash X\backslash \{x\},$

$Y$

と

(32)

$\sum_{\sigma\in S_{n}}f(\sigma)\tau_{\lambda}(\sigma)$$[n]\backslash Y\backslash$の立場を交換することにより，$1 \leq k<\lfloor\frac{n-1}{2}\rfloor$$=$$C^{-1}( \Sigma_{\sigma\in S_{n}}f(\sigma)[0\mu\neq n)\nu_{\frac{\bigoplus_{\triangleright}}{\langle}\lambda}\bigoplus_{l=1}\rho_{\mu}(\sigma)0\lambda_{\mu}])C$に対して式 (32) が成立することが必要十分であること

.

(35)

$= C^{-1}(\{\begin{array}{lll}\hat{f}_{\rho} n 00 \hat{f}’\end{array}\})C$$\lambda=(n-k-1, k, 1)$ に対すに注意する．このとき，る 2 つの tabloids $\{t_{X,x}\},$ $\{t_{Y,y}\}$ を

ここで $f$ は確率分布であるから$\overline{[n]\backslash X\backslash \{x\}} \overline{[n]\backslash Y\backslash \{y\}}$(36)$\hat{f}_{\rho_{(n)}}=\sum_{\sigma\in S_{n}}f(\sigma)\cdot 1=1$$\{t_{Y,y}\}=Y$$\{t_{X,x}\}=X$$\underline{x} \underline{y}$とおけば，各$\sigma\in S_{n}$である． の全成分力’であるとき，その$\hat{f}_{\tau_{\lambda}}$$\frac{1}{(n-k)(_{k}^{n})}$Rank は 1 となるため，に対して$[\tau_{\lambda}(\sigma)]_{\{t_{Y,y}\},\{t_{X,x}\}}$$C\hat{f}_{\tau_{\lambda}}C^{-1}=([+_{0\hat{f}’}^{10}])$$=\{\begin{array}{l}1 (\sigma(X)=Y\wedge\sigma(x)=y)0 (otherwise)\end{array}$(33)

も 1 である．そのためには，」 と他はない．よって，各の Rank$\hat{f}’=0$$k(1 \leq k\leq L\frac{n-1}{2}$が成立する．置換$\pi$を$F\subseteq S_{n}$から一様分布に従って抽出する確率分布を$k-1,$$k,$ $1),$$\mu\neq(n)$に対して，$\hat{f}_{\rho_{\mu}}$

る．

$1 \leq k’\leq k\leq L\frac{n-1}{2}$

」に対して

$)$

となる

$\mu\underline{\triangleright}(n-$はゼロ行列であ$(n-k’-1, k’, 1)\underline{\triangleright}$$(n-k-1, k, 1)$ であるから，$f(\pi)=\{\begin{array}{l}\Pi^{1}F (\pi\in F)0 (\pi\not\in F)\end{array}$$( \exists_{k}(1\leq k\leq L\frac{n-1}{2}\rfloor)\mu\underline{\triangleright}(n-k-1, k, 1))$とすれば，$\Leftrightarrow\mu\underline{\triangleright}(n-L\frac{n-1}{2}\rfloor-1, \lfloor\frac{n-1}{2}\rfloor, 1)$$[ \hat{f}_{\tau_{\lambda}}]_{\{t_{Y,y}\},\{t_{X,x}\}}=\sum_{\sigma\in S_{n}}f(\sigma)[\tau_{\lambda}(\sigma)]_{\{t_{Y,y}\},\{t_{X,x}\}}$$=( \lceil\frac{n-1}{2}\rceil, \lfloor\frac{n-1}{2}\rfloor, 1)$$=Pr[\pi(X)=Y\Lambda\pi(x)=y]\pi\in F$

(37)

(34)

であるので，

が成立する．従って，$F\subseteq S_{n}$が Robust であれば，各$\lambda=(n-k-1, k, 1)$ に対して

値$\frac{1}{(n-k)(\begin{array}{l}nk\end{array})}$次に$\hat{f}_{\rho_{\lambda}}$$\hat{f}_{\tau_{\lambda}}$の全成分は一つのとなる．

$F\subseteq S_{n}$for: Robust$\Rightarrow\hat{f}_{\rho_{\mu}}=0$$\mu\underline{\triangleright}(n-L\frac{n-1}{2}\rfloor-1, \lfloor\frac{n-1}{2}\rfloor, 1),$$\mu\neq(n)$を計算する．定理 1 の$\tau_{\lambda}=C^{-1}[\bigoplus_{\mu\underline{\triangleright}\lambda}\bigoplus_{l=1}^{K_{\lambda\mu}}\rho_{\mu}]C$(38)と簡単に表される．そして逆にれば，各 $\lambda=(n-k-1, k, 1),$
対してより，$\hat{f}_{\tau_{\lambda}}=C^{-1}[\bigoplus_{\mu\underline{\triangleright}\lambda}\bigoplus_{l=1}^{K_{\lambda\mu}}\hat{f}_{\rho_{\mu}}]C$$\hat{f}_{\tau_{\lambda}}$の全成分が$\frac{1}{(n-k)(_{k}^{n})}$$\Rightarrow$の右辺が成立す」 には Robust$(1 \leq k\leq L\frac{n-1}{2}$

となり，
$f$

$)$

Family からの一様ランダム抽出を表す．
$\square$5.2

最小値独立置換族と Young 直交表現

$F\subseteq S_{n}$が最小値独立であることを Young 直交表

現で特徴付けることは，前節ほど単純ではない．ただ

9
$F$
し，
が最小値独立であるとき，定理 2 の式 (22) を各について足し合わせることで， か$F$$X\in(^{[n]\backslash _{k}\{x\}})$

らの一様ランダム抽出は 1-wise independent である$F$ことが従うため，が最小値独立であれば，定理 5 によって，対応する分布関数 は$f$$\hat{f}_{\rho_{\mu}}=0$

for $\mu=(n-1,1)$(39)

本稿では，最小値独立性，Robust 性，対独立性といった置換族の確率的独立性を Young 直交表現に基$k$

づくフーリエ変換の言葉で解析した．

まず，ラベル依存度の基本性質 (逆元操作不変性，ラベル貼り替え不変性) を示した後，最小サイズ lcm $(n, n-1, \ldots, 1)$ を持つ最小値独立置換族を$n=4,5$ の場合について調査した．4 次の最小値独立置換族でサイズが $lcm(4,3,2,1)=12$ であるものを全数調査し，そのラベル依存度の分布を特定し，特にラベル依存度がとなる置換族が 4 次交代群およびその補集合として得られることを示した．また，同一サイズの最小値独立性を有さない置換族と比較して，最小値独立置換族は平均的に小さいラベル依存度を持つことを示した．さらに，4 次の最小値独立置換族
に対し，ある種の重ね合わせ操作を行った場合ラベル依存度が減少することを全数調査により示した．5 次の最小サイズ $(lcm(5,4,3,2,1)=60)$ の $LD=0$ とな

る最小値独立置換族は$A_{5}$とその補集合$A_{5}^{c}$が満たすことを示した．

次に，Robust 性，対独立性といった置換族の確率的独立性を Young 直交表現に基づくフーリエ係数の一部がゼロ行列となること (即ち，“帯域制限されて$k$いること”) として特徴づけた．

7

謝辞
本稿について議論頂いた和田州平氏に感謝いたし

ます．

参考文献
[1] A. Z. Broder., M. Charikar., A. M. Frieze., and $M.$
Mitzenmacher,-Wise Independent Permutations, “ STOC 1998, pp. 327-336${\rm Min}$[4] 小川浩明，武井由智，“対称群上の未知関数のラベル依存度の抽出，” 平成 24 年度電子情報通信学会信
$2C$ -2,
越支部大会講演論文集，Oct. 2012.
${\rm Min}$

まとめ

$O$

[3] Kondor, R., Shervashidze, N. and Borgwardt, K.
$M$ ., “The graphlet spectrum, ’ Proc. 26th ICML,
pp. 529-536 (2009)[5] Y. Takei and T. Itoh, “A General Constructionof-Wise Independent Permutations, ’ Trans.
Fund. IEICE, E83- $A$ (4), pp. 646-655 (2000)を満たすことが分かる．

6[2] P. Diaconis, Group Representations in Probability
and Statistics, Inst. Math. Stat. (1988)[6] Andrei Z. Broder and Michael Mitzenmacher,“Completeness and robustness properties of minwise independent permutations, “ Random Structures and Algomthms, Volume 18 Issue 1, pp.1830 (January 2001)[7] Gordon James and Adalbert Kerber, The Representation Theory of the Symmetnc Group, ENCY-

CLOPEDIA OF MATHEMATICS AND ITS AP-

PLICATIONS, Volume 16, CAMBRIDGE UNIVERSITY PRESS (1985)[8] Gordon James Representations of General Linear
Groups,, CAMBRIDGE UNIVERSITY PRESS(1984)[9] Jonathan Huang, Carlos Guestrin and Leonidas
Guibas ”Fourier Theoretic Probabilistic Inference
over Permutations, “ Journal of Machine Leaming
Research, 10, pp. 997-1070 (2009)