Sublinear algorithmに多用されるChernoff boundはランダマイズド・アルゴリズムを用いて確率的にデータマイニングアウトプットをしたときの、そのアウトプットの確度を教えてくれる不等式 それに関する文書はいろいろみつかるけれど、わかりにくかったので…

Markov 不等式 ある確率変数Xの値がt以上になる確率は、Xの期待値をtで割った値以下である # 取りうる値の種類数 n.val <- 10 # 正の確率変数値 v <- sort(runif(n.val)) library(MCMCpack) # 値別の生起確率 p <- rdirichlet(1,rep(1,n.val)) # 期待値 Ex <…