132강부터 134강까지 분포를 몇 개의 수로 요약했습니다. 요약은 정보를 버리는 일입니다.
그렇다면 남은 정보로 무엇을 말할 수 있습니까.
분포를 모르고 평균만 안다고 합시다. 이 확률변수가 평균의 열 배를 넘을 확률에 대해 무엇을 말할 수 있습니까. 아무것도 못 할 것 같지만 그렇지 않습니다.
분포가 무엇이든 성립합니다. 비음이라는 조건 하나만 필요합니다.
그리고 정보를 더 쓸수록 상한이 날카로워집니다.
| 아는 것 | 부등식 | 상한의 감소 |
|---|---|---|
| 평균 | 마르코프 | |
| 평균과 분산 | 체비쇼프 | 1/a^ |
| 적률생성함수 | 체르노프 | e^ |
이 계층이 이 강의의 뼈대이며, 134강 심화 2에서 셋째 줄을 미리 유도했습니다.
그리고 이 부등식들에서 큰 수의 법칙이 두 줄로 나옵니다. 142강의 정리를 여기서 미리 증명할 수 있으며, 그것이 03단원이 05단원으로 이어지는 다리입니다.
문제. 비음 확률변수 의 평균만 안다고 합니다.
(1) 지수분포에서 와 를 비교하세요.
(2) 균등분포에서도 비교하세요.
(3) 상한이 느슨한 이유와 그럼에도 쓰는 이유를 쓰세요.
생각의 실마리. 가 비음이므로 큰 값을 자주 가지면 평균이 커집니다. 평균이 정해져 있으면 큰 값을 자주 가질 수 없습니다.
풀이. (1)(2) 검산 결과입니다.
| 분포 | 실제 | 상한 | 상한실제 | ||
|---|---|---|---|---|---|
| 지수 | |||||
| 지수 | |||||
| 지수 | |||||
| 지수 | |||||
| 균등 | |||||
| 균등 | |||||
| 균등 |
가 커질수록 상한이 점점 느슨해집니다. 지수분포 에서 배 차이입니다.
(3) 상한은 로만 줄어드는데 지수분포의 꼬리는 로 줄기 때문입니다. 대신 분포를 전혀 몰라도 됩니다.
이 문제에서 배우는 것: 마르코프 부등식.
마르코프 부등식. 이고 이면
증명이 한 줄입니다. 지시함수를 씁니다.
이면 오른쪽이 이고 는 그 이상이며, 아니면 오른쪽이 이고 는 비음이라 언제나 성립합니다. 양변의 기댓값을 취하면
이고 로 나누면 끝입니다. 127강의 지시함수와 132강의 선형성만 썼습니다.
비음 조건이 필수입니다. 가 음수를 가지면 큰 음수가 평균을 낮춰 논증이 무너집니다.
음수를 갖는 경우에는 나 처럼 비음인 것에 적용하며, 문제 2가 정확히 그 방법입니다.
느슨함이 결함이 아닙니다. 이 부등식은 분포에 대해 아무것도 모르는 상황을 위한 것이며, 문제 3에서 등호가 실제로 달성됨을 봅니다.
실무에서 쓰이는 자리가 있습니다.
| 상황 | 어떻게 쓰는가 |
|---|---|
| 최악의 경우 보장 | 분포를 모를 때 상한을 약속합니다 |
| 다른 부등식의 재료 | 체비쇼프와 체르노프의 출발점입니다 |
| 알고리즘 분석 | 기대 실행시간에서 꼬리 확률로 |
| 자원 계획 | 평균 부하로 초과 확률의 상한을 |
둘째 줄이 가장 중요합니다. 이 강의의 나머지 전부가 마르코프 부등식을 어떤 비음 함수에 적용하느냐의 문제입니다.
바로 확인 1.
확인 1-1. 마르코프 부등식과 그 조건을 쓰세요.
답. 이며 이어야 합니다.
확인 1-2. 증명의 핵심 부등식을 쓰세요.
답. 이며 양변의 기댓값을 취합니다.
확인 1-3. 상한이 에 대해 어떻게 줄어드는지 쓰세요.
답. 로만 줄어듭니다.
문제. 평균과 분산을 아는 상황을 봅니다.
(1) 의 상한을 유도하세요.
(2) 세 분포에서 실제 확률과 비교하세요.
(3) 상한이 언제 쓸모 있는지 쓰세요.
생각의 실마리. 는 음수가 될 수 있어 마르코프를 바로 쓸 수 없습니다. 제곱하면 비음이 됩니다.
풀이. (1) 에 마르코프를 적용합니다.
마지막 등호가 분산의 정의입니다.
(2) 검산 결과입니다.
| 상한 | 정규분포 실제 | 지수분포 실제 | 균등분포 실제 | |
|---|---|---|---|---|
에서 상한이 이라 아무 정보가 없습니다.
정규분포 에서 상한 인데 실제는 으로 배 차이입니다.
**균등분포는 에서 정확히 **입니다. 유계이므로 평균에서 넘게 떨어질 수 없습니다.
(3) 가 클 때만 쓸모가 있습니다.
이 문제에서 배우는 것: 체비쇼프 부등식.
체비쇼프 부등식. 이면
두 형태가 같은 식이며 로 바꾼 것입니다.
130강 문제 3의 표와 나란히 보면 대비가 선명합니다.
| 체비쇼프(분포 무관) | 정규분포에서 실제 | |
|---|---|---|
가 커질수록 차이가 벌어집니다. 정규분포의 꼬리는 로 줄고 체비쇼프는 로만 줄기 때문입니다.
그래도 체비쇼프를 쓰는 이유는 분포를 몰라도 되기 때문입니다. 정규성을 가정할 수 없을 때 유일하게 쓸 수 있는 보장입니다.
흔한 오해를 짚습니다. " 안에 가 있다"는 것은 정규분포에서만 참입니다. 일반적으로는 체비쇼프의 만 보장되며, 꼬리가 두꺼운 자료에서 규칙을 쓰면 극단값의 빈도를 크게 과소평가합니다.
한쪽 꼬리에는 더 나은 형태가 있습니다.
칸텔리 부등식. 에 대해
체비쇼프를 절반으로 나눈 것보다 낫습니다. 문제 4의 표에서 두 값을 나란히 봅니다.
바로 확인 2.
확인 2-1. 체비쇼프 부등식을 두 형태로 쓰세요.
답. 이고 입니다.
확인 2-2. 유도의 핵심을 쓰세요.
답. 에 마르코프 부등식을 적용합니다.
확인 2-3. " 안에 "가 일반적으로 참입니까?
답. 아닙니다. 정규분포에서만이며 일반적으로는 만 보장됩니다.
문제. 등호가 성립하는 분포를 찾습니다.
(1) 마르코프의 등호 분포를 구성하세요.
(2) 체비쇼프의 등호 분포를 구성하세요.
(3) 결론을 쓰세요.
생각의 실마리. 증명에서 를 썼습니다. 등호가 되려면 가 아니면 여야 합니다.
풀이. (1) , 인 두 점 분포입니다.
| 상한 | 차이 | ||||
|---|---|---|---|---|---|
차이가 정확히 입니다.
(2) 체비쇼프는 세 점 분포에서 등호가 됩니다. 이고 입니다.
| 1/k^ | 평균 | 분산 | 차이 | ||
|---|---|---|---|---|---|
평균이 이고 분산이 정확히 이면서 등호가 성립합니다.
(3) 분포를 모른다는 조건에서는 더 줄일 수 없습니다.
이 문제에서 배우는 것: 최선의 상한.
날카로움. 마르코프와 체비쇼프는 주어진 정보만으로는 개선할 수 없는 최선의 상한입니다.
"느슨하다"와 "나쁘다"는 다릅니다. 특정 분포에서 느슨한 것은 그 분포에 대한 추가 정보를 쓰지 않았기 때문이며, 부등식의 결함이 아닙니다.
이 구조가 반복해서 나타납니다.
| 상황 | 최악의 경우 |
|---|---|
| 마르코프 | 두 점 분포 |
| 체비쇼프 | 세 점 분포 |
| 부울 부등식(122강) | 서로 배반인 사건들 |
| 코시슈바르츠(63강) | 평행한 벡터 |
모든 부등식에 "언제 등호인가"라는 질문이 따라붙으며, 그 답이 부등식의 성격을 말해 줍니다.
실무의 교훈이 있습니다. 분포에 대한 가정을 하나 추가할 때마다 상한이 날카로워집니다.
| 가정 | 얻는 것 |
|---|---|
| 비음 | 마르코프 |
| 분산 유한 | 체비쇼프 |
| 단봉, 대칭 | 상한이 더 줄어듭니다 |
| 유계 | 호에프딩(146강) |
| 존재 | 체르노프(문제 4) |
| 정규 | 정확한 값 |
셋째 줄이 흥미롭습니다. 단봉이라는 약한 가정만 더해도 이 로 줄어들며, 이를 비에나예채비셰프 부등식이라 합니다.
바로 확인 3.
확인 3-1. 마르코프의 등호 분포를 쓰세요.
답. , 인 두 점 분포입니다.
확인 3-2. 체비쇼프의 등호 분포를 쓰세요.
답. 에 각 , 에 나머지를 주는 세 점 분포입니다.
확인 3-3. 부등식이 느슨한 것이 결함입니까?
답. 아닙니다. 주어진 정보만으로는 최선입니다.
문제. 이항분포 , 의 오른쪽 꼬리를 봅니다.
(1) 실제 꼬리 확률을 계산하세요.
(2) 체비쇼프, 칸텔리, 체르노프 상한을 각각 구하세요.
(3) 감소 속도를 비교하세요.
생각의 실마리. 134강 심화 2에서 에 마르코프를 적용하면 체르노프가 나온다고 했습니다. 실제로 얼마나 날카로운지 확인합니다.
풀이. 검산 결과입니다.
| 실제 꼬리 | 체비쇼프 | 칸텔리 | 체르노프 | 체르노프실제 | |
|---|---|---|---|---|---|
| 2.844397\times10^ | 2.500000\times10^ | 2.000000\times10^ | 1.335137\times10^ | ||
| 1.758821\times10^ | 1.111111\times10^ | 1.000000\times10^ | 1.035740\times10^ | ||
| 3.925070\times10^ | 6.250000\times10^ | 5.882353\times10^ | 2.669931\times10^ | ||
| 2.818141\times10^ | 4.000000\times10^ | 3.846154\times10^ | 2.084037\times10^ | ||
| 5.579545\times10^ | 2.777778\times10^ | 2.702703\times10^ | 4.257960\times10^ |
세 상한 모두 참이지만 감소 속도가 전혀 다릅니다.
에서 칸텔리는 이고 체르노프는 로 약 배 차이입니다.
체르노프는 실제의 배에서 배 안에 머무릅니다.
이 문제에서 배우는 것: 체르노프 경계.
체르노프 경계. 가 존재하면 모든 에 대해
이며 가장 좋은 를 고르면
유도는 마르코프 한 번입니다. 가 비음이고 이면 와 가 같은 사건이므로
세 부등식이 모두 마르코프에서 나온 것입니다. 무엇에 적용하느냐만 다릅니다.
| 부등식 | 무엇에 마르코프를 적용하는가 |
|---|---|
| 마르코프 | 자체 |
| 체비쇼프 | (X-\mu)^ |
| 체르노프 | e^ |
지수함수를 쓰는 것이 결정적입니다. 제곱은 다항식이라 상한도 다항적으로 줄지만, 지수는 지수적으로 줄기 때문입니다.
르장드르 변환. 는 107강의 볼록 켤레함수이며 로 씁니다.
가 볼록이므로 이 최적화가 잘 정의됩니다. 134강 문제 5에서 이었고, 일반적으로 입니다.
대가는 이 존재해야 한다는 것입니다. 134강 문제 4의 로그정규처럼 꼬리가 두꺼우면 쓸 수 없고, 체비쇼프의 다항 감소로 만족해야 합니다.
| 꼬리 | 쓸 수 있는 최선 |
|---|---|
| 유계 | 호에프딩(146강) |
| 부분가우스 | 체르노프, |
| 지수 이하 | 체르노프, e^ |
| 멱법칙 | 체비쇼프, 1/t^ |
바로 확인 4.
확인 4-1. 체르노프 경계를 쓰세요.
답. 입니다.
확인 4-2. 세 부등식이 공통으로 쓰는 것을 쓰세요.
답. 모두 마르코프 부등식이며 적용 대상만 다릅니다.
확인 4-3. 체르노프를 쓸 수 없는 경우를 쓰세요.
답. 가 존재하지 않는 두꺼운 꼬리입니다.
문제. 체비쇼프를 표본평균에 적용합니다.
(1) 의 상한을 구하세요.
(2) 여러 과 에서 계산하세요.
(3) 원하는 보장을 위해 필요한 을 구하세요.
생각의 실마리. 133강 문제 4에서 이었습니다. 체비쇼프에 이 값을 넣습니다.
풀이. (1) 의 평균이 이고 분산이 이므로
(2) 에서 계산한 결과입니다.
| n=10^ | ||||
|---|---|---|---|---|
을 키우면 어떤 에 대해서도 으로 갑니다.
(3) 를 풀면 입니다.
| 필요한 | ||
|---|---|---|
이 문제에서 배우는 것: 약한 큰 수의 법칙.
약한 큰 수의 법칙. 가 독립이고 평균이 , 분산이 유한하면 임의의 에 대해
이며 이를 확률수렴이라 합니다.
증명이 체비쇼프 한 줄입니다. 상한 이 에서 으로 가기 때문입니다.
132강에서 미뤄 둔 약속이 여기서 지켜집니다. 기댓값의 두 얼굴 중 "장기 평균"이 정당화되었습니다. 다만 분산이 유한해야 하며, 132강 문제 4의 코시분포에서는 성립하지 않습니다.
142강에서 조건을 약화합니다. 실제로는 만으로 충분하며, 분산이 없어도 됩니다. 증명은 더 어렵습니다.
표본 크기 계산이 실무의 핵심 쓸모입니다. 그런데 체비쇼프의 답은 대단히 보수적입니다.
| 체비쇼프 | 호에프딩 (유계 ) | ||
|---|---|---|---|
약 배 차이입니다. 값이 에 갇혀 있다는 정보를 더 쓰면 호에프딩 부등식이 훨씬 적은 표본을 요구하며, 146강에서 다룹니다.
두 부등식의 형태 차이가 원인입니다.
체비쇼프는 이 에 비례하고 호에프딩은 에 비례합니다. 보장을 강하게 할수록 차이가 벌어집니다.
바로 확인 5.
확인 5-1. 표본평균에 체비쇼프를 적용한 결과를 쓰세요.
답. 입니다.
확인 5-2. 약한 큰 수의 법칙을 쓰고 필요한 가정을 쓰세요.
답. 표본평균이 참평균으로 확률수렴하며 독립과 유한 분산이 필요합니다.
확인 5-3. 체비쇼프와 호에프딩의 의존성 차이를 쓰세요.
답. 와 입니다.
| 부등식 | 식 | 필요한 것 |
|---|---|---|
| 마르코프 | ||
| 체비쇼프 | P(\lvert X-\mu\rvert\ge k\sigma)\le1/k^ | 분산 유한 |
| 칸텔리 | 분산 유한 | |
| 체르노프 | 존재 | |
| 큰 수의 법칙 | 독립, 분산 유한 |
| 모두 마르코프에서 | 무엇에 적용하는가 |
|---|---|
| 마르코프 | |
| 체비쇼프 | (X-\mu)^ |
| 체르노프 | e^ |
| 등호가 되는 분포 | 형태 |
|---|---|
| 마르코프 | 두 점 분포 |
| 체비쇼프 | 세 점 분포 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 음수를 갖는 에 마르코프를 씁니다 | 비음이어야 합니다 |
| "에 "를 일반화합니다 | 정규분포에서만입니다 |
| 부등식이 느슨해서 나쁘다고 봅니다 | 주어진 정보로는 최선입니다 |
| 꼬리가 두꺼운데 체르노프를 씁니다 | 이 없으면 못 씁니다 |
문제 6. 마르코프 부등식과 조건을 쓰세요.
답. 이며 이어야 합니다.
문제 7. 증명의 핵심 부등식을 쓰세요.
답. 이며 양변의 기댓값을 취합니다.
문제 8. 비음 조건이 왜 필요한지 쓰세요.
답. 큰 음수가 평균을 낮춰 논증이 무너지기 때문입니다.
문제 9. 체비쇼프 부등식을 두 형태로 쓰세요.
답. 과 형태입니다.
문제 10. 체비쇼프의 유도를 쓰세요.
답. 에 마르코프를 적용합니다.
문제 11. " 안에 "의 일반적 보장을 쓰세요.
답. 이며 는 정규분포에서만입니다.
문제 12. 칸텔리 부등식을 쓰세요.
답. 입니다.
문제 13. 마르코프와 체비쇼프의 등호 분포를 쓰세요.
답. 두 점 분포와 세 점 분포입니다.
문제 14. 부등식이 느슨한 것이 결함입니까?
답. 아닙니다. 주어진 정보만으로는 최선입니다.
문제 15. 체르노프 경계를 쓰고 유도를 쓰세요.
답. 이며 에 마르코프를 적용합니다.
문제 16. 세 부등식의 감소 속도를 각각 쓰세요.
답. , , 입니다.
문제 17. 표본평균에 체비쇼프를 적용한 결과와 그 함의를 쓰세요.
답. 이며 에서 이 되어 약한 큰 수의 법칙이 됩니다.
문제 18. 체비쇼프와 호에프딩의 의존성 차이를 쓰세요.
답. 와 입니다.
심화 1. 부등식의 계층을 정리하세요.
이 강의의 부등식들이 하나의 사다리를 이룹니다.
| 층 | 가정 | 상한 | 등호 |
|---|---|---|---|
| , 평균 | 두 점 분포 | ||
| 분산 유한 | \sigma^{2}/\varepsilon^ | 세 점 분포 | |
| 차 적률 | \mathbb{E}\lvert X-\mu\rvert^{k}/\varepsilon^ | 점 분포 | |
| 존재 | 기울어진 분포 |
셋째 줄이 일반화된 마르코프입니다. 에 마르코프를 적용하면 나오며, 를 키우면 상한이 로 빨라집니다. 다만 차 적률이 존재해야 합니다.
넷째 줄이 극한입니다. 모든 를 동시에 쓰는 것이 이며, 그래서 체르노프가 가장 날카롭습니다.
대편차 이론이 이 사다리의 정점입니다. 체르노프 경계가 지수적으로 정확하다는 것을 보이며
상한뿐 아니라 정확한 감소율을 줍니다. 크라메르 정리라 하며, 문제 4에서 체르노프가 실제의 배에서 배 안에 머문 것이 이 정리의 실제 모습입니다. 이 커져도 배율이 크게 늘지 않습니다.
심화 2. 젠센 부등식과의 관계를 보세요.
132강 심화 1의 젠센 부등식도 같은 가족입니다.
체르노프에서 실제로 쓰입니다. 이므로
이고 따라서 가 일 때만 양수입니다. 평균보다 작은 값에 대해서는 오른쪽 꼬리 경계가 무의미하다는 뜻이며, 당연한 결과가 식에서 나옵니다.
부등식들의 계보를 정리하면 이렇습니다.
| 부등식 | 무엇에서 나오는가 |
|---|---|
| 체비쇼프 | 마르코프 |
| 체르노프 | 마르코프 + 젠센 |
| 호에프딩 | 체르노프 + 유계성 |
| 베른슈타인 | 체르노프 + 분산 |
| 매디아미드 | 마팅게일 + 체르노프 |
전부 마르코프에서 시작합니다. 확률론에서 가장 단순한 부등식 하나가 집중 현상 이론 전체를 떠받칩니다.
심화 3. 강한 큰 수의 법칙과의 차이를 정리하세요.
문제 5에서 증명한 것은 약한 버전입니다.
| 버전 | 진술 | 이름 |
|---|---|---|
| 약한 | 확률수렴 | |
| 강한 | 거의 확실한 수렴 |
차이가 미묘하지만 실질적입니다.
약한 버전은 각 마다 벗어날 확률이 작다고 말합니다. 강한 버전은 하나의 궤적을 끝까지 따라가면 반드시 수렴한다고 말합니다.
약한 것이 강한 것을 함의하지 않습니다. 매 마다 벗어날 확률이 작아도, 무한히 자주 벗어날 수 있습니다. 확률들의 합이 발산하면 실제로 그렇게 됩니다.
보렐칸텔리 보조정리가 다리입니다.
체비쇼프의 상한 은 합이 발산하므로(이 조화급수) 이것만으로는 강한 버전을 얻지 못합니다. 부분수열을 쓰거나 사차 적률을 쓰는 더 정교한 논증이 필요하며, 142강에서 다룹니다.
실무에서 어느 쪽이 중요한지가 갈립니다.
| 상황 | 필요한 버전 |
|---|---|
| 고정된 의 오차 보장 | 약한 것으로 충분합니다 |
| 온라인 학습의 수렴 | 강한 것이 필요합니다 |
| 몬테카를로 정지 규칙 | 강한 것이 안전합니다 |
심화 4. 부등식이 학습이론에서 쓰이는 자리를 보세요.
122강 심화 4에서 부울 부등식과 결합한 형태를 예고했습니다. 완성해 봅니다.
한 가설 에 대해서는 호에프딩이 이렇게 줍니다.
그런데 우리는 훈련 뒤에 가장 좋아 보이는 를 고릅니다. 그 는 데이터에 의존하므로 위 부등식을 바로 쓸 수 없습니다.
부울 부등식으로 모든 를 동시에 덮습니다.
이것을 이하로 만들면 일반화 상한이 나옵니다.
가설공간이 클수록 벌점이 커집니다. 가 모형 복잡도의 척도이며, 무한 가설공간에서는 VC 차원이 이 역할을 합니다.
세 도구가 모두 이 단원과 앞 단원에서 나왔습니다.
| 도구 | 어디서 |
|---|---|
| 호에프딩 | 체르노프(문제 4) |
| 부울 부등식 | 122강 문제 2 |
| 표본평균의 분산 | 133강 문제 4 |
심화 5. 실무에서 부등식을 쓰는 방법을 정리하세요.
첫째로 서비스 수준 약속입니다. 응답 시간의 평균만 알 때 마르코프로 상한을 약속할 수 있습니다. 평균이 밀리초면 초를 넘을 확률이 이하입니다. 분포를 몰라도 되는 것이 계약에서 중요합니다.
둘째로 이상 탐지 임계값입니다. 정규성을 가정할 수 없으면 대신 체비쇼프로 임계를 정합니다. 를 정하면 위양성률이 이하로 보장됩니다.
셋째로 A/B 테스트 표본 크기입니다. 문제 5의 계산이며, 127강 심화 6에서 정규 근사로 한 것보다 보수적입니다. 정규성을 믿을 수 없을 때 안전한 하한을 줍니다.
넷째로 확률적 알고리즘의 반복 횟수입니다. 성공확률 인 시행을 반복해 실패 확률을 이하로 만들려면
이며 의존이라 매우 효율적입니다. 라스베이거스 알고리즘의 표준 분석입니다.
주의할 점 하나가 있습니다. 부등식은 상한이므로 실제 확률을 추정하는 데 쓰면 안 됩니다. "체비쇼프로 "라는 말은 " 이하"이지 ""가 아닙니다.
심화 6. 집중 현상을 미리 보세요.
문제 5에서 표본평균이 참값 근처에 모인다고 했습니다. 이 현상이 훨씬 일반적입니다.
집중 부등식. 많은 독립 성분에 의존하지만 어느 하나에는 크게 의존하지 않는 함수는 그 평균 근처에 집중됩니다.
표본평균은 특수한 경우입니다. 는 각 를 만큼만 반영합니다.
일반화가 매디아미드 부등식입니다. 가 각 좌표를 바꿀 때 이상 변하지 않으면
평균 말고도 최댓값, 정렬 결과, 그래프의 연결성 같은 복잡한 함수에 쓸 수 있습니다.
고차원에서 이 현상이 강해집니다. 차원이 오를수록 함수값이 평균 근처에 더 몰리며, 이를 측도의 집중이라 합니다.
| 현상 | 고차원에서 |
|---|---|
| 구면의 부피 | 적도 근처에 집중됩니다 |
| 두 무작위 벡터의 각도 | 거의 직각입니다 |
| 정규 벡터의 노름 | 근처에 집중됩니다 |
| 최근접 이웃 거리 | 모든 점이 비슷하게 멉니다 |
넷째 줄이 차원의 저주의 정확한 형태입니다. 거리 기반 방법이 고차원에서 무너지는 것은 거리들이 모두 비슷해지기 때문이며, 이는 집중 현상의 결과입니다.
146강에서 정식으로 다루며, 이 단원의 부등식들이 그 출발점입니다.
import numpy as np, math, itertools
Phi = lambda z: 0.5*(1 + math.erf(z/np.sqrt(2)))
# --- 문제 1: 평균만으로 꼬리를 제한한다 ---------------------------------
print(" 마르코프 부등식 P(X >= a) <= E[X]/a (X >= 0)")
print(" 분포 E[X] a 실제 P(X>=a) 상한 E[X]/a 상한/실제")
lam = 1.0
for a in [1.0, 2.0, 5.0, 10.0]:
act = np.exp(-lam*a); ub = (1/lam)/a
print(" %-16s %7.3f %6.1f %14.8f %14.8f %12.2f"
% ("지수 lam=1", 1/lam, a, act, ub, ub/act))
print(" 균등 U(0,1) 에서도 봅니다")
for a in [0.5, 0.8, 0.95]:
act = 1-a; ub = 0.5/a
print(" %-16s %7.3f %6.2f %14.8f %14.8f %12.2f"
% ("균등 U(0,1)", 0.5, a, act, ub, ub/act))
print(" 상한은 a 가 커지면 1/a 로만 줄어드는데 실제 꼬리는 훨씬 빨리 줄어듭니다")
print(" 대신 분포를 전혀 몰라도 됩니다. 비음이고 평균만 알면 성립합니다")
# 마르코프 부등식 P(X >= a) <= E[X]/a (X >= 0)
# 분포 E[X] a 실제 P(X>=a) 상한 E[X]/a 상한/실제
# 지수 lam=1 1.000 1.0 0.36787944 1.00000000 2.72
# 지수 lam=1 1.000 2.0 0.13533528 0.50000000 3.69
# 지수 lam=1 1.000 5.0 0.00673795 0.20000000 29.68
# 지수 lam=1 1.000 10.0 0.00004540 0.10000000 2202.65
# 균등 U(0,1) 에서도 봅니다
# 균등 U(0,1) 0.500 0.50 0.50000000 1.00000000 2.00
# 균등 U(0,1) 0.500 0.80 0.20000000 0.62500000 3.13
# 균등 U(0,1) 0.500 0.95 0.05000000 0.52631579 10.53
# 상한은 a 가 커지면 1/a 로만 줄어드는데 실제 꼬리는 훨씬 빨리 줄어듭니다
# 대신 분포를 전혀 몰라도 됩니다. 비음이고 평균만 알면 성립합니다
# --- 문제 2: 분산까지 쓰면 날카로워진다 ---------------------------------
print(" 체비쇼프 부등식 P(|X-mu| >= k sigma) <= 1/k^2")
print(" k 1/k^2 상한 정규분포 실제 지수분포 실제 균등분포 실제")
for k in [1, 2, 3, 4, 5]:
ub = 1/k**2
nor = 2*(1-Phi(k))
# 지수 lam=1: mu=1, sigma=1. |X-1| >= k -> X >= 1+k 또는 X <= 1-k
ex = np.exp(-(1+k)) + (1 - np.exp(-max(0.0, 1-k)))
# 균등 U(0,1): mu=0.5, sigma=1/sqrt(12)
s = 1/np.sqrt(12); un = max(0.0, 1 - 2*min(0.5, k*s))
print(" %9d %13.8f %17.8f %17.8f %16.8f" % (k, ub, nor, ex, un))
print(" k=1 에서 상한이 1 이라 아무 정보가 없습니다. k 가 커야 쓸모가 생깁니다")
print(" 분포를 알면 훨씬 날카롭습니다. 정규분포 k=3 에서 0.1111 대 0.0027 로 41 배 차이입니다")
print(" k=3 에서 상한 %.6f, 정규 실제 %.6f, 비 %.1f"
% (1/9, 2*(1-Phi(3)), (1/9)/(2*(1-Phi(3)))))
# 체비쇼프 부등식 P(|X-mu| >= k sigma) <= 1/k^2
# k 1/k^2 상한 정규분포 실제 지수분포 실제 균등분포 실제
# 1 1.00000000 0.31731051 0.13533528 0.42264973
# 2 0.25000000 0.04550026 0.04978707 0.00000000
# 3 0.11111111 0.00269980 0.01831564 0.00000000
# 4 0.06250000 0.00006334 0.00673795 0.00000000
# 5 0.04000000 0.00000057 0.00247875 0.00000000
# k=1 에서 상한이 1 이라 아무 정보가 없습니다. k 가 커야 쓸모가 생깁니다
# 분포를 알면 훨씬 날카롭습니다. 정규분포 k=3 에서 0.1111 대 0.0027 로 41 배 차이입니다
# k=3 에서 상한 0.111111, 정규 실제 0.002700, 비 41.2
# --- 문제 3: 느슨한 것이 아니라 최선이다 --------------------------------
print(" 두 부등식은 최악의 분포에서 등호가 됩니다")
print(" 마르코프 등호 분포: P(X=0)=1-p, P(X=a)=p. E[X] = p*a")
print(" a p E[X] P(X>=a) 상한 E[X]/a 차이")
for a, p in [(2.0, 0.5), (5.0, 0.2), (10.0, 0.1)]:
print(" %9.1f %6.2f %8.2f %10.4f %14.4f %10.2e"
% (a, p, p*a, p, (p*a)/a, abs(p - (p*a)/a)))
print(" 체비쇼프 등호 분포: P(X=-k s)=P(X=k s)=1/(2k^2), P(X=0)=1-1/k^2")
print(" k P(|X|>=k s) 1/k^2 평균 분산 차이")
for k in [2.0, 3.0, 5.0]:
q = 1/(2*k*k); pm = 2*q
m = 0.0
v = 2*q*(k*1.0)**2 + (1-2*q)*0.0 # sigma=1 로 두면 분산이 1
print(" %9.1f %13.6f %10.6f %8.2f %8.4f %8.2e"
% (k, pm, 1/k**2, m, v, abs(pm - 1/k**2)))
print(" 분포를 모른다는 조건에서는 더 줄일 수 없습니다. 부등식이 최선입니다")
# 두 부등식은 최악의 분포에서 등호가 됩니다
# 마르코프 등호 분포: P(X=0)=1-p, P(X=a)=p. E[X] = p*a
# a p E[X] P(X>=a) 상한 E[X]/a 차이
# 2.0 0.50 1.00 0.5000 0.5000 0.00e+00
# 5.0 0.20 1.00 0.2000 0.2000 0.00e+00
# 10.0 0.10 1.00 0.1000 0.1000 0.00e+00
# 체비쇼프 등호 분포: P(X=-k s)=P(X=k s)=1/(2k^2), P(X=0)=1-1/k^2
# k P(|X|>=k s) 1/k^2 평균 분산 차이
# 2.0 0.250000 0.250000 0.00 1.0000 0.00e+00
# 3.0 0.111111 0.111111 0.00 1.0000 0.00e+00
# 5.0 0.040000 0.040000 0.00 1.0000 0.00e+00
# 분포를 모른다는 조건에서는 더 줄일 수 없습니다. 부등식이 최선입니다
# --- 문제 4: 적률생성함수까지 쓰면 지수가 된다 --------------------------
print(" 체르노프 P(X >= a) <= inf_t e^{-ta} M(t)")
print(" 이항 n=100, p=0.5 의 오른쪽 꼬리를 세 방법으로 잡습니다")
n, p = 100, 0.5
mu_b, sd_b = n*p, np.sqrt(n*p*(1-p))
def exact_tail(a):
return sum(math.comb(n, k)*p**k*(1-p)**(n-k) for k in range(int(np.ceil(a)), n+1))
def chern(a):
ts = np.linspace(1e-6, 3.0, 300001)
M = (1-p+p*np.exp(ts))**n
return float(np.min(np.exp(-ts*a)*M))
print(" 체비쇼프는 양쪽 부등식이라 한쪽 꼬리에는 칸텔리 부등식이 더 맞습니다")
print(" 칸텔리 P(X-mu >= t) <= sigma^2/(sigma^2 + t^2)")
print(" a 실제 꼬리 체비쇼프 칸텔리 체르노프 체르노프/실제")
for a in [60, 65, 70, 75, 80]:
act = exact_tail(a)
t_ = a - mu_b; d = t_/sd_b
cheb = min(1.0, 1/(d*d))
cant = sd_b**2/(sd_b**2 + t_*t_)
ch = chern(a)
print(" %9d %13.6e %13.6e %13.6e %13.6e %13.1f"
% (a, act, cheb, cant, ch, ch/act))
print(" 세 상한 모두 참이지만 감소 속도가 다릅니다")
print(" 체비쇼프와 칸텔리는 1/t^2 로 줄고 체르노프는 지수로 줄어듭니다")
print(" a=80 에서 칸텔리 %.3e 대 체르노프 %.3e 로 %.0f 배 차이입니다"
% (sd_b**2/(sd_b**2 + (80-mu_b)**2), chern(80),
(sd_b**2/(sd_b**2 + (80-mu_b)**2))/chern(80)))
# 체르노프 P(X >= a) <= inf_t e^{-ta} M(t)
# 이항 n=100, p=0.5 의 오른쪽 꼬리를 세 방법으로 잡습니다
# 체비쇼프는 양쪽 부등식이라 한쪽 꼬리에는 칸텔리 부등식이 더 맞습니다
# 칸텔리 P(X-mu >= t) <= sigma^2/(sigma^2 + t^2)
# a 실제 꼬리 체비쇼프 칸텔리 체르노프 체르노프/실제
# 60 2.844397e-02 2.500000e-01 2.000000e-01 1.335137e-01 4.7
# 65 1.758821e-03 1.111111e-01 1.000000e-01 1.035740e-02 5.9
# 70 3.925070e-05 6.250000e-02 5.882353e-02 2.669931e-04 6.8
# 75 2.818141e-07 4.000000e-02 3.846154e-02 2.084037e-06 7.4
# 80 5.579545e-10 2.777778e-02 2.702703e-02 4.257960e-09 7.6
# 세 상한 모두 참이지만 감소 속도가 다릅니다
# 체비쇼프와 칸텔리는 1/t^2 로 줄고 체르노프는 지수로 줄어듭니다
# a=80 에서 칸텔리 2.703e-02 대 체르노프 4.258e-09 로 6347412 배 차이입니다
# --- 문제 5: 큰 수의 법칙이 두 줄로 나온다 ------------------------------
print(" 체비쇼프를 표본평균에 적용하면 큰 수의 법칙이 나옵니다")
print(" P(|Xbar - mu| >= eps) <= sigma^2 / (n eps^2)")
sig2 = 1.0
print(" eps n=100 n=1000 n=10000 n=1000000")
for eps in [0.5, 0.1, 0.05, 0.01]:
vs = [sig2/(nn*eps*eps) for nn in [100, 1000, 10000, 1000000]]
print(" %9.2f %11.6f %12.6f %12.6f %13.6f" % (eps, *[min(1.0, v) for v in vs]))
print(" n 을 키우면 어떤 eps 에 대해서도 0 으로 갑니다. 이것이 약한 큰 수의 법칙입니다")
print(" 필요한 n 을 역으로 구합니다. n >= sigma^2 / (delta eps^2)")
print(" eps delta 필요한 n")
for eps, delta in [(0.1, 0.05), (0.01, 0.05), (0.01, 0.01)]:
print(" %9.2f %9.2f %14d" % (eps, delta, int(np.ceil(sig2/(delta*eps*eps)))))
print(" 146강의 호에프딩은 같은 보장에 훨씬 적은 n 을 요구합니다")
print(" eps delta 체비쇼프 n 호에프딩 n(유계 [0,1])")
for eps, delta in [(0.1, 0.05), (0.01, 0.05)]:
nc = int(np.ceil(sig2/(delta*eps*eps)))
nh = int(np.ceil(np.log(2/delta)/(2*eps*eps)))
print(" %9.2f %7.2f %12d %20d" % (eps, delta, nc, nh))
# 체비쇼프를 표본평균에 적용하면 큰 수의 법칙이 나옵니다
# P(|Xbar - mu| >= eps) <= sigma^2 / (n eps^2)
# eps n=100 n=1000 n=10000 n=1000000
# 0.50 0.040000 0.004000 0.000400 0.000004
# 0.10 1.000000 0.100000 0.010000 0.000100
# 0.05 1.000000 0.400000 0.040000 0.000400
# 0.01 1.000000 1.000000 1.000000 0.010000
# n 을 키우면 어떤 eps 에 대해서도 0 으로 갑니다. 이것이 약한 큰 수의 법칙입니다
# 필요한 n 을 역으로 구합니다. n >= sigma^2 / (delta eps^2)
# eps delta 필요한 n
# 0.10 0.05 2000
# 0.01 0.05 200000
# 0.01 0.01 1000000
# 146강의 호에프딩은 같은 보장에 훨씬 적은 n 을 요구합니다
# eps delta 체비쇼프 n 호에프딩 n(유계 [0,1])
# 0.10 0.05 2000 185
# 0.01 0.05 200000 18445
문제 3의 두 표에서 차이가 모두 정확히 입니다. 부등식이 느슨해 보이는 것은 결함이 아니라, 주어진 정보만으로는 더 줄일 수 없다는 뜻입니다. 최악의 분포가 실제로 존재합니다.
문제 4의 표가 이 강의의 요약입니다. 같은 꼬리에 대해 세 상한이 , , 입니다. 정보를 더 쓸수록 상한이 날카로워지며, 체르노프는 참값의 배 안에 있습니다.
문제 5의 마지막 표가 다음 단원으로 가는 이유입니다. 같은 보장에 체비쇼프는 개, 호에프딩은 개를 요구합니다. 약 배 차이이며, 146강에서 이 개선을 다룹니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 마르코프 부등식 | Markov's inequality | 평균만으로 꼬리를 제한합니다 |
| 체비쇼프 부등식 | Chebyshev's inequality | 분산까지 씁니다 |
| 칸텔리 부등식 | Cantelli's inequality | 한쪽 꼬리 전용입니다 |
| 체르노프 경계 | Chernoff bound | 를 써서 지수적입니다 |
| 르장드르 변환 | 입니다 | |
| 확률수렴 | convergence in probability | 약한 큰 수의 법칙입니다 |
| 거의 확실한 수렴 | almost sure convergence | 강한 버전입니다 |
| 보렐칸텔리 보조정리 | Borel-Cantelli lemma | 두 수렴을 잇습니다 |
| 크라메르 정리 | Cramér's theorem | 체르노프가 지수적으로 정확합니다 |
| 매디아미드 부등식 | McDiarmid's inequality | 일반 함수의 집중입니다 |
| 측도의 집중 | concentration of measure | 고차원에서 값이 몰립니다 |
| 비에나예채비셰프 | Vysochanskij-Petunin | 단봉이면 상한이 줄어듭니다 |
여기서 03단원 기댓값과 적률이 끝납니다. 132강에서 분포를 하나의 수로 요약하고, 133강에서 퍼짐을 재고, 134강에서 모든 적률을 한 함수에 담고, 135강에서 그 요약만으로 확률을 얼마나 제한할 수 있는지 보았습니다.
네 강의가 하나의 흐름입니다.
다음 136강부터 04단원 여러 변수의 확률이 시작됩니다. 지금까지는 확률변수가 하나였습니다. 둘 이상이 되면 관계라는 새로운 대상이 나타나며, 133강 문제 3에서 공분산을 미리 쓴 것이 정식화됩니다. 105강의 변수변환과 86강의 스펙트럼 정리가 다시 도구가 되고, 140강의 다변량 정규분포에서 S4의 이차형식이 확률의 언어로 나타납니다.