확률 부등식(마르코프·체비쇼프·체르노프) 계산기

X가 음수가 아니면 P(X ≥ a) ≤ E[X]/a라는 부등식입니다. 평균 하나만 알면 쓸 수 있는 대신 상한이 매우 헐겁습니다. 「평균이 100인데 1000 넘는 일이 10%보다 자주 일어날 수는 없다」는 뜻이며, 자주 일어난다면 그것만으로 평균이 100을 넘어 버리기 때문입니다.

k가 1 이하일 때입니다. 상한 1/k²이 1 이상이 되어 「확률이 100% 이하」라는 참이지만 공허한 말이 됩니다. k = 0.5를 넣으면 상한이 4, 곧 400%로 나오는데 이는 오류가 아니라 그 정도 범위에서는 아무 말도 할 수 없다는 뜻입니다.

분포가 대칭일 때만 옳고 일반적으로는 틀립니다. 한쪽 꼬리에는 칸텔리 부등식 P(X − μ ≥ kσ) ≤ 1/(1+k²)를 써야 하며, 이쪽이 1/2k²보다도 죕니다. k = 2에서 체비쇼프는 25%, 반으로 나누면 12.5%인데 칸텔리는 20%로 더 큽니다 — 반으로 나눈 값이 오히려 참이 아닐 수 있다는 뜻입니다.

독립인 확률변수의 합이라는 정보를 더 쓰기 때문입니다. 체비쇼프는 분산만 보아 n에 반비례해서만 좋아지지만, 체르노프·회프딩은 n에 지수적으로 좋아집니다. 표본이 1000개쯤 되면 두 상한이 몇십 자릿수까지 벌어집니다. 대신 「독립이고 유계」라는 조건이 필요합니다.

대개 체르노프가 죄지만 언제나 그렇지는 않습니다. 회프딩 exp(−2nε²)은 절대적인 초과분 ε만 보고, 체르노프는 평균 대비 비율 δ를 보기 때문에 p가 작고 꼬리가 먼 경우 체르노프가 크게 이깁니다. 반대로 δ가 작을 때는 회프딩이 나을 수 있어, 이 도구는 둘을 함께 냅니다.

상한이 아니라 근사이기 때문입니다. 부등식들은 실제 확률보다 반드시 크거나 같지만, 정규 근사는 실제보다 작게 나올 수 있습니다. 특히 p가 작고 문턱값이 평균에서 먼 이항분포에서 과소평가하는 일이 흔합니다. 안전 여유를 잡는 계산에서 이 둘을 섞어 쓰면 안 됩니다.

분포를 모를 때 말할 수 있는 유일한 것이라는 데 쓸모가 있습니다. 실제 분포를 알면 훨씬 정확한 값을 낼 수 있지만, 실무에서는 평균과 분산 정도만 아는 경우가 많습니다. 또 알고리즘 분석에서는 「어떤 입력에도 이보다 나쁘지 않다」는 보장이 필요해 정확한 값보다 상한이 쓸모 있습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.