Direct sampling of discrete random structures with algebraic dependencies

点击翻译按钮获取中文摘要

データ解析のあらゆる分野においてサンプリングのアルゴリズムは必須である。近似的なサンプリングが使われることが多いので、近似ではないサンプリングを敢えてダイレクトサンプリングと呼ぶ。代表者はGelfandらが定義したGKZ超幾何系(A超幾何系)が定める離散確率分布族について計算代数を用いたダイレクトサンプリングのアルゴリズムを考案した。本研究は、付随する計算の効率化を図り、より一般的な代数的従属性をもつ離散確率構造のサンプリングに展開することを目的としている。令和4年度の研究実績として、より一般的な代数的従属性をもつ離散確率構造への展開（交付申請書研究方法２）について、量子計算の周辺にいくつかの課題を見出した。量子超越（何らかのタスクについて何らかの基準の下で古典計算が量子計算を優越すること）の実証は、ランダムに生成した量子回路の出力を古典計算機で生成するタスクについて行われており、その理由は分布函数の計算が計算複雑性の意味で難しいことに依拠する。ベイズ的手法を用いることで従来考えられているものとは異なる効率の高い古典計算のアルゴリズムを得た。この成果は研究集会で発表し、論文を作成中である。また、派生的ではあるが、本研究の発端になったDirichlet過程に関連するサンプリングの周辺に成果を得た。Dirichlet過程を定常分布とする拡散過程を有限グラフ上の測度に値をとる拡散過程として一般化し、双対なマルコフ過程を導出した。完全グラフの場合はDirichlet過程に関連する新しい漸化式を与える。応用として、グラフの独立集合を発見するアルゴリズムが要する時間の評価と、グラフに値をとる標本の尤度を計算するアルゴリズムを導出し、論文を発表した。