알고리즘 & 확률/Balls into bins (3) 썸네일형 리스트형 「상자에 공 넣기, 상자를 두 개씩 고르면?」 증명 보충 예전에 상자에 공 넣기 문제(balls-into-bins problem)에서 매번 상자 두 개를 균일한 확률로 골라 공의 개수가 적은 쪽에 넣으면 어떻게 되는지 소개해 드린 적이 있습니다. 2020.03.22 - [알고리즘 & 확률/Balls into bins] - 상자에 공 넣기, 상자를 두 개씩 고르면? (Power of Two Choices) 상자에 공 넣기, 상자를 두 개씩 고르면? (Power of Two Choices) 지난 포스트에서는 상자에 공 넣기 문제(balls into bins problem)를 공부했습니다. 2020/03/21 - [수학적 도구/Randomness] - 상자에 공 넣기 (Balls into Bins Problem) 상자에 공 넣기 (Balls into Bins Pro.. 상자에 공 넣기, 상자를 두 개씩 고르면? (Power of Two Choices) 지난 포스트에서는 상자에 공 넣기 문제(balls into bins problem)를 공부했습니다. 2020/03/21 - [수학적 도구/Randomness] - 상자에 공 넣기 (Balls into Bins Problem) 상자에 공 넣기 (Balls into Bins Problem) 다음과 같은 상황을 생각해 보죠. 여러분의 눈 앞에는 \(n\) 개의 상자가 있고 옆에는 \(n\) 개의 공이 있습니다. 여러분은 공을 상자에 넣어야 합니다. 항상 특별한 일상을 원하는 여러분은 좀 독특한 방식으로.. gazelle-and-cs.tistory.com 문제는 다음과 같았습니다. 우리에게 \(n\) 개의 공이 주어지고 우리는 이를 \(n\) 개의 상자에 담으려고 합니다. 만약 우리가 공을 하나씩 넣을 때마다 .. 상자에 공 넣기 (Balls into Bins Problem) 다음과 같은 상황을 생각해 보죠. 여러분의 눈 앞에는 \(n\) 개의 상자가 있고 옆에는 \(n\) 개의 공이 있습니다. 여러분은 공을 상자에 넣어야 합니다. 항상 특별한 일상을 원하는 여러분은 좀 독특한 방식으로 공을 상자에 담아 보고자 합니다. 바로 공 하나를 넣을 때 상자를 균등한 확률(uniformly at random)로 선정하여 거기에 담는 것이죠. 과연 이런 방식으로 넣었을 때 상자에 담긴 공의 개수 중 가장 큰 값은 무엇일까요? 최악의 경우에는 당연히 \(n\)이 됩니다. 상자 하나에 모두 담기는 것이죠. 하지만 이런 경우가 많이 일어날까요? 각각의 공이 각 상자에 담길 확률이 \( \frac{1}{n} \)이고 이전에 공을 어떻게 넣었느냐가 이번에 넣을 공을 어떻게 넣을지 영향을 주지 않.. 이전 1 다음
