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

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

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

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

成果（経過）
(1) 束の数の確率分布を漸化式の形で導出するとともに、確率分布導出の際に現れる漸化式がEulerian数と呼ばれる数列を構成することを示した．現在、漸化式の直接証明に取り組んでいる．
(2) 確率分布の導出過程においてEulerian数との間に微妙な差異があることを示した．
(3) 確率分布についてモーメントなどの基本統計量を求め，正規分布との比較，確率分布近似の精密化を行った．さらに，求めた確率分布と連続型一様分布との関係について言及した．
(4) 確率分布の近似とその精密化を行う際に，高次のキュムラントを必要とする．この確率分布は(0, 1)上の一様分布に従う n + 1 個の互いに独立で同一な確率変数の和のキュムラントと酷似していることが分かり，このことを利用してキュムラントの一般項の導出を試みている．

当該研究に関するこれまでの成果は以下の学会・シンポジウムで発表するとともに，論文としてまとめた．

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

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

II．論文発表
(1) ある種の並べ替え算法のおける分布について (2007) 土屋高宏, 中村永友, 札幌学院大学商経論集, 第24巻, 第2号, 31-47.
(2) 変形バケットソートに現れる離散型確率分布とEulerian数 (2009) 土屋高宏, 中村永友, 統計数理, 第57巻, 第1号, 掲載.

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

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