昭和60（1985）年度　共同研究実施報告書

課題番号	60−共研−1			専門分類		1
研究課題名	２進探索木の確率模型
フリガナ 代表者氏名	イトウ　ヨシアキ 伊藤　栄明			ローマ字
所属機関	統計数理研究所
所属部局	領域統計研究系
職　　名	教授
所在地
TEL				FAX
E-mail
URL
配分経費	研究費	0千円	旅　費		0千円		研究参加者数	3　人

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

２進探索木，クィックソート等の計算技法における確率模型を研究する。特に１次元ランダム・パッキング，２進順序確率木，確率逐次２分割の統計量について確率論的研究および数値計算を行う。


停止規則のある確率逐次２分割を提案し，対応する確率２進木を考えた。区間の長さｘを根のラベルとし，分割ごとに小区間の長さを左右の部分木の根のラベルとする。この無限２進木で１以上のラベルをもつ節点だけ残して，他を消せば有限の２進木が得られ，その末端節点の子供たち（外部節点と呼ぶ）が，１未満の区間に対応する節点とする。この確率２進木は点より出発して定速度で成長する区間が，長さ１になれば２分裂し，その後も全区間が定速度で成長しては２分裂するモデル，とも同等であり，ｑｕｉｃｋｓｏｒｔや２進探索木で現われる確率２進木の連続版である。得られた区間の長さの最大値は木の高さに対応させることができ，この確率分布についての漸近的な評価を与えた。この問題より数学的に興味ある関数方程式が得られ，それについて数値的，及び解析的な研究を行った。

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

渋谷政昭，伊藤栄明
Ｒａｎｄｏｍ ｓｅｑｕｅｎｔｉａｌ ｂｉｓｅｃｔｉｏｎ ａｎｄ ｉｔｓ ａｓｓｏｃｉａｔｅｄ ｂｉｎａｒｙ ｔｒｅｅ
Ａｎｎ．Ｉｎｓｔ．Ｓｔａｔｉｓｔ．Ｍａｔｈ．Ａ 投稿中
確率逐次２分割
日本数学会 １９８５年１０月
停止規則のある確率逐次２分割
日本数学会 １９８５年４月

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

統計数理研究所では，内外研究者の協力を得て従来からランダム・パッキングに関連する凾数方程式の研究を行っている。その成果を活かし，計算アルゴリズムに関連する確率模型の研究を行う。数値計算のために必要な計算プログラム作成の補助の謝金，文献収集，論文タイプ等が経費である。

研究参加者一覧
氏名	所属機関
渋谷　政昭	高千穂商科大学
住田　潮	国際大学