스털링근사 (1) 썸네일형 리스트형 상자에 공 넣기 (Balls into Bins Problem) 다음과 같은 상황을 생각해 보죠. 여러분의 눈 앞에는 n 개의 상자가 있고 옆에는 n 개의 공이 있습니다. 여러분은 공을 상자에 넣어야 합니다. 항상 특별한 일상을 원하는 여러분은 좀 독특한 방식으로 공을 상자에 담아 보고자 합니다. 바로 공 하나를 넣을 때 상자를 균등한 확률(uniformly at random)로 선정하여 거기에 담는 것이죠. 과연 이런 방식으로 넣었을 때 상자에 담긴 공의 개수 중 가장 큰 값은 무엇일까요? 최악의 경우에는 당연히 n이 됩니다. 상자 하나에 모두 담기는 것이죠. 하지만 이런 경우가 많이 일어날까요? 각각의 공이 각 상자에 담길 확률이 1n이고 이전에 공을 어떻게 넣었느냐가 이번에 넣을 공을 어떻게 넣을지 영향을 주지 않.. 이전 1 다음
