확률론 [Coupon Collector 문제] [보편성(universality)] [선형성(linearity)]

Coupon Collector 문제

n 가지 장난감을 모아야 전체를 모은다고 할 때,

장난감 전부를 모으는 데까지 걸리는 시간 

T(뽑아야 하는 장난감 수)의 기댓값을 구하시오

 

n 종류 

각각의 장난감을 구분하기 위함이죠

나올 확률이 모두 같다고 합시다.

 

얼마나 많은 장난감을 사야하는지에 대한 척도가 될것이다. 

모든 종류의 장난감을 모으기 위한 척도

 

 

T (뽑아야 하는 장난감 수)

 

T1= 첫번 째에 이전에 가지고 있지 않았던 장난감을 모으는데 걸리는 시간

T2= 새로운 두번째 장난감이 나올 때까지 걸린 추가 시간

T3= 새로운 세번째 장난감이 나올 때까지 걸린 추가 시간

 

T2-1 ~ Geom(n-1/n)

Tj -1 ~ Geom(n-(j-1)/n)

 

위의 경우에 위의 T들은 독립이지만 

선형성은 이들이 독립이 아니어도 성립할거에요 

두 번째 새로운 장난감을 얻는데 걸린시간 같은것인데 

이건 추가적으로 얼마의 시간이 걸렸는지와는 상관이 없기 때문입니다.

하지만 이들이 독립이 아니더라도 아래와 같은 식은 성립합니다.

 

E(T) = E(T1) + ... E(Tn)

=1 + n/(n-1) + n/(n-2) + ... + n/1 = n(1+1/2+...+1/n)

=n(1+1/2+1/3+....1/n) ==>조화급수

 

조화급수는 로그로 근사할 수 있다는것이죠

 

충분히 n이 크다면 nlogn으로 근사할 수 있습니다.

 

균등의 보편성

x축 위의 점을 랜덤하게 고른다고 해봅시다

X ~ F 라고 할 때 

X는 확률변수이고 F는 누적분포함수라고 했을 때

X를 자신의 누적분포함수에 집어 넣으면 균등분포를 얻게 될 것입니다.

 

F(x0)=1/3

P(F(X)<=1/3)

=P(X<=x0)

=F(x0)=1/3

 

==> 균등분포가 된다. 

균등분포는 확률과 길이가 비례한다고 했었죠

 

Unif(0,1)에 대해서는 

확률이 길이와 같게 되는겁니다.

0과 1 사이에서 말이죠

 

F(X)~Unif(0,1)

 

이를 기하학적으로 이야기하면 

x축 위의 임의의 점과

0과 1 사이의 임의의 수를 고르는 것을 연관짓는 것입니다.

 

로지스틱 분포

누적분포함수를 갖는데

모든 실수 x에 대하여 F(x) = eˣ / (1 + eˣ)입니다.

 

시뮬레이션을 위해서 U ~ Unif(0,1)이라고 하고

F^-1(U)를 생각해보면 

이를 U와 같다고 하고 

이를 x에 대해서 나타낸 U라고 하면 

이를 풀어내서 역으로 나타내면

U에 대해 나타낸 x를 구할 수 있습니다.

 

F^-1(u)=log(u-(1-u)) ~ logistic

 

대칭성과 선형성

X,Y,Z를 독립적이고 같은 분포를 따르는 양의 확률 변수라고 했을 떄

확률 변수끼리의 선형성이 적용이 될까?

 

대칭성이란 무엇인가?

완전히 대칭이라면 

이들이 독립이고 같은 분포를 갖기 때문입니다

X와 Y가 같다는것이 아닙니다.

어떤 문제든 구조가 같다는 것을 말하고 있는 것입니다.

대칭성에 의해 같아야만 하죠