정직한 가차 시스템에게 기대함
29/10/2015
밥을 먹다가 누군가 요즘 모바일 게임에서는 대부분의 아이템이 가차 로 불리는 시스템을 사용하기 때문에 쓸만한 장비 풀 세트를 갖추기 위해서 최소한 어느 정도 이상의 금액은 결제해야한다 라는 이야기를 했다. 그 이야기를 들으면서 전체 종류가 n 개인 아이템이 있으며 구매 시 완전히 랜덤으로 배송될 때 모든 종류를 다 얻기 위해서 평균적으로 몇 번을 반복 구매해야 하는지가 궁금해졌다.
전체 \( n \)개 중 \( i \)종류의 아이템을 가지고 있다고 하면 \( \frac{i}{n} \)의 확률로 이미 가지고 있는 아이템을 얻고 나머지 \( \frac{n-i}{n} \)가 가지고 있는 종류가 아닌 아이템을 얻는다.
따라서 \( j \)번째 구매후에야 기존에 없던 아이템을 얻을 확률은 \( {(\frac{i}{n})}^{j-1}\frac{n-i}{n} \)가 된다. 그러므로 \( j \)번째 구매에서 다시 새로운 종류를 얻기 위한 구매 횟수의 기대값은 \( \sum_{j>=1}{(\frac{i}{n})}^{j-1}(\frac{n-i}{n}) j \)이다. 그런데
\( \sum_{j \geq 1}{(\frac{i}{n})}^{j-1}(\frac{n-i}{n}) j
\)
\( = \sum_{j \geq 1}{(\frac{i}{n})}^{j-1}( 1 - \frac{i}{n}) j
\)
\( = \sum_{j \geq 1}{(\frac{i}{n})}^{j-1} j - \sum_{j \geq 1}{(\frac{i}{n})}^{j} j
\)
이고 \( j-1 = k \) 라 하면
\( \sum_{k \geq 0}{(\frac{i}{n})}^{k} (k+1) - \sum_{j \geq 1}{(\frac{i}{n})}^{j} j
\)
\( = \sum_{k \geq 0}{(\frac{i}{n})}^{k} k + \sum_{k \geq 0}{(\frac{i}{n})}^{k} - \sum_{j \geq 1}{(\frac{i}{n})}^{j} j
\)
\( = 0 + \sum_{k \geq 1}{(\frac{i}{n})}^{k} k + \sum_{k \geq 0}{(\frac{i}{n})}^{k} \)
\( - \sum_{j \geq 1}{(\frac{i}{n})}^{j} j
\)
\( = \sum_{k \geq 0}{(\frac{i}{n})}^{k}
\)
\( = \frac{1}{ 1 - \frac{i}{n} }
\)
\( = \frac{n}{n-i}
\) 가 된다.
따라서 \( j \)번째 구매후에야 기존에 없던 아이템을 얻을 확률은 \( {(\frac{i}{n})}^{j-1}\frac{n-i}{n} \)가 된다. 그러므로 \( j \)번째 구매에서 다시 새로운 종류를 얻기 위한 구매 횟수의 기대값은 \( \sum_{j>=1}{(\frac{i}{n})}^{j-1}(\frac{n-i}{n}) j \)이다. 그런데
\( \sum_{j \geq 1}{(\frac{i}{n})}^{j-1}(\frac{n-i}{n}) j
\)
\( = \sum_{j \geq 1}{(\frac{i}{n})}^{j-1}( 1 - \frac{i}{n}) j
\)
\( = \sum_{j \geq 1}{(\frac{i}{n})}^{j-1} j - \sum_{j \geq 1}{(\frac{i}{n})}^{j} j
\)
이고 \( j-1 = k \) 라 하면
\( \sum_{k \geq 0}{(\frac{i}{n})}^{k} (k+1) - \sum_{j \geq 1}{(\frac{i}{n})}^{j} j
\)
\( = \sum_{k \geq 0}{(\frac{i}{n})}^{k} k + \sum_{k \geq 0}{(\frac{i}{n})}^{k} - \sum_{j \geq 1}{(\frac{i}{n})}^{j} j
\)
\( = 0 + \sum_{k \geq 1}{(\frac{i}{n})}^{k} k + \sum_{k \geq 0}{(\frac{i}{n})}^{k} \)
\( - \sum_{j \geq 1}{(\frac{i}{n})}^{j} j
\)
\( = \sum_{k \geq 0}{(\frac{i}{n})}^{k}
\)
\( = \frac{1}{ 1 - \frac{i}{n} }
\)
\( = \frac{n}{n-i}
\) 가 된다.
이제 전체 종류를 모두 구하기 위해 필요한 구매 수의 기대값은 위에서 구한 각각의 구매 기대값의 합 이므로
\( \sum_{i=0}^{n-1} \frac{n}{n-i}
\)
\( = n\sum_{i=0}^{n-1} \frac{1}{n-i} \)
\( = n( \frac{1}{n} + \frac{1}{n-1} + \frac{1}{n-2} \ldots + 1)
\)
\( = n H_{n} \) 단 \( H_{n} \) 은 조화급수
\( \sum_{i=0}^{n-1} \frac{n}{n-i}
\)
\( = n\sum_{i=0}^{n-1} \frac{1}{n-i} \)
\( = n( \frac{1}{n} + \frac{1}{n-1} + \frac{1}{n-2} \ldots + 1)
\)
\( = n H_{n} \) 단 \( H_{n} \) 은 조화급수
그런데 조화급수 \( H_{n} \) 은 \( \log n \) 으로 어림지워지므로 결국 \( \frac{1}{n} \) 의 확률로 나오는 서로 다른 아이템 n 개를 얻기 위해서는 평균적으로 \( n\log n \) 번 구매를 반복할 필요가 있다.
정말 그런지 실재 랜덤신의 가호를 받아 처리해 보자
아래는 카드의 종류를 \( n \)을 10부터 1000까지 변경하면서 시뮬레이션하는 코드이다.
아래는 카드의 종류를 \( n \)을 10부터 1000까지 변경하면서 시뮬레이션하는 코드이다.
#!/usr/bin/perl
use strict;
use warnings;
my %n_count_hash = ();
foreach my $n ( (10..1000) ){
my %n_hash = ();
foreach ( (1..$n) ){
$n_hash{$_} = 1;
}
my $count = 0;
while( scalar(keys %n_hash) ){
my $current = int(rand($n))+1;
delete($n_hash{$current});
$count ++;
}
$n_count_hash{$n} = $count;
}
foreach ( sort {$a<=>$b} keys %n_count_hash ){
printf "% 4d % 8d\n"
, $_, $n_count_hash{$_};
}
(조화급수가 \( \log n \) 로 어림지워지는 이야기는 나중에.)