イントロダクション：ぱらぱらめくるCrash course "Sublinear Algorithms for Big Datasets"

• イントロダクションのPDF
• Big dataを使う例
  • (1,2,...,n+1)の値のカードがあるときに、バラバラな順番にn枚のカードを見たとする。出ていないカードの値を当てるには、n+1個の値の出た・出ないを全部覚えておく必要はない(覚えておいても良い)。それまでに出た数の和だけ覚えておけば(常に１つの値だけ覚えておけば)、最後に1+2+...+(n+1)からその値を引いてやれば、出ていない数はわかる。「値が出てくるというストリーム」に乗って、メモリとしては、数値１個分の使用のみで、目的が達成できる
  • 全部の出た・出ないを記録して答えるという重さと、数値１個分を覚えるだけの軽さとを比較して、軽いのがsublinearさ加減
• どんなことが問題になるか
  • 確率
    • 出てくるカードがランダムに出てくるなら、ランダムでないなら、などが気になるので、確率に関する理解が必要
    • 付随して、確率に関する基礎的なこと、独立、条件付き独立、その生起確率の期待値、非独立な事象に関する不等式
  • 基本統計量
    • 単純な統計量(平均(期待値)、分散)とか。これらは数値列をかいつまんでいるので、「k個の値が出たのに、1個の数値だけにして取っておく」というときに、とっておくべき値になる
    • 期待値は線形和が使える(非独立な事象でも)。分散は、独立なら線形和が使える
  • 不等式
    • 全部のデータを使わないで推定するのだから、このくらいの範囲で大丈夫、と言わなくてはならない
    • そこに使うのが、確率の世界の不等式
    • Markov 不等式
      • 確率変数の累積分布について期待値を使ってどのくらいなのかの情報をくれる
    • Chebychev 不等式
      • 確率変数の期待値からのずれについて、ある範囲にどれくらいの確率で入るかの情報を、期待値と期待値からのずれの絶対値とを使って教えてくれる
    • Chernoff bound
      • Chebychevが確率変数の取る値に関するものであるのに対して、Chernoff boundはある範囲の値を取る確率変数を複数回観測したときのその平均に関して、それが確率変数の期待値からどれくらいずれるかについて教えてくれる