フックウォークを用いた確率論的証明法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/04/18 14:05 UTC 版)
「フック長の公式」の記事における「フックウォークを用いた確率論的証明法」の解説
これは1979年に、 C. Greene, A. Nijenhuis と H. S. Wilf によって発見された、確率論的証明法である。証明の概略は、次のとおりである。 e λ = n ! ∏ ( i , j ) ∈ Y ( λ ) h λ ( i , j ) . {\displaystyle e_{\lambda }={\frac {n!}{\prod _{(i,j)\in Y(\lambda )}h_{\lambda }(i,j)}}.} を定義し、 d λ = e λ {\displaystyle d_{\lambda }=e_{\lambda }} を証明する。 d λ {\displaystyle d_{\lambda }} は以下で与えられる。 d λ = ∑ μ ↑ λ d μ , {\displaystyle d_{\lambda }=\sum _{\mu \uparrow \lambda }d_{\mu },} ここで、 μ ↑ λ {\displaystyle \mu \uparrow \lambda } は、 μ {\displaystyle \mu } がヤング図形λから一つのコーナーセルを削除することで得られるヤングタブローであることを表している。 そのようなμの全体にわたって和をとる。ここで、慣習として ϕ {\displaystyle \phi } を空のダイアグラムとして、 d ϕ = 1 {\displaystyle d_{\phi }=1} を用いる。 上の式に対する説明は、「ヤングタブローの最大項はそのコーナーセルで生じるものである」となる。 そのセルを削除することで、μの形のヤングタブローを得る。 μの形のヤングタブローの数が d μ {\displaystyle d_{\mu }} であり、それらμに関して和をとることでその式を得る。 ここで、 e ϕ = 1 {\displaystyle e_{\phi }=1} であることにも注意されたい。それゆえ、次を示せば十分で、 e λ = ∑ μ ↑ λ e μ , {\displaystyle e_{\lambda }=\sum _{\mu \uparrow \lambda }e_{\mu },} その結果、 d λ = e λ {\displaystyle d_{\lambda }=e_{\lambda }} は帰納的に証明される。 上の式の和は、次のように式を書き換えることによって、確率の和と捉えることができる。 ∑ μ ↑ λ e μ e λ = 1. {\displaystyle \sum _{\mu \uparrow \lambda }{\frac {e_{\mu }}{e_{\lambda }}}=1.} われわれはこのようにして、 e μ e λ {\displaystyle {\frac {e_{\mu }}{e_{\lambda }}}} が、ヤング図形μの集合上の確率測度を定めている。(ここで μ ↑ λ {\displaystyle \mu \uparrow \lambda } ) これはフックウォークと呼ばれるランダムウォークを定義を用いた構成法によるものである。 フックウォークは、ヤング図形λの上で、ひとつのコーナーセルを選択する。 フックウォークは次のルールによって定義される。 (1) | λ | {\displaystyle |\lambda |} 個のセルのなかから一様ランダムにひとつのセルを選び、そこからランダムウォークを始める。 (2) 現在の ( i , j ) {\displaystyle (i,j)} セルの次のセルは、一様ランダムにフック H λ ( i , j ) ∖ { ( i , j ) } {\displaystyle H_{\lambda }(i,j)\setminus \{(i,j)\}} から選ぶ。 (3) 一つのコーナーに到達するまでこれを続け、そのコーナーセルを c {\displaystyle {\textbf {c}}} とする。 命題: λに属するすべてのコーナーセル ( a , b ) {\displaystyle (a,b)} に対して、次が成り立つ。 P ( c = ( a , b ) ) = e μ e λ , {\displaystyle \mathbb {P} \left({\textbf {c}}=(a,b)\right)={\frac {e_{\mu }}{e_{\lambda }}},} ここで、 μ = λ ∖ { ( a , b ) } {\displaystyle \mu =\lambda \setminus \{(a,b)\}} . この命題を得れば、すべての c = ( a , b ) {\displaystyle {\textbf {c}}=(a,b)} に関して和をとることによって、 ∑ μ ↑ λ e μ e λ = 1 {\displaystyle \sum _{\mu \uparrow \lambda }{\frac {e_{\mu }}{e_{\lambda }}}=1} を得る。
※この「フックウォークを用いた確率論的証明法」の解説は、「フック長の公式」の解説の一部です。
「フックウォークを用いた確率論的証明法」を含む「フック長の公式」の記事については、「フック長の公式」の概要を参照ください。
- フックウォークを用いた確率論的証明法のページへのリンク