독일 탱크 문제 German tank problem

Data Genetics 블로그에서 독일 탱크 문제에 관한 포스팅을 하길래 계산을 좀 해봤다. ㅋ 본 포스팅 내용은 마지막 약간의 본인의 계산을 제외하면 거의 위키피디아의 내용을 베낀 것임을 미리 알려둔다.

 


때는 바야흐로 할 이야기가 차고 넘치는 2차 세계 대전 중이다. ㅋ 위키피디아에 따르면, D-day 상륙작전 전에 독일군이 대규모 Panzer 5호 전차를 운용한다는 소문이 돌았다고 한다. 그래서 연합군은 독일의 탱크 생산량을 추정하고 싶었은데, 가장 전통적인 방법은 첩보정보를 입수하는 것이다. 그러나 과장으로 점철된 독일군의 홍보 때문에 이게 쉽지 않았던 모양이다. 그래서 추정을 하는 다른 방법으로 파괴된 전차들의 일련번호들을 조사해 독일군 운용 전차 크기를 통계적으로 추정하는 연구를 시작했는데, 전쟁 이후에 실제 독일군의 전차 운용 데이터가 드러나면서 두 결과를 비교한 표가 위키피디아에 나와 있으니 이를 그대로 베껴보자. ㅋ

시기 통계적 추정 첩보 정보 독일군 기록
1940년 6월 169 1,000 122
1941년 6월 244 1,550 271
1942년 8월 327 1,550 342

딱 봐도 통계학의 완벽한 승리다. ㅋㅋㅋ 위키피디아에 따르면 한국전쟁 당시에 소련군 장비를 추정할 때도 쓰인 모양이다. 근데 과연 어떻게 계산 했을까?

먼저 세팅을 해보자. N은 실제 독일군 탱크 대수라 하고 (추정하고 싶은 바로 그 값), k는 관측된 탱크의 수라 하고, m은 관측된 일련번호중 가장 큰 값이라 하자. 만약 시리얼 넘버 #2, #6, #7, #14인 네 대의 탱크가 발견되었다면, k=4, m=14가 된다. 이걸로 우리는 독일군 전체 탱크의 대수를 추정하고 싶다. 모든 모델링이 그렇듯 몇 가지 가정이 필요하다.

  1. 시리얼 넘버가 겹치는 탱크가 없다.
  2. 시리얼 넘버는 1부터 시작한다.
  3. 시리얼 넘버는 1씩 커진다.

아마 실제로는 조금 더 복잡하겠지만, 수학적 재미를 위해 과감히 생략하자. 여하간 그렇다면, 전체 운용 탱크의 대수는 적어도 m대 이상은 되어야 한다. 비교적 쉽게 생각할 수 있는 추정방법 중 하나는, 관측된 값들의 평균 간격을 최대값에 더하는 것이다. 샘플이 k개이고, 최대값이 m이므로 평균 간격은 \frac{m-k}{k}가 된다. 왜 k를 빼냐하면 샘플 그 자체를 세지 않기 때문이다. 위에서 예를 든 숫자의 경우, #2와 #6 사이에는 탱크가 #3, #4, #5 세 대가 있으므로 두 샘플간의 간격은 3이다. 그래서 각 샘플의 간격은 1, 3, 0, 6이므로 평균 간격은 10/4가 된다. 이를 최대값에 더하면 16.5가 추정되는 탱크의 수가 된다. 일반적으로,

\displaystyle \hat{N} = m + \frac{m-k}{k} = m\left(1+\frac{1}{k}\right)-1

이 대충 추정한 계산값이 unbiased 인지 확인해보자. E(\hat{N}) = N 임을 확인하면 된다. m의 기대값은 다음과 같이 계산된다.

\displaystyle E(m) = \sum_{m=k}^N m\frac{\binom{m-1}{k-1}}{\binom{N}{k}} = \frac{1}{\binom{N}{k}}\sum_{m=k}^N k\binom{m}{k} = k\frac{\binom{N+1}{k+1}}{\binom{N}{k}} = \frac{k(N+1)}{k+1}

마지막 부분에서 파스칼 삼각형의 대각선을 따라 더하는 공식을 썼다. 따라서

\displaystyle E(\hat{N}) = E\left(m (1+1/k )-1\right) = N

그러므로 우리의 추정량은 unbiased 라는 것을 알 수 있다.

베이지안을 써서 다른 추정을 해 보자. 독일 탱크의 수는 확률에 따라 변하는 확률 변수로 볼 수 있으므로 확률 질량함수를 유도해보자. 관측 최대값 m과 관측 대수 k를 확률변수화하여 M, K라고 두고, P(N=n \mid M = m \cap K=k)라는 확률을 (n \mid m, k) 라고 줄여 표기하자. 조건부 확률 공식을 이용하면,

\displaystyle (n\mid m, k) = \frac{(n, m, k)}{(m, k)} = (m\mid n, k)\frac {(n, k)}{(m, k)} = (m\mid n, k)\frac {(n\mid k)}{(m\mid k)}

가 된다. 우측 세 항을 따로따로 계산해보자.

먼저 (m | n, k) 부분인데, 말 그대로 독일군 전차수가 n이고, k대 관측할 때 m이 최대값이 될 확률이므로 경우의 수를 세면 다음과 같다.

\displaystyle (m\mid n, k) = \begin{cases} \frac{\binom{m - 1}{k - 1}}{\binom{n}{k}} &\text{if } k \le m \le n\\ 0 &\text{otherwise} \end{cases}

(n | k)는 k대 관측할 때, 독일군 전차수가 n일 확률인데, 몇 대를 관측하든 그 이상의 숫자들은 동일한 확률이라고 가정한다. 즉, 100대를 관측했으면 독일군 전차수가 총 100대일 확률, 101대일 확률 , 102대일 확률 … 등등이 다 같다고 본다. 즉 discrete uniform distribution이므로,

\displaystyle (n\mid k) = \begin{cases} \frac 1{\Omega - k} &\text{if } k \le n < \Omega \\ 0 &\text{otherwise} \end{cases}

여기서 오메가는 충분히 큰 수이다. 무한히 클 수 있다고 가정하면 확률이 모두 빵이 되므로 적절한 upper bound로 막아준다.

마지막으로 (m | k)인데, 이건 가능한 모든 n에 대해 합산해준다. 즉,

\displaystyle \begin{aligned} (m \mid k) &=(m\mid k)\cdot 1 \\ &=(m\mid k){\sum_{n=0}^\infty(n\mid m, k)} \\ &=(m\mid k){\sum_{n=0}^\infty(m\mid n, k)\frac {(n\mid k)}{(m\mid k)}} \\ &=\sum_{n=0}^\infty(m\mid n, k)(n\mid k) \end{aligned}

위 결과들을 종합하면

\displaystyle (n\mid m, k) = \begin{cases} \frac{(m\mid n, k)}{\sum_{n=m}^{\Omega - 1} (m\mid n, k)} &\text{if } m \le n < \Omega \\ 0 &\text{otherwise} \end{cases}

인제 (n | k)가 약분되었는데, 아래쪽의 합이 오메가를 무한대로 보내도 수렴하므로 무한급수로 바꾼다.

\displaystyle (n \mid m, k) = \begin{cases} 0 &\text{if } n < m \\ \frac{(m\mid n, k)}{\sum_{n=m}^{\infty}(m\mid n, k)} &\text{if } n \ge m \end{cases}

저 무한급수는 어떻게 계산할까? 다음과 같은 기가막힌 partial fraction을 보자.

\displaystyle \frac{1}{\binom{j}{k}} = \frac{k}{k-1}\left(\frac{1}{\binom{j-1}{k-1}}-\frac{1}{\binom{j}{k-1}}\right)

ㅋㅋ 이런건 각자 증명해보자. 별로 안 어렵다. 여하간 그래서 다음과 같은 확률 분포를 얻는다.

\displaystyle (n \mid m, k) = \begin{cases} 0 &\text{if } n < m \\ \frac{k-1}{k}\frac{\binom{m-1}{k-1}}{\binom{n}{k}} &\text{if } n \ge m \end{cases}

이 분포의 기대값을 계산해보자. n 곱해서 무한히 더하면 된다. 즉,

\displaystyle \begin{aligned} E(N) & = \sum_{n=m}^{\infty}n\frac{k-1}{k}\frac{\binom{m-1}{k-1}}{\binom{n}{k}} \\ & = \frac{k-1}{k}\binom{m-1}{k-1} \sum_{n=m}^{\infty} \frac{1}{\frac{1}{n}\binom{n}{k}} \\ & = \frac{k-1}{k}\binom{m-1}{k-1} \sum_{n=m}^{\infty} \frac{1}{\frac{1}{k}\binom{n-1}{k-1}} \\ & = \frac{(k-1)^2}{k-2}\frac{\binom{m-1}{k-1}}{\binom{m-2}{k-2}} \\ & = \frac{(m-1)(k-1)}{k-2} \end{aligned}

를 얻는다. 막판에 위 partial fraction을 또 썼다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중