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

課題番号	21−共研−2056		分野分類			統計数理研究所内分野分類			g
						主要研究分野分類			2
研究課題名	Eulerian Numbersと離散型確率分布モデル
フリガナ 代表者氏名	ツチヤ　タカヒロ 土屋　高宏				ローマ字		Tsuchiya Takahiro
所属機関	城西大学
所属部局	理学部数学科
職　　名	准教授
配分経費	研究費	0千円		旅　費		0千円		研究参加者数		3　人

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

研究目的
本研究は，バケットソートと呼ばれる計算時間がO(n)で高速に行える並べ替え（整列，ソーティング）技法を扱う．これは並べ替えをしたいデータの取りうる値がn通りあるとき，あらかじめn個のバケツを用意しておき，あるいは動的にバケツを増やしていきながら，各々の数字と対応するバケツにデータを入れていくアルゴリズムである．本研究の目的はn個の連続した数字があり，あらかじめ用意するバケツ数が決められておらず，その数がデータの初期状態に依存する変形バケットソートを考え，そのバケツ数（束の数）の離散型確率分布モデルとその周辺について研究を遂行することである．

成果および経過
(1) これまでの研究では確率分布導出のための漸化式を，Eulerian数と呼ばれる数列から代数的に証明したが，組合せ論を利用した漸化式の直接証明が可能かどうか引き続き検討中である．
(2) 確率分布の近似とその精密化を行う際に，高次のキュムラントを必要とする．この確率分布は(0, 1)上の一様分布に従う n + 1 個の互いに独立で同一な確率変数の和のキュムラントと酷似していることが分かっている．このことを利用してキュムラントの一般項の導出を試みている．
(3) カードの番号が1からnの異なる数の並べ替えを基礎として，さらに番号が欠落している場合の束の数の確率分布について考究している．
(4) これまでの研究成果を英文雑誌に投稿準備中である．

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

?．学会・シンポジウム発表
(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) 土屋高宏, 中村永友, 統計数理, 第57巻, 第1号, 159-178.

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

研究参加者一覧
氏名	所属機関
川崎　能典	統計数理研究所
中村　永友	札幌学院大学