極限・関数の大小比較とランダウの記法(駆け足で読む統計学のための数学入門30講 4)

• 第４講　極限

関数ははにてある値に収束する、もしくは、に発散するとき、次のように書く

• ポアソン分布は２項分布の生起確率Pをゼロに限りなく近づけたものに相当している
  
  • ２項分布は、ある事象が起きる確率Pと起きない確率1-Pであるときに、総計N回の観測で、k回起きる確率を与える分布である
    
    • 
    • この式では、N回試行してk回起きる確率が求められている。言い換えると試行回数を指定して、起きる回数も指定することでその確率が求められている
  • ポアソン分布は２項分布の極限
    
    • 今、Pが非常に小さい事象を考える。非常に小さいのでこれくらい(たとえば１万回に１回くらい)なことはわかっているが、実際に何回試行するかは未定だとする。そのような場合にも、極限をとることで、事象がk回起きる確率が計算できる。それは、生起確率が非常に小さいので、実際にN回試行するとしようとN'回試行すると仮定しようと、回試行すると仮定した場合とみなせるような状況だから、である(多分。）
    • 実際に２項分布の極限をとってみる
      
      • 非常に小さい生起確率とすると、n回の試行においてk回起きる確率は
        
        • 
        • 今、とするとと式変形できて、これは、k回起きる確率が(１万回に１回くらい稀な事象、というときのとkのみによって決まることがわかる
• アルゴリズムA1とアルゴリズムA2とがあって、いずれも、入力データサイズが大きくなれば大きくなるほど計算量は増える。したがって、いずれのアルゴリズムの計算量も発散する。しかしながら、アルゴリズムの計算量は、その発散の速さの多寡で比較する。そのときに用いるのが、ランダウの表記である
  
  • 今、ある関数とがにおいてともにに発散するとする。そうは言っても、その発散の速度には違いが存在しえて、(1)の場合と、(2),Cは定数の場合と、(3)それよりも大(xに関する増大関数)の場合とである。(1)の場合、はより高位の無限大(より速く発散する)ことを示し、(2)の場合、はと同位の無限大(同じくらいの速度で発散する)ことが示されている。(3)の場合にははより高位の無限大(より速く発散する)ことが示されている。(1)のとき、と書いて、はのスモールオーダーになっていると言う。(2)の場合には、と書いて、ラージオーダーになっていると言う。(2)のようなとき、の計算量はたかだかのそれであることが示される。アルゴリズムAの計算量はである、などと用いる