数理解析研究所講究録
第 1894 巻 2014 年 10-1810フーリエ変換によるあみだくじの解析
武井由智

中村彰吾
Shogo Nakamura

Yoshinori Takei

長岡技術科学大学
Nagaoka University of Technology

1

はじめに

1.1

背景と目的

分布の距離が，フーリエ係数行列によって，繰り返し
回数で抑えられることを示す．また，4 次の置換における具体的な計算結果を示す．第 4 節ではまとめを

離散的対象の順列を定義域とする関数に対して，対述べる．

象へのラベル付けによってどの程度その関数が左右されるかという尺度，ラベル依存度が 2012 年に小川
[4] によって対称群上のフーリエ解析を用いて定義さ2

準備れている．置換群上の関数のラベル依存度は，元の本節では対称群の表現，フーリエ変換，ラベル依存度の定義，及び擬似ランダム置換の発生方法の定義
数から引きさった成分が，元の関数をどれだけ占め について述べる．ここでの記述は [1,2,3,5] を参考ているかで定義される．擬似ランダム置換の発生法 としている．
を評価する上で，ラベル依存度をはじめとするフーリエ解析に基づくデータは有用な情報を含むと考え置換と対称群はカード 2.1
られる．たとえば，1988 年に Diaconis
関数のラベル不変な関数の空間への正射影を元の関$[5|$

シャッフルのモデルとしてランダムな互換の繰り返しを考え，結果の確率分布と一様分布との距離の上界を与えているが，そこでは対称群上のフーリエ解
析が重要な手法として応用されている．
そこで本論文では隣接互換の繰り返しによる擬似
ランダム置換 (あみだくじ) に注目し，その確率分布
関数と一様分布との距離がフーリエ係数行列の固有値と隣接互換の繰り返し回数によって上から抑えられることを示す (定理 3). とくに置換される対象の数 $n=4$ のとき (あみだくじの縦棒が 4 本のとき) の具体的な上界を導出する (定理 3 系 1). さらに，この場合において，あみだくじを環状とする (1 と $n=4$の互換を許す) ことが，一様分布との距離およびラベ
ル依存度を減少させることを示す．

$n$

$n$

$S_{n}:=\{\sigma$: $[n]arrow[n]|$ 全単射$\}$

で定義される． は，写像の結合を演算として群をなし， 次対称群と呼ばれる．
$S_{n}$$n$$S_{n}$$|S_{n}|=n!$ である． の要素のサイズは，$S_{n}$

これが $\sigma(j)=i_{j}(j=1, \ldots, n)$$\sigma$は，を満たすとき，$\sigma=[Matrix]$(1)のように表記され，たとえば $\sigma(1)=5,$ $\sigma(2)=$
$1,$

1.2

$[n]:=\{1,2, \ldots, n-1, n\}$ と個の対象の集合を，すると， 個の対象の置換の集合は，$\sigma(3)=4,\sigma(4)=3,\sigma(5)=2$, なる置換$\sigma$は，本論文の構成第 2 節では本論文で扱う対称群やその上の関数のフーリエ解析，ラベル依存度について述べる．第 3 節
では隣接互換の繰り返しによる確率分布関数と一様$\sigma=[Matrix]$ .

(2)

11
の様に表記される．任意の置換は，$i=k$$\pi(s_{i})=\{\begin{array}{l}s_{i+1} 1\leq i<ks_{1}\end{array}$$k<i\leq n$$s_{i}$という巡回置換 (cycle) $\pi=(s_{1}, s_{2}, \ldots , s_{k})$ の組み
合わせで表すことが出来る．式 (2) を巡回置換表記(cycle notation) で書くと，$\sigma=(152)(34)$

図 1: ラベルを貼り替えた置換の例となる．置換を構成する巡回置換の長さを巡回置換型 (cycle-type), あるいは単に型 (type) と呼ぶ．

$\lambda=$$(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{k}),$$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{k},$を $n$ の分割と呼び$\lambda\vdash n$

任意の巡回置換$\sum_{i=1}^{k}\lambda_{i}=n$整数$(s_{1}, s_{2}, \ldots, s_{k})$る．したがって，互換の集合は対称群全体を生成す

る．さらに任意の互換 $(i,j)$ は次のように隣接互換の積で表すことが出来る．

...

$(i,j)=\tau_{j-1}$$\tau_{i+1^{\mathcal{T}}i^{\mathcal{T}}i+1}$$n$$\lambda\vdash n$...

例えば $n=4$ のときを$\lambda_{1},$$\lambda_{k}$$\lambda_{2},$$\ldots,$

個のタイル$(2, 1, 1)=\ovalbox{\tt\small REJECT},$$(2,2)=H,$$\cdots$となる．Ferrers 図形に数字 1, 2, . . . , を過不足なく割り当てたものをヤング盤と呼ぶ．例えば $n=4$ の$n$とき$\tau_{j-1}$『に対して，$\lambda=$

ここで， は一般性を失わずに $i<i$ である．故に， 全体が隣接互換のみの積で生成することが出
$i,$

の分割

は互換の積， の並びで図的に表現したものを Ferrers 図形と呼ぶ．

で表すことが出来$(s_{1}, s_{2})\cdot(s_{2}, s_{3})\cdot\ldots\cdot(s_{k-1}, s_{k})$$\ovalbox{\tt\small REJECT}=(k, k+1)$

Young 直交表現 [3]

2.3

と書く．

$j$

$S_{n}$$t=$

来ることが分かる．

2.2

共役とラベルの貼り替えのようなものをいう．特に各行と列について数が昇順に並んでいるものを標準ヤング盤と呼ぶ． に対する標準ヤング盤の数はフック長 l。を用いて，$\lambda$

に対し，置換される 1, 2, 3, 4, 5 にそれぞれ 5,1,2,3,4 というラベルを貼ると置換$\sigma_{1},$$\sigma_{2}\in S_{5}$$\{\sigma_{1}, \sigma_{2}\}=$(3)$d_{\lambda}= \frac{n!}{\prod_{x}l_{x}}$(123) (45), (12) (3) $(45)\}$

$\{$

は

で表される．フック長とは Ferrers 図形の位置 のタイルに関して，より右側，より下側につづくタイ
ルの数に 1 を加えた数である．
群 $G$ の表現は， :$x,$ $y\in G$
であって，
$x$

$\{\pi_{1}, \pi_{2}\}=${(512)(34), (51)(2) (34)}のように見える．その様子を図 1 に示す．ラベルの張り替えは$\pi_{i}=\tau\sigma_{i}\tau^{-1},$$\dot{?}=1,2$$\tau=(\begin{array}{lllll}1 2 3 4 55 1 2 3 4\end{array})$$Garrow \mathbb{C}^{d\cross d}$$\rho$

に対して，$\rho(xy)=\rho(x)\rho(y),$ $\rho(x^{-1})=\rho(x)^{-1}$を満たすもの (すなわち， から次正則行列への準同型写像) をいう．また，この式から単位元 $e\in S_{n}$に対し $\rho(e)=I$ が得られる．表現が与えられた場合にある正則行列 に対し，$\rho$と表現できる．

また，$\sigma,$$\pi\in S_{n}$で$\exists_{\mathcal{T},\pi=\tau\sigma\tau^{-1}}$

のとき

$\pi$

と

$\sigma$

は

と
共役と呼び
に対し
は共役” なる関係は上の同値関係となる．この関係に関す$\pi_{1},$$\pi_{2}\in S_{n}$$\pi_{1}$$\pi_{2}$$d$$\rho,$$\rho_{1},$$\rho_{2}$$A$$S_{n}$

る同値類を共役類と呼ぶ．また，$\forall_{\mathcal{T},\sigma\in S_{n},f(\sigma)=}$$f(\tau\sigma\tau^{-1})$が成り立つ関数を類関数と呼ぶ．

$\rho(x)=A\{\begin{array}{ll}\rho_{1}(x) 00 \rho_{2}(x)\end{array}\}A^{-1}$$(x\in G)$

12と書けるときかつ $(i,j)=(k, l)$ のときはの直和であるといい，と書く．このとき は可約であるという． なわち，$\rho_{1}\oplus\rho_{2}$$\rho$$\rho$$\rho$は$\rho_{1},$$\rho\cong$$\rho_{2}$$\lambda=\lambda’$$1/d_{\lambda}$

である．す$\rho$

が表現の直和で書けないとき，既約であるといい，を既約表現と呼ぶ．対称群の場合，既約表現としてヤング直交表現 (YOR) がよく用いられる．YOR
は整数 の分割ごとに定義された既約表現:
であり，次数 は式 3 で与えらの要素は標準ヤング盤 でインれる．
$\lambda\vdash n$$n$$S_{n}arrow \mathbb{R}^{d_{\lambda}xd_{\lambda}}$$d_{\lambda}$$\rho_{\lambda}$$[\rho_{\lambda}(\tau_{k})]^{d_{\lambda}xd_{\lambda}}$$t$$\langle\rho_{\lambda,(i,j)}|\rho_{\lambda’,(k,l)}\rangle=\frac{1}{d_{\lambda}}\delta_{\lambda\lambda’}\delta_{ik}\delta_{jl}$が成立する． 上の関数
$S_{n}$$\rho_{\lambda}$:$S_{n}arrow \mathbb{R}^{d_{\lambda}xd_{\lambda}}$の既約表現における関数 $f$ の$f:S_{n}arrow \mathbb{R}$に対し，$\lambda\vdash n$

フーリエ変換は

デックスされ，対角成分は(6)$f( \lambda)=\sum_{\sigma\in s_{\mathfrak{n}}}f(\sigma)\rho_{\lambda}(\sigma)$(4)$[\rho_{\lambda}(\tau_{k})]_{t,t}=1/d_{t}(k, k+1)$

も標準ヤング盤の場合，(4) にとなる．また，$\tau_{k}(t)$で定義される．これに対し $7-|Jx$ 逆変換

加えて非対角要素$f( \sigma)=\frac{1}{n!}\sum_{\lambda\vdash n}d_{\lambda}tr[f(\lambda)\rho_{\lambda}(\sigma)^{T}]$

(7)

(5)

$[\rho_{\lambda}(\tau_{k})]_{t,\tau_{k}(t)}=\sqrt{1-1/d_{t}(k,k+1)^{2}}$が成り立つ．
があらわれる．他のすべての行列要素はゼロである．
ここで $d_{t}(i,j)=c(j)-c(i),$ $c(x)$ は の content と 補題 1. 関数$x$$p:S_{n}arrow \mathbb{R}$が $p(\pi_{i})=p(\pi_{i}^{-1})$ を満た呼ばれる量であり，ヤング盤の中に置かれた の列 すとき，
インデックスと行インデックスの差で定義される．すべての置換は隣接互換の積で表されることから，式(4), (5) によっての表現が定義できる．以$x$$\hat{p}(\lambda)=\hat{p}(\lambda)^{T}$$\forall_{\sigma}\in S_{n}$上のように定義したは，$\rho_{\lambda}(\sigma)^{-1}=\rho_{\lambda}(\sigma)^{T}$$\rho_{\lambda}$は直交行列である．
たす．すなわち，$\lambda=(2,2)$のとき$n=4,$
例として，を満$\rho_{\lambda}(\sigma)$

証明．

$p(\pi_{i})=p(\pi_{i}^{-1})$$d_{\lambda}=2$の $\sigma=(123)(4)$

さある．

で，

における値は$\rho_{(2,2)}((123)(4))=$がみたされるため，$\rho_{\lambda}$$\hat{p}(\lambda)=\sum_{\sigma\in S_{n}}p(\sigma)\rho_{\lambda}(\sigma)$$= \sum_{\sigma\in S_{n}}p(\sigma^{-1})\rho_{\lambda}(\sigma)$画$= \sum_{\sigma\in S_{n}}p(\sigma)\rho_{\lambda}(\sigma^{-1})$となる．

だが， は表現なのでし，さらに， は直交行列なので$\rho_{\lambda}(\sigma^{-1})=\rho_{\lambda}(\sigma)^{-1}$$\rho_{\lambda}$

また， に対し，指標と呼ばれる関数$\rho_{\lambda}$$\chi_{\lambda}$

が$\rho_{\lambda}$

が成立$\rho_{\lambda}(\sigma)^{-1}=\rho_{\lambda}(\sigma)^{T}$であるよって，$\chi_{\lambda}(\sigma):=tr[\rho_{\lambda}(\sigma)]$で定義される． は共役に対して不変な関数 (類関$\chi_{\lambda}$$\hat{p}(\lambda)=\sum_{\sigma\in \mathbb{S}_{n}}p(\sigma)\rho_{\lambda}(\sigma)^{T}=(\sum_{\sigma\in S_{n}}p(\sigma)\rho_{\lambda}(\sigma))^{T}=\hat{p}(\lambda)^{T}$

数 である．
$)$となり，$\hat{P}(\lambda)$2.4対称群上のフーリエ解析$f,$ $g:S_{n}arrow \mathbb{R}$に対し，これらの内積を

また，指標は対称行列である．口$\chi_{\lambda}$$\langle\chi_{\lambda}|\chi_{\lambda’}\rangle=\delta_{\lambda\lambda’}$類関数の空間は$\langle f|g\rangle=\frac{1}{n!}\sum_{\sigma\in S_{n}}f(\sigma)g(\sigma)$

は次を満たす:.

$\{\chi_{\lambda}\}_{\lambda\vdash n}$(S)で張られることが知られては類関数の空間のおり，式 (8) とあわせて，正規直交基底をなす．さらに，指標の2 乗和と共役の $(k, l)$ 成分は$\{\chi_{\lambda}\}_{\lambda\vdash n}$で定義する． の $(i,j)$ 成分と$\rho_{\lambda}$$\lambda=\lambda’$$\rho_{\lambda’}$かつ $(i,j)=(k, l)$ のときを除き直交する． 類の関係として下が成立する．

13
定理 1. [1]に対して，$\pi’\in S_{n}$$\pi,$$c(\pi)$

を

$\pi$

の共役類

2. 各 $1\leq i\leq l$ に対してのサイズとするとき次が成立する．

$\pi_{i}$を隣接互換の集合$\{(j, j+1)|1\leq j\leq n-1\}\subseteq s_{n}$から，一様ランダムに抽出する．

( と ’f 共役)$J\grave{}\grave{}$$\frac{1}{c(\pi)}$

$\pi$

$\pi$

(9)

$\frac{1}{n!}\sum_{\lambda\vdash n}\chi_{\lambda}(\pi)\chi_{\lambda}(\pi’)=\{$

0(その他)

を周波数領域のそれに結びつけ
また，内積る，パーセバルの定理が成立する．
$\langle f|g\rangle$

定理 2(パーセバルの定理). [2] 関数$S_{n})$$f(\sigma),$ $g(\sigma)(\sigma\in$3.

$\pi=\pi\iota\ldots\pi_{2}\pi_{1}$繰り返し回数とする．口に対する性質を考察するとき， を固定すると，ランダム置換の出力が の偶奇に応じて，偶置換または奇置換に偏る不都合が生じる．そこで定義 1 では 段のあみだくじと言った場合，確率
$k$

$k$

$k$

$k$

1/2 で 段または $k+1$ 段のあみだくじがそれぞれ選ばれるモデルを考えている．
この擬似ランダム置換は図 2 のようなあみだくじ

に対して

$k$

$\sum_{\sigma\in S_{n}}f(\sigma)g(\sigma)=(\frac{1}{n!})^{2}\sum_{\lambda\vdashn}d_{\lambda}tr[f(\lambda)^{T}\hat{g}(\lambda)].$と考えられる．要素数

2.5

$n$

が縦棒の数で，隣接互換の

回数が横棒の本数に対応している．一回隣接互換による置換 は，点線で挟まれた横棒一本のあみだく
上の確率分布を と置くとじに対応し，その畳み込み$\pi_{i}$$S_{n}$

関数 $f,$:$g$$S_{n}arrow \mathbb{R}$はそれぞれランダム置換$\sigma,$$P$$\tau$の確率分布関数とする．つまり $f(\sigma)=Pr[\sigma],$ $g(\tau)=$
が独立であるとする．2 つのランダム置換( が先， が後に作用する)
とき，2 つの合成であることに注意する． 回がいかなる確率分布に従うかを考える．$h(\pi)=Pr[\pi]$ となる．
は を 段
とすると
$[AJ$ で事象のインジケータ変数 $(A$ が 隣接互換による確率分布をとおくとき，$g_{k}=p*\cdots*$p(右積み重ねたものなので，式 (10) より，
真のとき 1, 偽のとき ) で表せば辺は 回畳み込み) であり，この関係を式 (11) を用$p(\pi_{i})=\{\begin{array}{ll}\frac{1}{n-1} (\pi、が一回隣接互換)0 (それ以外)\end{array}$$Pr[\tau|$$\sigma,$$\pi=\sigma\tau$$\tau$$\tau$$\sigma$$p(\pi_{i})=p(\pi_{i}^{-1})$

$A$

$k$

$g_{k}$$g_{k}$

$P$

$k$

$O$

$k$

いてフーリエ係数で表現すると$h( \pi) = \sum_{\sigma,\tau\in \mathbb{S}_{n}}f(\sigma)g(\tau)[\pi=\sigma\tau I$$g_{k}=\hat{p}^{k}\wedge.$$= \sum_{\tau\in S_{n}}f(\pi\tau^{-1})g(\tau)$$= f*g(\pi)$ .

(10)

定義 1 の$P^{(*(k+1))})$

すなわち， は畳み込み $f*g$ となる．一般に $f*g$ について，そのフーリエ変換は簡明な性質をもつ，つま$k$$f_{k}= \frac{1}{2}(P^{(*k)}+$段あみだくじでは，であるため，$h$(12)$\hat{f}_{k}=\frac{\hat{p}^{k}+\hat{p}^{k+1}}{2}$り，畳み込み定理$\overline{f*g}(\lambda)=f(\lambda)\cdot\hat{g}(\lambda)$(11)が成立する．この式の右辺はフーリエ係数行列の積が成立する．
次に隣接互換の他に 1 とのあみだくじを定義する．

$n$の互換を認めた，環状定義 2(環状あみだくじ). 次の方式で得られるラン
ダム置換 を環状あみだくじと呼ぶ．

である．

$\pi$

2.6

擬似ランダム置換の生成法

本論文で考察する擬似ランダム置換生成法はランダムな隣接互換の繰り返しによるものを考える．よ1. 等確率で を
$l$

置換

$\pi$

を

$k$

段あみだくじと呼ぶ．

1. 等確率で$l$

を $k,$ $k+1$ から選ぶ．

$k+1$ から選ぶ．

2. 各 $1\leq i\leq l$ に対してを 1 と の互換と隣接互換の集合 $\{(j,j+1)|1\leq j\leq n-1\}U\{(1, n)\}\subseteq$

り正確には次の通り定義する．

定義 1(あみだくじ). 次の方式で得られるランダム$k,$$S_{n}$

3.

$\pi_{i}$$n$から，一様ランダムに抽出する．

$\pi=\pi_{l}\cdots\pi_{2}\pi_{1}$とする．口

これは図 2 のあみだくじにおいて 1 と $n(=5)$ の間にも横棒が発生するモデルである．

14$123 4 5$

で，式 (8) から$P(P(f))$$=$$\sum_{\lambda’\vdash n}\sum_{\lambda\vdash n}\langle f|\chi_{\lambda}\rangle\langle\chi_{\lambda}|\chi_{\lambda’}\rangle\chi_{\lambda’}$$= \sum_{\lambda\vdash n}\langle f|\chi_{\lambda}\rangle\chi_{\lambda}$(16)$= P(f)$であるから$\langle f|P(f)\rangle = \langle f|P(P(f))\rangle$$= \langle P(f)|P(f)\rangle$

(17)

である．

関数 $f$ のラベルの貼り換えに対する関数 $f$ の安定性の尺度がラベル依存成分 $f-P(f)$ と $f$ のそれぞれの 2- $J$ ルムの 2 乗の比として，

図 2: 隣接互換の繰り返しに基づく置換

2.7$LD(f)= \frac{\langle f-P(f)|f-P(f)\rangle}{\langle f1f\rangle}$対称行列と固有値

実行列

$A$

(18)

で定義される．この式はのフロベニウスノルムは$\langle f-P(f)|f-P(f)\rangle$$\Vert A\Vert_{F}=\sqrt{tr[A^{T}A]}$$=\langle f|f\rangle-2\langle f|P(f)\rangle+\langle P(f)|P(f)\rangle$と定義する．trの成分の 2 乗和であることに注意する． が 次対称行列であるとき直交行列とするとで対角化でき， の固有値を$[A^{T}A]h^{\backslash ^{\backslash }}A$

$A$

$A$

$U$

$=\langle f|f\rangle-\langle P(f)|P(f)\rangle$$d$$\mu_{1},$$\ldots,$$\mu_{d}$であることから，(13)$tr[A^{k}A^{Tk}]=\sum_{i=1}^{n}\mu_{i}^{2k}$$LD(f) = \frac{\langle f|f\rangle-\langle P(f)|P(f)\rangle}{\langle f1f\rangle}$$= 1- \frac{\langle P(f)|P(f)\rangle}{(f1f\rangle}$

乗のフロベニウスノルムが固有値の $2k$ 乗和で表現できる．

となり，実対称行列の2.8ラベル依存度の定義 [4]

関数

$f$

(19)

$k$

のラベル非依存成分 $P(f)$と書くことができる．

3
として

(14)

$(P(f))( \sigma)=\sum_{\lambda\vdash n}\langle f|\chi_{\lambda}\rangle\chi_{\lambda}(\sigma)$

擬似ランダム置換の解析

Diaconis [5] は一般の互換 $(i,j)(1\leq i<j\leq n)$ の繰り返しに基づく確率分布の一様分布との距離の上界を示した．そこではフーリエ解析，特にパーセバルのような関数が考えられる．これは 2.4 節で述べたように，$\{\chi_{\lambda}\}_{\lambda\vdash n}$あるから $P$ はが類関数の空間の正規直交基底でから類関数空間への直射影とみからラベル非依存成分 $P(f)$ を引く$\mathbb{R}^{s_{n}}$なせる．関数とラベル依存成分が得られる．一般に
$f$

$f,$

$g\in \mathbb{R}^{s_{\mathfrak{n}}}$にの定理が重要な役割を果たしている．この節では定義 2 で与えたような隣接互換の繰り返しによる確率分布にフーリエ解析を適用して解析を行う．
まず，確率分布関数 と一様分布との距離を $f$ の$f$

フーリエ係数を用いて表現することで，フーリエ係
数行列の固有値によって，確率分布 と一様分布
$f$

対し

$u$

の距離が繰り返し回数で抑えられることを示す．また，実際に隣接互換の繰り返しによって確率分布$\langle P(f)|g\rangle = \sum_{ム\vdash n}\langle f|\chi_{\lambda}\rangle\langle\chi_{\lambda}|g\rangle$$u$$= \langle f|P(g)\rangle$

(15)

$f$

と

一様分布 の距離がどの程度近づくかを示す．また，$n=4$ の場合に実際に計算を行いその結果を示す．

15
3.1

一様分布との距離 [2, Chap.17, The
Upper Bound Lemma]

くじ $(横棒 k, k+1 本が確率}1/2 で選ばれる)$ の場合であった まを考えると式 (12) よりた補題 1 よりは対称行列である．その 乗であ$\hat{f}_{k}=\frac{\hat{p}^{k}+\hat{p}^{k+1}}{2}$$k$$\hat{p}(\lambda)$

任意の確率分布

$f$

と一様分布

く距離について考える．関数

$f$

$u$

の 2- $J$ ルムに基づと一様分布の距離の2 乗がる$\hat{p}^{k}$は対称で，このことから践は対称である．よっは実数値対称行列であるて，式 (21) についてことから，式 (21) の値は$\hat{f}_{k}(\lambda)$$\Vert f-u\Vert_{2}^{2}=\sum_{\sigma\in S_{n}}|f(\sigma)-u(\sigma)|^{2}$$\frac{1}{n!}\sum_{(n)\neq\lambda\vdash n}d_{\lambda}\Vert\hat{f}k(\lambda)\Vert_{2}^{2}$

であり，定理 2(パーセバルの定理) より$= \frac{1}{n!}\sum_{(n)\neq\lambda\vdash n}d_{\lambda}tr[\hat{f}_{k}(\lambda)\hat{f}_{k}(\lambda)^{T}].$$\sum_{\sigma\in S_{n}}|f(\sigma)-u(\sigma)|^{2}=\frac{1}{n!}\sum_{\lambda\vdash n}d_{\lambda}\Vert f(\lambda)-\hat{u}(\lambda)\Vert_{2}^{2}(20)$

右辺を変形するととフーリエ係数で表せる．ここで確率分布関数

いては，その自明表現$\rho_{(n)}$

$f$

につ

$k$

$\wedge$に対するフーリエ係数が$\frac{1}{n!}\sum_{\lambda\vdash n,\lambda\neq(n)\lambda\neq(1^{n})},d_{\lambda}$$k+1$

tr $[( \frac{p(\lambda)+p(\lambda)}{2})$$f((n))= \sum_{\sigma\in S_{n}}f(\sigma)\rho_{(n)}(\sigma)=\sum_{\sigma\in S_{n}}f(\sigma)\cdot 1=1$$( \frac{\hat{p}(\lambda)^{k}+\hat{p}(\lambda)^{k+1}}{2})^{T}]$である．また確率分布関数

くじの場合，$f=f_{k}$が定義 1 のとすると，1 の
$f$

$k$

段あみだ

$=\underline{1}$$4^{\sum_{\lambda\vdash n,\lambda\neq(n)\lambda\neq(1^{n})},d_{\lambda}}n!$tr$[(\hat{p}(\lambda)^{k}+\hat{p}(\lambda)^{k+1})$$(\hat{p}(\lambda)^{k}+\hat{p}(\lambda)^{k+1})^{T}]$

.

(22)

$\hat{f}_{k}(1^{n})=\frac{\hat{p}((1^{n}))^{k}+\hat{p}((1^{n}))^{k+1}}{2}$

補題 1 より$\hat{p}(\lambda)=\hat{p}(\lambda)^{T}$であるため，この式の値は$= \frac{(-1)^{k}+(-1)^{k+1}}{2}=0$$\frac{1}{4n!}\sum_{\lambda\vdash n,\lambda\neq(n)\lambda\neq(1^{n})},d_{\lambda}tr[(\hat{p}(\lambda)^{k}+\hat{p}(\lambda)^{k+1})$

である．よって，九と の直流成分 $(\lambda=(n))$ に対するフーリエ係数は 1 である．また， の直流成分以$\hat{u}$$(\hat{p}(\lambda)^{k}+\hat{p}(\lambda)^{k+1})]$$\hat{u}$外 $(\lambda\neq(n))$ のフーリエ係数行列が$0$行列であることから$= \frac{1}{4n!}\sum_{\lambda\vdash n,\lambda\neq(n),\lambda\neq(1^{n})}d_{\lambda}tr[(\hat{p}(\lambda))^{2k}(\hat{p}(\lambda)+I)^{2}].$(23)$\frac{1}{n!}\sum_{\lambda\vdash n}d_{\lambda}\Vert\hat{f}_{k}(\lambda)-\hat{u}(\lambda)\Vert_{2}^{2}$

ここで$= \frac{1}{n!}\sum_{\lambda\vdash n,\lambda\neq(n),\lambda\neq(1^{n})}d_{\lambda}\Vert\hat{f}_{k}(\lambda)\Vert_{2}^{2}$(21)$\hat{p}$

の固有値を
とし，
の範囲での絶対値における最大固有$\mu_{(\lambda)1},$$\ldots,$$\lambda\vdash n,$$\mu(\lambda)d_{\lambda}$$(n),$ $(1^{n})$$\lambda$を値をとなり，関数
きる．関数$f_{k}$$f_{k}$のフーリエ係数行列で表すことがでが $karrow\infty$ で一様分布に近づくとき$\mu_{\max}=\max_{\lambda\vdash n,\lambda\neq(n),\lambda\neq(1^{n}),1\leq i\leqd_{\lambda}}(|\mu_{(\lambda)i}|)(24)$と定義する．もし $\mu_{\max}<1$ なら，和の下の trace にであり，式 (20) の右辺も に向かう． ついて不等式
つまりであり，これは関数
姦の直流成分を除いたフーリエ係数行列が 0 行列に$\Vert f_{k}-u\Vert_{2}^{2}arrow 0$$0$$\Vert\hat{f}_{k}(\lambda)\Vert_{2}arrow 0(\lambda\neq(n))$$tr[(\hat{p}_{A})^{2k}((\hat{p}_{\lambda})+I)^{2}]$

向かうことを意味する．

3.2$\leq\mu_{\max}^{2k}(\mu_{\max}+1)$

繰り返し回数とフーリエ係数行列の固
有値の関係

確率分布九が段数 によってどの程度一様分布に近づくかを示す．ここで姦が定義 1 の 段あみだ
$k$

$u$

$k$

(tr

$[(\hat{p}_{\lambda})]+$

tr $[I]$ )(25)(証明は付録 A 参照) を適用して$\Vert fk-u\Vert_{2}^{2}$$\leq\underline{1}\sum_{\lambda\vdash n}d_{\lambda\mu_{\max}^{2k}(\mu_{\max}+1)(tr[\hat{P}(\lambda)]+}$$4n!$

tr $[I])$ .

16$\mu_{\max}$は$\lambda$に依らないので前に出すと，右辺は次のよ

うに変形できる

3.3

固有値，一様分布との距離の計算$n=4$ に限定して具体的な数値による以下では，計算を行う．隣接置換を一回行った置換の確率分布に対する$n=4$ としたときの各とおき，のフーリエ係数行列とその固有値を示す．行列のインデックスとなる標準ヤング盤を行および列に添え$\frac{1}{4n!}\sum_{\lambda\vdash n}d_{\lambda}\mu_{mm}^{2k}(\mu_{mr}+1)(tr[\hat{p}(\lambda)]+ tr[I])$$\lambda\vdash 4$$p_{1}$.

$= \frac{\mu_{\max}^{2k}(\mu_{\max}+1)}{4n!}\sum_{\lambda\vdash n}d_{\lambda}(tr[\hat{p}(\lambda)]+tr[I])$$p_{1}$

書きしてある．
ここで$\neg_{n}1.$$=$$\sum_{\lambda\vdash n}d_{\lambda}tr[\hat{p}(\lambda)]$が式 (7) のフーリエtrで逆変換による単位元でのの値 $p(e)$$n!$あることおよびに注意すると(tr
tr $[I]$ ) $=n!$ である．したがって$[\hat{p}(\lambda)\rho_{\lambda}(e)^{T}|$$\frac{1}{n!}\sum_{\lambda\vdash n}d_{\lambda}$

$=$

$p$

$\sum_{\lambda\vdash n}d_{\lambda}^{2}$$0$$\hat{p}_{1(4)}=\overline{L^{1}\perp\perp\Delta^{i}}$$\overline{L^{1}\perp 2\llcorner\llcorner\lrcorner(1)^{J4}}$$=$$[\hat{p}(\lambda)]+$$\sum_{\lambda\vdash n}d_{\lambda}$$\hat{p}_{1(3,1)}=$$\frac{\mu_{\max}^{2k}(\mu_{mw}+1)}{4n!}\sum_{\lambda\vdash n}d_{\lambda}(tr[(\hat{p}(\lambda)]+tr[I])$$\overline{\frac{\#^{s\lrcorner_{-}}2}{F_{\ell}^{12\supset 3}\mapsto_{3}^{12}\Delta^{4}}}$$= \frac{\mu_{\max}^{2k}(\mu_{\max}+1)}{4}$以上をまとめて次の定理を得る．

$\hat{p}_{1(2,2)}=\overline{\frac{\fbox_{2}^{13}\supset 4}{\#}}$

定理 3. 1 段のあみだくじの確率分布を

:

$p$

段
とする．

$s_{n},$$k$

あみだくじの確率分布を九を式 (24) で定義した九の固有値の最大絶対値とし，とする．このとき九と一様分布$= \frac{p^{(\cdot k)}+p^{(\cdot(k+1))}}{2}$野野野$\mu_{mm}$$\mu_{\max}\leq 1$$u$$\hat{p}_{1(2,1,1)}=$$(2x_{9}- \frac{952}{6183}-\frac{5}{9,2}I2{}_{0}L$の 2 乗距離の 2 乗は上界逼 $)$$\Vert f_{k}-u\Vert_{2}^{2}\leq\frac{1}{4}\mu_{mm}^{2k}(\mu_{mr}+1)$$(-31)\ovalbox{\tt\small REJECT}_{I}^{2}$

をもつ．
これは

$\hat{p}_{1(1,1,1,1)}=\ovalbox{\tt\small REJECT}_{4}^{1}32$$p(\lambda)\wedge$の固有値の $\lambda\neq(n),$$(1^{n})$での絶対値における最大値が 1 未満であれば，次に隣接互換の他に 1 と の互換を認めた，環状のあみだくじ (定義 2) を考える．この環状のあみだ$n$$f_{k}= \frac{v^{(\cdot k)}+v^{(\cdot(k+1))}}{2}$が，2 乗ノルムにおいて一様分布に収束することを示す．また， に対する一様分布との距離の上界が最大$k$固有値で評価できる．

くじの 1 段，つまり一回置換の確率分布をフーリエ係数行列とその固有値を示す．

さらに，次節で調査する $n=4$ に対する 段あみだ
くじのフーリエ解析から次の具体的結果が得られる．
$k$$\hat{p}_{2(4)}=\overline{L^{\iota}\perp 2\frac{34}{}}$系 1(定理 3 に対する). $n=4$ に対する様分布を $u,$$k$

段あみだくじから生じる

上の一
上の分布

$S_{n}$$S_{n}$

を九とすると$\hat{p}_{2(3,1)}=$$\overline{\frac{}{}\frac{B^{\lrcorner}21l\underline{4}}{H_{4}^{\iota\lrcorner}1H_{s_{2}}^{2}\lrcorner}}$$\Vert f_{k}-u\Vert_{2}^{2}\leq\frac{1}{4}(\frac{1+\sqrt{2}}{3})^{2k}(\frac{1+\sqrt{2}}{3}+1)$$\leq 0.451(0.805)^{2k}.$$\hat{p}_{2(2,2)}=$$\overline{\frac{fl}{f}34241213}$$\overline{L^{1}\lrcorner^{2}\lrcorner\lrcorner\underline{r}(1)^{J}}$$p_{2}$とおき，

17

図 3: 段数$k$に対する$p_{1)}p_{2}$の一様分布との距離隣接互換の繰り返しにょる疑似ランダム置換 (あみだくじ) に注目し，その確率分布の性質を対称群上18のフーリエ解析に基づいて調査した．その結果確率分布関数と一様分布との距離がフーリエ係数行列の固有値とあみだくじの段数によって上から抑えられることを示した (定理 3). さらに，置換される対象の数 $n=4$ のとき (あみだくじの縦棒が 4 本) のあみだ
くじ (定義 1) の具体的な上界を導出した (定理 3 系
1 . また $n=4$ のとき，あみだくじと環状あみだく$x<0$ に対して，$\xi=-x=|x|>0$ とおくと
$f(x)=f(-\xi)=\xi^{2k}(1-\xi)<\xi^{2k}(1+\xi)=f(\xi)$ .

よって，式 (26) で $x=\xi$ としたものから$0\leq|x|\leq\alpha\Rightarrow f(x)\leq f(\alpha)$.

$)$

布との距離およびラベル依存度が前者のそれより減つまり $|x|\leq\alpha$ なら $x^{2k}(1+x)\leq\alpha^{2k}(1+\alpha)$ . さらになら $1+x\geq 0$ から $x^{2k}(1+x)^{2}\leq\alpha^{2k}(1+\square$

少することを示した．

$\alpha)(1+x)$

じ (定義 2) を比較し，後者の確率分布関数と一様分$\alpha\leq 1$.

命題 1. 実対称行列 に対し，その絶対値におけるなら最大固有値を とするとき，$A$

謝辞$\alpha\leq 1$$\alpha$

トレースの不等式についてご教示頂いた和田州平氏に感謝いたします．

tr $[A^{2k}(A+I)^{2}]\leq\alpha^{2k}(\alpha+1)(tr[A+I])$ .

証明． の固有値を $\mu_{1)}\mu_{d}$ とする．補題 2 の$A$を$\mu_{i}$$x$として足し合わせ，

参考文献$\sum_{i=1}^{d}\mu_{i}^{2k}(\mu_{i}+1)^{2}\leq\alpha^{2k}(\alpha+1)\sum_{i=1}^{d}(\mu_{i}+1)(27)$

[1]

$J$

.- $P$. セール．有限群の線形表現．岩波書店．1974.

[2] Audrey Terras: Fourier Analysis on Finite
Groups and Applications London Math. Soc.
Student Texts 43, 1999
[3] Risi Kondor. Group theoretical methods in machine learning. Ph. . thesis, Columbia University, 2008.

とするとき，左辺は$D=UAU^{-1}=(\begin{array}{lll}\mu_{1} 0 \ddots 0 \mu_{d}\end{array})$

tr $[D^{2k}(D+I)^{2}]$ であり，これは$D$[4] 小川浩明，武井由智．“対称群上の未知関数のラベル依存度の抽出”, 平成 24 年度電子情報通信$2C$ -2, Oct. 2012.
学会信越支部大会講演論文集，[5] Persi Diaconis: Group Representations in Probability and Statistics. IMS. 1988.

tr $[U^{-1}(D^{2k}(D+I)^{2})U]$$=tr[U^{-1}D^{2k}UU^{-1}(D+I)^{2}U]$$=tr[A^{2k}(A+I)^{2}]$に等しい．また，式 (27) の右辺は$\alpha^{2k}(\alpha+1)$

である

付録 $A$

レースの不等式 (25) の証明$\vdash$補題 2. 実数 $x(-1<-\alpha<x<\alpha<1)$ に対して
$x^{2k}(x+1)^{2}\leq\alpha^{2k}(\alpha+1)(x+1)$.

$x\geq 0$ にお証明．関数 $f(x):=x^{2k}(1+x)$ を考える．

いて $f(x)$ は増加である．よって$0\leq x\leq\alpha\Rightarrow f(x)\leq f(\alpha)$

.

(26)

(tr $[A]+$ tr $[I]$ )口