ビンとボールのゲームにおける2ビン選択モデルの一般化
スポンサーリンク
概要
- 論文の詳細を見る
n本のビンとn個のボールに対して,各ボールが一様ランダムに1本のビンを選んでそのビンに入れられる,という試行はビンとボールのゲームと呼ばれ,確率論の基本的な問題として古くから議論されてきた.特にn個のボールを割り振った後の一つのビンに入っているボールの最大値(ビンの最大高さ)は確率1-o(1)でおよそln n/ ln ln n であるという事実は良く知られている.このゲームに関して, Azarらは各ボールが一様ランダムに二つのビンを選び,入っているボールの数が少ない方にボールを入れるという2ビン選択モデル(two-choice model)を許した場合にビンの最大高さは確率1-o(1)でおよそln ln nになるということを証明した.本稿では2ビン選択モデルを一般化し,そのモデルに対する解析を行う.我々のモデルではゲーム開始前にr個の閾値T_1,…,T_r を用意しておく.また各ボールは2ビンを一様ランダムに選び,ボールの個数をビンに問い合わせるが,問い合わされたビンは現在入っているボールの個数がT_k以上T_<k+1>未満であることしか教えない.このモデルにおいて,r⪇ln ln n/6 のとき,ビンの最大高さは確率1-o(1)でせいぜいO(r^<r+1>√<ln n/ln ln n>)である事を証明する.またこの最大高さを達成するための閾値の設定の最適性についても議論する.
- 社団法人電子情報通信学会の論文
- 2003-09-18
著者
-
河内 亮周
京都大学情報学研究科
-
岩間 一雄
今井量子計算機構プロジェクト(ERATO)
-
岩間 一雄
科学技術振興事業団創造科学推進事業今井量子計算機構プロジェクト
-
河内 亮周
Department of Mathematical and Computing Sciences, Tokyo Institute of Technology
-
河内 亮周
Department Of Mathematical And Computing Sciences Tokyo Institute Of Technology
-
Iwama Kazuo
Kyoto University:japan Science And Technology Corporation
関連論文
- 片方のみがタイを持つ安定結婚問題に対する25/17近似アルゴリズム (アルゴリズムと計算機科学の数理的基盤とその応用)
- Designing Quantum Game Strategies from Quantum Communication Protocols
- 計算量理論における乱数(学生/教養のページ)
- DS-1-14 飛び道具を考慮した逆算法に基づく詰将棋列挙技術(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- 部の大きさの比が高々定数倍の孤立2部クリークの列挙
- 遺伝的な距離に基づいた家系図推定問題
- 単調論理回路における還元
- 逆算法に基づく詰将棋の列挙
- 量子計算における整数格子問題へのアプローチ(量子情報処理論文)
- NP困難問題における最悪時困難性からの平均時困難性証明への試み
- 頑健な量子状態復号とルジャンドル列の疑似乱数性
- An improvement of the soundness of a 3-bit PCP (理論計算機科学の深化と応用--RIMS研究集会報告集)
- D-1-5 量子有限オートマトンの類似性判定アルゴリズム(D-1. コンピュテーション)
- (4, 1)-量子ランダムアクセス符号の非存在について
- 量子ネットワーク上での効率的な情報の伝送(計算理論とアルゴリズムの新展開)
- 3正則グラフの巡回セールスマン問題に対する厳密アルゴリズムの改善(計算機科学の理論とその応用)
- 男女平等安定マッチング問題に対する近似アルゴリズム
- オンライン問題の競合比解析の自動化について
- General Bounds for Quantum Biased Oracles (特集:量子計算と量子情報)
- Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications)
- Transmitting classical information on the quantum network efficiently
- オラクル同定問題に対する頑健な量子アルゴリズム
- オンライン問題の競合比解析の自動化について (計算機科学基礎理論の新展開)
- Approximating Vertex Cover on Dense Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- ビンとボールのゲームにおける2ビン選択モデルの一般化
- Noise-Tolerant Quantum Oracles (New Aspects of Theoretical Computer Science)
- 探索問題における一般的な量子オラクルの質問回数について
- A-1 3関数に対する量子クロー探索アルゴリズム(計算量・量子計算,A.アルゴリズム・基礎)
- 量子コンピュータ科学入門(量子情報科学 : 新しい情報処理のパラダイム)
- D-1-8 Mathematicaと並列計算機を併用した量子計算のシミュレーション
- 占有問題に対する量子アルゴリズム
- ブール関数を計算する量子回路の局所変換ルールの完全集合
- 伸長係数2のコンパクトラウティングアルゴリズム (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 量子探索と量子ゲーム(知能コンピューティングとその周辺〔第12回〕)
- A Lattice-Based Cryptosystem and Proof of Knowledge on Its Secret Key(Theory of Computer Science and Its Applications)
- Multi-Bit Cryptosystems based on Lattice Problems : Extended Abstract(New Trends in Theory of Computation and Algorithm)
- 配属人数下限付き研修医配属問題 (理論計算機科学の深化と応用)
- 3人部屋安定ルームメイト問題のNP完全性
- 平面グラフにおけるHajos Calculusの複雑さについて
- Negation-Limited Complexity of Parity and Inverters(Theory of Computer Science and Its Applications)
- DS-1-3 安定結婚問題に対する1.8-近似アルゴリズム(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 安定結婚問題に対する1.875-近似アルゴリズム
- 計算限界の最前線(新世代の計算限界-その解明と打破-招待解説論文)
- 二段組合せ回路の最大動作率について(計算理論とアルゴリズムの新展開)
- PPSZタイプの充足可能性判定アルゴリズムの成功確率増幅について
- 入札額の範囲が制限された正直なオークション
- Hajos Calculus on Planar Graphs (Theoretical Computer Science and its Applications)
- Geometric Characterization of Quantum Oracle Identification(New Trends in Theory of Computation and Algorithm)
- 任意の量子一方向性関数に対するハードコア述語の一般的構成法
- 局所探索法による安定結婚問題の近似
- Quantum Biased Oracles (特集:量子計算と量子情報)
- 正直なオークションにおける談合の影響 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 安定結婚問題に対する局所探索近似アルゴリズムの改良
- 定数ラウンドで復元可能な合理的秘密分散
- 計算論的安全性に基づく量子暗号
- 任意の量子一方向性関数に対するハードコア述語の一般的構成法
- 素体上多項式に対する計算困難な関数
- Gowers一様性による剰余関数と多項式の相関の評価 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- Quantum Sampling for Balanced Allocations(Foundations of Computer Science)
- Max-Stretch Reduction for Tree Spanners
- タイル縁に上書きルールを用いた敷き詰め問題
- タイル縁に上書きルールを用いた敷き詰め問題
- 効率の良い罫線描画について
- Quantum asymmetric-key cryptosystems secure against computationally unbounded adversaries (計算機科学の理論とその応用 RIMS研究集会報告集)
- Complexity-Theoretical Quantum List Decoding and Applications to Quamtum Hardcore Functions (計算理論とアルゴリズムの新展開 RIMS研究集会報告集)
- Rational Secret Sharing for Non-Simultaneous Channels (情報理論)
- 量子探索と量子ゲーム
- リスト復号の質問計算量
- 非同時通信路における合理的秘密分散(情報セキュリティ)
- NP-解探索における質問計算量について
- A Fourier analytic approach to list-decoding for sparse random linear codes (New Trends in Theoretical Computer Science)
- Query Complexity of Witness Finding (コンピュテーション)
- NP-解探索における質問計算量について(一般)
- 計算複雑さへの招待(2) : アルゴリズムから攻める計算複雑さの下界証明(【特別企画】「計算限界解明」チュートリアル講演第2回)
- Quantum-Advised Algorithms for Biased Oracles (コンピュテーション)