ソーティング過程に現れる離散確率分布とその精密化

ソーティング過程に現れる離散確率分布とその精密化
城西大学理学部
札幌学院大学経済学部
土屋高宏
中村永友
1. 概要バケットソートを変形したソーティング過程に現れる離散確率分布を導出する．バケッ
トソートは並べ替えるデータの取りうる値が k 通りのとき，あらかじめ k 個の入れ物を用意する
か，あるいは動的にそれを増やしながら，各々の数字に対応した入れ物にデータを入れていくア
ルゴリズムである．土屋・中村 (2008) は，n 個の連続した数字（カード）があり，あらかじめ用
意する入れ物数を決めず，最終的に必要な入れ物数がデータの初期状態に依存する変形バケット
ソートを考案し，その入れ物数を表す漸化式と離散確率分布（Eulerian 分布）を導出した．
本報告では，変形バケットソートを一般に拡張したときの理論について考察する．特に連番のう
ち番号が欠落している場合の入れ物数の離散確率分布（欠番のある Eulerian 分布）を導出し，こ
の確率分布の性質について考察する．
2. 問題設定 1 から n までの数字が書かれたよくシャッフルされている n 枚のカードが手元にあ
る．カードを小さい順に並べ替えをするために，次の手順で行う．(1) 一番上のカードの数字が k
のとき，数字 k ＋ 1 のカードがすでにテーブルに置かれていたらその上にカード k を載せる．(2)
もしテーブル上に k ＋ 1 が無ければ，どのカードの上にも載せず，テーブルにカード k を置く．(3)
(1) と (2) を手元のカードが無くなるまで続ける．(4) テーブルの上に m 個のカードの束ができる
(1 · m · n)．(5) 各束の一番上のカードの数字を小さい順にまとめれば，並べ替えが完了する．
このとき，カードをテーブルに置き終わった時点におけるカードの束の数に関する確率分布がど
のようなものになるのかを議論する．
「束の数」はバケットソートにおける入れ物数に対応する．
3. 束の数の確率分布 n 枚のカードにおける束の数が i になる総数 Mn (i) について，次の漸化式
が成り立つ．
Mn (1) = Mn (n) = 1
(n ¸ 1);
Mn (i) = iMn¡1 (i) + fn ¡ (i ¡ 1)gMn¡1 (i ¡ 1)
(n ¸ 3; i = 2; ¢ ¢ ¢ ; n ¡ 1):
この漸化式は Eulerian 数を求める式と数学的に同値であり，束の数と Eulerian 数 A(n; i ¡ 1) の
間に Mn (i) = A(n; i ¡ 1) (i = 1; 2; ¢ ¢ ¢ ; n) が成り立つ．n 枚のカードが i 束になる確率 Pn (i) は，
Pn (i) = Mn (i)=n! で定義される．
4. 欠番のある Eulerian 分布前述のソーティング過程を一般に拡張し，欠番がある場合の離散
確率分布について考察する．1 から n までの数字が書かれた n 枚のカードのうち欠番がある状況
を考える．どの番号も等確率で欠番が生じるという仮定の下で，束の数の確率分布を導出する．1
枚だけ欠番があるとき，n 枚のカードにおける束の数が i になる総数 Mn¤ (i) について，次の漸化
式が成り立つ．
Mn¤ (1) = 2 (n ¸ 2);
Mn¤ (n) = 0 (n ¸ 1);
Mn¤ (i) = Mn (i) + Mn¡1 (i) ¡ Mn¡1 (i ¡ 1)
(n ¸ 3; i = 2; ¢ ¢ ¢ ; n ¡ 1):
ただし，Mn (i) は欠番がない場合の束の数を表す．n 枚のカードが i 束になる確率 Pn¤ (i) は，Pn¤ (i) =
Mn¤ (i)=n! で定義される．
参考文献
土屋高宏，中村永友 (2009). 変形バケットソートに現れる離散型確率分布と Eulerian 数, 統計
数理 57(1), 159-178.

Download Report