統計学輪講（第３９回）

日時	2000年12月19日(火)    15時50分〜16時40分
場所	経済学部5階視聴覚室
講演者　青木  敏(計数)
演題　	ネットワーク・アルゴリズムとその改良
概要：
  順序を考慮しない2元分割表における行と列の独立性の検定として、
通常の適合度カイ2乗検定の代わりに、Fisher の正確法検定を一般の
2元表の両側検定として拡張したものがしばしば用いられる。p値は、
周辺度数を固定したすべての分割表に関する、帰無仮説の下での確率
の和として定義され、厳密な計算を実行するために、いくつかのアル
ゴリズムが提案されている。Mehta and Patel (1983) の提案したネッ
トワーク・アルゴリズムは、現在でも、最も効率的なアルゴリズムと
して知られているが、特に周辺度数が不揃いな場合には、計算効率を
さらに上げることが可能である。
本輪講では、ネットワーク・アルゴリズムの概要を紹介し、アルゴリ
ズムの核となる最適化問題（最大化問題）の上界を、Mehta and Patel
とは異なる方法で評価し、それによって計算効率を上げることができ
ることを示す。