Learning Sums of Independent Integer Random Variables - todo314 @ ウィキ

Learning Sums of Independent Integer Random Variables

• In FOCS 2013

• 「離散」変数に対する中心極限定理のようなもの
• S = Σi X_i
  • X_i∈{0,…k-1}
  • 各X_iは独立かつiid性が「無い」
    • それぞれ分布が違う
  • 何個Sからドローすれば良い？
• k=2の時
  • 簡単らしい、正規分布で近似
• k=3の時
  • 偶奇性が出る、やべえ
  • ランダムなのに周期性が出る
• 結果
  • (i)構造定理
  • S \approx c*離散正規分布 + {1,…c}値をとる確率変数
    • c∈{0,…,k-1}
  • (ii)学習定理
  • poly(k,1/ε)個ドロー！！
  • X_iの値域を分割
    • 1つの確率変数
    • gcdして正規分布で近似
  • ちゃんとアルゴリズムしてる

FOCS

2013-11-03 02:10:16 (Sun)