補遺 確率変数の不等式

• Markov 不等式
  • 
  • ある確率変数Xの値がt以上になる確率は、Xの期待値をtで割った値以下である

# 取りうる値の種類数
n.val <- 10
# 正の確率変数値
v <- sort(runif(n.val))
library(MCMCpack)
# 値別の生起確率
p <- rdirichlet(1,rep(1,n.val))
# 期待値
Ex <- sum(v*p)
Ex
# 確率変数が値t[i]以上になる確率は？
ts <- seq(from=min(v),to=max(v),length=100)
# Markov 不等式が示す上限
PrMarkov <- Ex/ts
plot(ts,PrMarkov,ylim=c(0,max(PrMarkov)))
# 確率ベクトルから算出される値(赤線)がMarkov 不等式上限の下にある
PrMarkov.true <- rep(0,length(ts))
for(i in 1:length(ts)){
	tmp <- which(v >= ts[i])
	PrMarkov.true[i] <- sum(p[tmp])
}
points(ts,PrMarkov.true,col=2,type="l")

• Chebychev 不等式
  • 
  • 確率変数Xがその期待値Ex(X)からt以上離れている確率は、Xの分散をtの二乗で割った値以下である

Vx <- sum(p*(v-Ex)^2)

PrChebyshev <- Vx/ts^2
plot(ts,PrChebyshev,ylim=c(0,max(PrChebyshev)))

PrCheb.true <- rep(0,length(ts))
for(i in 1:length(ts)){
	tmp <- which(abs(v-Ex) >= ts[i])
	PrCheb.true[i] <- sum(p[tmp])
}
points(ts,PrCheb.true,col=2,type="l")

• • 独立試行を繰り返して、その和についてChebyshev 不等式をあてはめると、(複数の確率変数の値の平均値の分散は、独立試行の回数の二乗で小さくなっていくので、それによって上限が抑えられるため)、(値が小さい範囲でも)ぐっと抑えられてくる
  • 
  • n回繰り返すとその平均は、単独の時より期待値Ex(X)に近づいていくので、平均が期待値からt以上離れる確率はnにつれて小さくなる。その小さくなり方が、確率変数Xの分散をnで割ったものをtの二乗で割ったもの以下になる

# k回繰り返し
ks <- 2^(0:10)
ts <- ts
PrChebyshevReps <- matrix(0,length(ts),length(ks))
for(i in 1:length(ks)){
	Vxk <- Vx/ks[i]
	PrChebyshevReps[,i] <- Vxk/ts^2
}
matplot(PrChebyshevReps,type="l")

• Chernoff bound
  • 
  • n回繰り返して、その平均が期待値からt以上離れる確率は、指数にnとtの二乗の積を3と期待値とXの最大値の積で割ったものの負の数を取ったもの以下になる
  • Chebyshev 不等式より、nが大きくなると急速に上限が低くなる特徴がある

max.v <- max(v)
PrChernoff <- 2*exp(-Ex*1*(ts/Ex)^2/(3*max.v))
matplot(cbind(PrChebyshev,PrChernoff),type="l")
PrChernoffReps <- matrix(0,length(ts),length(ks))
for(i in 1:length(ks)){
	Vxk <- Vx/ks[i]
	PrChernoffReps[,i] <- 2*exp(-(Ex*ks[i]*(ts/Ex)^2)/(3*max.v))
}
matplot(PrChernoffReps,type="l")
matplot(cbind(PrChebyshevReps[,1],PrChernoffReps[,1]),type="l")
matplot(cbind(PrChebyshevReps[,8],PrChernoffReps[,8]),type="l")