現代数学解説

確率の問題を表現論を使って解く

表現論,群論

1663

はじめに

こんにちは. 今回は, Twitterで出した以下の問題の解説をしようと思います.

縦線が4本あり, ここに横線を $n$ 本書き加えて, あみだくじを作ります.
ただし, 以下のルールに従います.

横線は, 隣り合う縦線を結ぶもののみとする.
どの隣り合う縦線を結ぶ横線を書くかは, 確率 $\frac{1}{3}$ で決まる.
横線は, 上の方から順に書いていく.

このとき, 何も動かさないあみだくじができる確率を求めてください.

母関数で表す

この問題は, $S_{4}$ を $4$ 次対称群として, 隣接互換 $(12), (23), (34)$ から選んで $n$ 回掛け合わせて, 結果恒等置換になるような確率を求めよということになります. 掛け合わせて〇〇になる確率, と言えば母関数ですよね.

ただし今回は, よくあるやつと違って掛ける順番によって結果が変わってしまいます. なので普通の多項式は使えません. そこで群環の登場です. 群環を用いた母関数については私の過去の記事も参考にしてください.

群環 $C [S_{4}]$ で考えると, 以下のように言い換えられます.

$C [S_{4}]$ において, $(\frac{1}{3} (12) + \frac{1}{3} (23) + \frac{1}{3} (34))^{n}$ の $id$ の係数を求めよ.

行列環の直積で表す

$C [S_{4}]$ の構造を知りたいのですが, よく知られたようにこれは行列環の直積になり, しかも具体的な同型が表現論を用いて計算できます.

$G$ を有限群, $(W_{i}, ρ_{i})$ を $G$ の既約表現全体, $n_{i} = \dim W_{i}$ とする. $ρ_{i} : G \to {GL}_{n_{i}} (C)$ を線型に拡張して定まる $\tilde{ρ} : G \to \prod_{i} M_{n_{i}} (C)$ は同型である.

そこで, $S_{4}$ の既約表現を調べましょう.

$S_{4}$ の共役類は $id, (12), (12) (34), (123), (1234)$ で代表される $5$ つなので既約表現も $5$ つになります.
まず自明表現と置換の符号により $2$ つの $1$ 次表現があります.
次にKleinの四元群を $K$ として $S_{4} / K ≅ S_{3} ≅ D_{3}$ なので, $D_{3}$ の $C^{2}$ への自然な作用（回転と反転による）を, $K$ の元を自明に作用させることで $S_{4}$ の作用に拡張できこれが $2$ 次表現になります.
さらに ${(x, y, z, w) \in C^{4} | x + y + z + w = 0}$ への基底の置換による作用が $3$ 次表現になります.
残りは $3$ 次表現が $1$ つですが, これの指標は直交関係式から分かります. 実はこれは, 上の $3$ 次表現に符号による表現をテンソルしたものになっています.

以上より, $C [S_{4}] ≅ C^{2} \times M_{2} (C) \times M_{3} (C)^{2}$ であると分かります.

同型を具体的に求める

これが一番大変なところです. 上で求めた既約表現（を線型性で延長したもの）がそのまま同型になっているので, 既約表現を具体的に求めないといけません.

長くなるので畳んでおきます.

(クリックして開く)

・2次既約表現

上で述べた通り,

S_{3} ≅ D_{3}

の自然な作用, つまり回転を

R_{\frac{2 π}{3}} = (\begin{matrix} - \frac{1}{2} & - \frac{\sqrt{3}}{2} \\ \frac{\sqrt{3}}{2} & - \frac{1}{2} \end{matrix})

, 反転を

T = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})

に送るような作用を拡張するので,

(12) \mapsto T, (123) \mapsto R_{\frac{2 π}{3}}, (12) (34) \mapsto I

と送れば良いです.

・3次既約表現

これは少し難しいですが, 基底の入れ替えによる3次表現ということは正6面体群が浮かびます. （うれしいことに, 正6面体群は

S_{4}

となります！）
つまり, 立方体の回転に対応するような基底の取り換えが表現になっているはずです. 実際

(1234)

が

90

度回転の

(\begin{matrix} 0 & - 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix})

に対応します. 互換

(12)

はというと, 少し計算すると対角線での回転

(\begin{matrix} - 1 & 0 & 0 \\ 0 & 0 & - 1 \\ 0 & - 1 & 0 \end{matrix})

に対応させるとうまく行くとわかります.

さてもう1つの既約表現ですが, こちらは上で述べたように, 置換の符号の表現をテンソルしたものなので, 符号をただ掛けたものになります.

以上により, 具体的な同型を計算すると次のようになります.

$C [S_{4}] ≅ C^{2} \times M_{2} (C) \times M_{3} (C)^{2}$

$(12) \mapsto (1, - 1, (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} - 1 & 0 & 0 \\ 0 & 0 & - 1 \\ 0 & - 1 & 0 \end{matrix}))$

$(23) \mapsto (1, - 1, (\begin{matrix} - \frac{\sqrt{3}}{2} & - \frac{1}{2} \\ - \frac{1}{2} & \frac{\sqrt{3}}{2} \end{matrix}), (\begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 & - 1 \\ 0 & - 1 & 0 \\ - 1 & 0 & 0 \end{matrix}))$

$(34) \mapsto (1, - 1, (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & - 1 \\ 0 & - 1 & 0 \end{matrix}), (\begin{matrix} - 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}))$

これを用いて, $(\frac{1}{3} (12) + \frac{1}{3} (23) + \frac{1}{3} (34))^{n}$ を計算していきましょう.

$n$ 乗を計算する

上の同型により, 行列環の方では $(\frac{1}{3} (12) + \frac{1}{3} (23) + \frac{1}{3} (34))^{n}$ は

$(1, (- 1)^{n}, {(\begin{matrix} - \frac{\sqrt{3}}{6} & \frac{1}{2} \\ \frac{1}{2} & \frac{\sqrt{3}}{6} \end{matrix})}^{n}, {(\begin{matrix} \frac{2}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{3} & 0 \\ \frac{1}{3} & 0 & 0 \end{matrix})}^{n}, {(\begin{matrix} - \frac{2}{3} & 0 & - \frac{1}{3} \\ 0 & - \frac{1}{3} & 0 \\ - \frac{1}{3} & 0 & 0 \end{matrix})}^{n})$

になります. あとはこれを計算して, $C [S_{4}]$ に戻せばいいです.

ここで先に逆に戻す公式Fourier逆変換を思い出しておきます.

$G$ の既約表現全体を $(ρ_{i}, W_{i})_{i = 1}^{k}, \dim W_{i} = n_{i}$ としたとき, $C [G] ≅ \prod_{i = 1}^{k} M_{n_{i}} (C)$ の元 $u = (u_{1}, \dots, u_{k})$ を $C [G]$ に戻したときの $s \in G$ の係数は $\frac{1}{# G} \sum_{i = 1}^{k} n_{i} {Tr}_{W_{i}} (ρ_{i} (s^{- 1}) u_{i})$ である

ということで, 特に $s = id$ のときを考えて, 結局分かればいいのは上の行列のトレースなのです. $n$ 乗のトレースは固有値の $n$ 乗の和なので簡単に計算できます.

$(\begin{matrix} - \frac{\sqrt{3}}{6} & \frac{1}{2} \\ \frac{1}{2} & \frac{\sqrt{3}}{6} \end{matrix})$ の固有値は $\pm \frac{1}{\sqrt{3}}$ , $(\begin{matrix} \frac{2}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{3} & 0 \\ \frac{1}{3} & 0 & 0 \end{matrix})$ の固有値は $1, \frac{1 \pm \sqrt{2}}{3}$ であることから, Fourier逆変換公式を使って, 整理すると以下を得ます.

求める確率は, $n$ が奇数のとき $0$ であり, $n$ が偶数のとき

$\frac{1}{12} + \frac{1}{2 \cdot 3^{\frac{n}{2} + 1}} + \frac{1 + (1 + \sqrt{2})^{n} + (1 - \sqrt{2})^{n}}{4 \cdot 3^{n}}$

具体的に計算すると, $1, 0, \frac{1}{3}, 0, \frac{17}{81}, 0, \frac{115}{729}, \dots$ となります. $n \to \infty$ とすると $\frac{1}{12}$ つまり偶置換の個数の逆数になっているので, 合っていそうですね.