平成23（2011）年度　一般研究２実施報告書

 

課題番号

23−共研−2058

分野分類

統計数理研究所内分野分類

g

主要研究分野分類

2

研究課題名

Eulerian 分布と正規乱数フィルタの生成

フリガナ

代表者氏名

ツチヤ タカヒロ

土屋 高宏

ローマ字

Tsuchiya Takahiro

所属機関

城西大学

所属部局

理学部数学科

職　　名

准教授

配分経費

研究費

40千円

旅　費

63千円

研究参加者数

3　人

 

 

研究目的と成果（経過）の概要

[研究目的]
本研究は，バケットソートと呼ばれる高速なデータソーティング技法があり，その変形版に注目する．これは並べ替えるデータの取りうる値がk通りのとき，あらかじめk個の入れ物を用意するか，あるいは動的にそれを増やしながら，各々の数字に対応した入れ物にデータを入れていくアルゴリズムである．本研究の発端は，n個の連続した数字(カード)があり，あらかじめ用意する入れ物の数を決めず，最終的に必要な入れ物の数がデータの初期状態に依存する変形バケットソートを考え，その数に関する離散確率分布を導出したことによる．この離散確率分布は，導出の際に現れる漸化式がEulerian数と呼ばれる数列を構成することから，Eulerian分布と呼んだ．本研究ではEulerian分布に関連する基礎研究およびその応用として，以下の課題に取り組む．
(1) Eulerian分布は連続一様分布にしたがう確率変数の和の分布と関係し，漸近的に正規分布に収束することがわかっている．このため，分布の漸近理論や正規確率分割と関係している．Eulerian分布に対する正規分布の近似は，通常の漸近展開の方法でかなり良い精度が得られることから，正規分布の近似精度の良さを使った新しい正規乱数生成法の構成（正規乱数フィルタの構築）が可能であると考えられる．このことから，カードのシャッフルが一様乱数の生成と関係し，カードの並びから正規乱数が導かれることになる．この関係を利用して正規乱数フィルタを構築し，理論的な解明と実装を行う．
(2) データソーティング技法から派生するさまざまな確率分布モデルの研究を推進する．例えば，カードの番号が1からnの異なる数の並べ替えについて，番号が欠落している場合の入れ物数の確率分布の導出を試みる．この分布は非対称な確率分布となることが予想され，特に確率分布の導出の際に現れる統計的・代数的性質について研究する．

[研究経過]
(1) 正規乱数フィルタの構成ついては，入れ物の数に対応する離散変数から正規乱数に対応する連続変数への変換（配置）がポイントになるので，まずはこの割り当て方法について研究打合せを実施した．当該確率分布が一様分布に従う確率変数の和の分布と酷似していることがキュムラントの観点から分かっているので，このことを利用できないか現在検討している．
(2) カードの番号が欠落している場合の入れ物数の確率分布の導出は引き続き検討中である．

 

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

当該研究に関連する情報源，これまでの成果は以下の通りである．

[学会・シンポジウム発表]
(1) 変形バケットソートにおけるバケット数の分布について (2007) 統計関連学会, 神戸大学
(2) ある種の並べ替え算法における確率分布と変形パスカル三角形 (2007) 第12回情報・統計科学シンポジウム, 21世紀COEプログラム「機能数理学の構築と展開」（九州大学大学院数理学研究院）共催, 九州大学
(3) ある種の並べ替え算法における離散型確率分布モデル (2008) 統計数理研究所共同利用研究重点テーマ「統計メタウェアの開発」共通公開研究会, 統計数理研究所
(4) ソーティング過程に現れるEulerian数と離散型確率分布 (2008) 人工知能学会, データマイニングと統計数理研究会(SIG-DMSM), 小樽市民センター研修室
(5) ある種の並べ替え算法に現れる確率分布とEulerian数 (2008) 統計関連学会, 慶應義塾大学
(6) 変形バケットソートとオイラリアン分布 (2008) 第13回情報・統計科学シンポジウム, 九州大学

[論文発表]
(1) ある種の並べ替え算法のおける分布について (2007) 土屋高宏, 中村永友, 札幌学院大学商経論集, 第24巻, 第2号, 31-47.
(2) 変形バケットソートに現れる離散型確率分布とEulerian数 (2009) 土屋高宏, 中村永友, 統計数理, Vol.57, No. 1, 159-178.
(3) Eulerian numbers and discrete distribution in modified bucket sort. (2012) 土屋高宏, 中村永友, 投稿準備中.

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

研究会は開催していないが，共同研究者との研究打合せを，2月に統計数理研究所で4日間実施した．

 

研究参加者一覧

氏名

所属機関

川崎 能典

統計数理研究所

中村 永友

札幌学院大学