計算代数のdirect samplerへの応用 (Computer Algebra --Theory and its Applications)

Abstract

Diaconis-Sturmfels (1998)は行列Aのきめるaffinetoric idealの生成元がAできまるある分布のMarkov chain Monte Carlo (MCMC) simulationのためのMarkov基底を与えることを示したさらにこの生成元はGröbner基底の計算で求めることが可能である. A超幾何系はこのaffine toric idealと一階の方程式系できまる方程式系である上記の分布の分配関数(または正規化定数)はこの方程式系の解となる間野はこの分配関数の満たす漸化式(contiguity relation)を使えば効率的なdirect samplerを構成できることを示したこの漸化式を求めるにはさまざまな計算代数の手法が適用可能である. この小文は講演内容に従い, 間野のdirectsamplerを概説し, また最近得られたいくつかの結果の要約を述べる.

Diaconis-Sturmfels (1998) show that any set of generators of the affine toric ideal for a matrix A gives a Markov basis for the Markov chain Monte Carlo (MCMC) simulation for a distribution associated to A. Moreover, a set of generators can be obtained by Grabner basis computation. The A-hypergeometric system is a system of differential equations consisting of affine toric ideal m the 8, space and a set of first order differential equations. The partition function (or the normalizing constant) of the distribution associated to A is a solution of this system of differential equations. Mano show that recurrence relations (or contiguity relations) of the partition function gives an efficient direct sampler. We can apply several methods in computer algebra to derive recurrence relations for the direct sampler. In this note, we shortly introduce Mano's direct sampler and present a sketch of our recent results on the direct sampler.