아무튼 그쪽 분야 문제 풀이...라기보다 직관 + 귀납법 풀이 추가

문제는 여기: https://arca.live/b/math/36137571

풀이 혹은 논의는 여기: https://arca.live/b/math/36155397

------------------------------------------------------------------------------------------------

총 n개의 상자 중 m개의 상자에 돌이 들어 있고, 나머지 상자는 비어있습니다. (단 n >= m)

무작위로 상자를 열어서 돌이 든 m개의 상자를 모두 찾는 것이 목표입니다.

m개의 상자를 찾을 때까지 열은 모든 상자의 개수를 k개라고 한다면,

k의 평균기댓값은 얼마인가요?

------------------------------------------------------------------------------------------------

이렇게 생각해보겠습니다.

(1) 우선 m 개의 돌이 들어있는 상자가 있습니다.

(2) 여기에 n - m 개의 빈 상자를 하나씩 random 하게 집어넣습니다.

그러면 m + 1 개의, 돌이 든 상자 사이의 공간은 서로 동등하므로, 각각의 공간에 들어가는 빈 상자 숫자의 기대값은 (n-m)/(m+1) 입니다.

물론 n-m 개의 빈 상자가 각각의 m+1 개의 공간에 같은 확률로 들어간다는 뜻은 아닙니다. 예컨대 첫 번째 상자가 2 번째와 돌상자와 세 번째 돌상자 사이의 공간에 들어갔다면, 다음 빈 상자를 넣는 입장에서 보면 m+2 개의 공간에 random 하게 집어넣게 되므로, 2번째 돌상자와 세 번째 돌상자 사이에 들어갈 확률은 다른 상자들 사이 혹은 가장자리에 들어갈 확률의 2배가 될 겁니다.

그러나 어떤 식으로 집어넣건, 결국 시작하는 시점에서 m+1 개의 공간은 서로 동등하므로, 기대값이 서로 같을 수밖에 없습니다.

따라서 마지막 m번째 돌상자 이후에 오는 빈 상자 숫자의 기대값도 (n-m)/(m+1) 이므로

k 의 기대값은 n - (n-m)/(m+1) = (n+1)m/(m+1) 이 됩니다.

------------------------------------------------------------------------------------------------

전체 상자 숫자가 n 일 때 마지막 m번째 돌상자 이후에 오는 빈 상자 숫자의 기대값을 E(n, m) 이라고 하고

E(n, m) = (n-m)/(m+1) 이라는 것을 증명합니다.

(1) n = m 일 때 E(m, m) = 0 은 당연하게 성립합니다.

(2) n= k 에서 성립할 때

E(k+1, m) - E(k) 는 k+1 번째 빈 상자가 m번째 돌상자 이후에 올 확률과 같습니다.

P(u) = 전체 상자 숫자가 k일 때 마지막 m번째 돌상자 이후에 오는 빈 상자의 숫자가 u 일 확률 이라고 하면

(원칙적으로는 P(k, m, u) 로 표기해야겠지만 다른 k값에 대해서 P를 나타내지는 않을 것이므로 k, m은 생략합니다.)

m번째 돌상자 이후에 오는 빈 상자의 숫자가 u일 때, k+1 개의 "상자 사이의 빈 칸" 중에서 m번째 이후의 것은 u+1 개이므로