Reservoir Sampling 썸네일형 리스트형 Reservoir Sampling Q. 전체 모집단의 갯수(n)를 알지 못하는 상황에서 편향 없이 1개를 샘플링하면 각 샘플링의 확률은 1/n이 된다. 어떻하면 이를 코드로 구현할 수 있을까? https://www.youtube.com/watch?v=A1iwzSew5QY 위의 영상에 방법이 나와 있다. 모자 n개가 있고, i 번째 모자를 최종적으로 쓰고 있으려면 (i 번째 모자를 쓰고), (i+1번째 모자를 쓰지 않고), (i+2번째 모자를 쓰지 않고)... (n번째 모자를 쓰지 않으면 된다) 즉, (i번째 모자를 최종적으로 쓰고 있을 확률) = (i 번째를 선택할 확률) = (1 / i) * (1 - (1/(i+1))) * (1 - (1/(i+1))) ... *(1 - 1/(n)) 이 식을 정리하면 1 / n 이 된다. 따라서, 코드로.. 더보기 이전 1 다음