tailinequality (1) 썸네일형 리스트형 체르노프 부등식 (Chernoff Bounds) 여러분의 눈 앞에 총 \(n\)개의 서로 다른 상자가 놓여 있다고 합시다. 각 상자 안에는 흰 공과 검은 공으로만 차 있습니다. 여러분은 각 상자의 흰 공과 검은 공의 비율이 얼마나 되는지 모두 알고 있습니다. 즉, \(i\) 번째 상자에는 \( p_i \)의 비율로 흰 공이 있다고 해 보겠습니다. 여러분이 상자에서 각각 공을 하나씩 뽑는다면 과연 흰 공은 몇 개를 뽑게 될까요? 그 기댓값은 구하기 쉽습니다. 바로 기댓값의 선형성(linearity of expectation)에 의해 \( \sum_{i = 1}^n p_i \) 개가 될 것입니다. 그렇다면 실제로 공을 뽑았을 때, 과연 흰 공의 개수가 기댓값 혹은 기댓값 부근의 값이 될 확률은 얼마나 될까요? 이는 신뢰의 문제입니다. 만약 그 값이 들쭉날.. 이전 1 다음
