'확률 통계'에 해당되는 글 1건

  1. 2010.03.22 윷놀이에 대한 수학적, 물리학적 고찰
물리2010.03.22 18:23

학부 통계물리시간에 교수님께서 재밋는 이야기를 해주시면서 다음과 같은 문제에 도전해 보라고 이야기 하셨습니다. 다름이 아닌 윷놀이에 대한 것인데요. 

 

윷이 뒤집어진 경우에는 \cup 이런 모양일거고, 실험적으로 확률은 0.6 정도 된다고 하네요. 반대로 덥혀있는 모양 \cap 인 경우에는 0.4 정도의 확률을 가진다고 합니다. 이때 교수님이 제시한 문제는 다름아닌 윷 놀이를 할때 한번 던졌을때 말이 전진하는 기대값이 얼마냐는 것입니다. (계산이 너무 복잡해지는 것을 막기위해 빽도는 빼는걸로 합니다. )

자.. 언듯 보면 쉬운 문제지만.. 아주 어려움 부분은 모나 윷이 나오면 한번 더 던질 수 있다는 것입니다. 이게 정말 문제를 급격하게 어렵게 만듭니다. 이것때문에 뭔가 풀릴듯 안풀릴듯 하는 느낌 때문에 밤늦도록 잠도 못 자보건 오랜만에 일이었습니다. 슬슬 풀이로 넘어가 보도록 하죠. 우선 제가 풀었던 방법이 있는데 기발하긴 했으나 깔끔하지 않았고 '모'에서 한번 더 던지는 부분이 오류가 심해서 그냥 버리도록 하죠.(뭔가 아깝네요..ㅠ_ㅠ) 우선 교수님의 솔루션입니다.

 

각각의 수들을 인덱스 형태로 나타내 보도록 하죠. 

a_1=1 \\ a_2=2 \\ a_3=3 \\ b_4=4 \\ b_5=5

 

우선 a, b는 말이 나왔을때 움직일수 있는 거리입니다. 도, 개, 걸, 윷, 모 라고 하죠. 윳과 모는 한번 더 던질때 계산이 달라지기 때문에 b라고 표기 했습니다. 다음으로

P_1=\phantom{}_{4} C_{0}(0.4)^4 \\ P_2=\phantom{}_{4} C_{1}(0.4)^3 (0.6) \\ P_3=\phantom{}_{4} C_{2}(0.4)^2(0.6)^2 \\ P_4=\phantom{}_{4} C_{3}(0.4)(0.6)^3 \\ P_5=\phantom{}_{4} C_{4}(0.6)^4

의 확률값을 가지게 됨니다. 이것은 마치 

(0.4+0.6)^4

의 각항들을 표시해놓은 것이라고 할수 있죠. 

 

그렇다면 윷을 한번만 던질때 기대값은 얼마일까요?

(0) \ \ \ a_1P_1+a_2P_2+a_3P_3

대충 이런 느낌이 되네요. 두번은

(1) \ \ \ (a_1+b_4)P_1P_4+(a_2+b_4)P_2P_4+(a_3+b_4)P_3P_4\ (a_1+b_5)P_1P_5+(a_2+b_5)P_2P_5+(a_3+b_5)P_3P_5

이런식의 두가지 형태를 가지게 됨니다. 한번은 윷이 

(2) \ \ \ (a_1+2b_4)P_1P_4^2+(a_2+2b_4)P_2P_4^2+(a_3+2b_4)P_3P_4^2\\ (a_1+2b_5)P_1P_5^2+(a_2+2b_5)P_2P_5^2+(a_3+2b_5)P_3P_5^2 \\2\left[(a_1+b_4+b_5)P_1P_4P_5\right]+2\left[(a_2+b_4+b_5)P_2P_4P_5\right]+2\left[(a_3+b_4+b_5)P_3P_4P_5\right]

세번 던질때는 이런 기대값을 따르겠네요. 미리 이야기 하는 것이지만 각 줄들을 다 합해야 기대값이 됨니다. 그리고 (2)에서 마지막 줄에서는 윷이 먼저 나올수도 있고 모가 먼저 나올수도 있기때문에 저런식으로 표시했습니다. 

벌써부터 보며서 조금씩 규칙성을 찻을수 있네요. 

인덱스 1,2,3 은 따로 빼보도록 하죠.

(2) \ \ \ \sum_{i=1}^{3}(a_i+2b_4)P_iP_4^2\\ +\sum_{i=1}^{3}(a_i+2b_5)P_iP_5^2\ +2\sum_{i=1}^{3}\left[(a_i+b_4+b_5)P_iP_4P_5\right]
많이 간단한 모양이 됬네요. 

이항 전개방식으로 바꾸어 보도록 하죠. 우선 a 와 b부분을 분리해보도록 합시다. 

(2) \ \ \ \sum_{i=1}^{3}a_i P_i P_4^2+\sum_{i=1}^{3}2b_4 P_iP_4^2\\ +\sum_{i=1}^{3}a_iP_iP_5^2+\sum_{i=1}^{3}2b_5P_iP_5^2\ +\sum_{i=1}^{3}2a_iP_iP_4P_5+\sum_{i=1}^{3}2b_4P_iP_4P_5+\sum_{i=1}^{3}2b_5P_iP_4P_5\right]

이향 전개 형식으로 묶습니다. 

(2) \ \ \ \sum_{i=1}^{3}a_i P_i (P_4+P_5)^2 +\sum_{i=1}^{3}P_i(b_4P_4+b_5P_5)^2
이것은 위의 식과 전혀 같지가 않습니다. 일단은 인수 분해 한다는 마음으로 묶어 준것인데, 앞에  a에 관한 항은 정확하게 맞지만 뒤의 항은 뭔가 꺼림직 하지요.

완전히 다른 것이지만.. 우선 이런식으로 써줌으로서, 좀 중간에 생각하면서 쉴 여유를 만든후에 미분이라는 개념을 도입합니다. 

(2) \ \ \ \sum_{i=1}^{3}a_i P_i (P_4+P_5)^2 +\frac{\partial}{\partial b_4}\sum_{i=1}^{3}P_i(b_4P_4+b_5P_5)^2 +\frac{\partial}{\partial b_5}\sum_{i=1}^{3}P_i(b_4P_4+b_5P_5)^2
네.. 위를 전개해서 미분하면 분명히 전전식의 결과와 완벽하게 일치 합니다. 2차 이상의 항에서도 이와 같을가요?

글을 읽는 사람들은 누구나 의심해보는 일이지만 직접해보면 완벽하게 같다는 것을 알수 있습니다. 
자 그럼 모든 n에 대해서 합을 해보도록 합시다.

\sum_{n=0}^{\infty}\sum_{i=1}^{3}\left[a_i P_i (P_4+P_5)^n +\frac{\partial}{\partial b_4}P_i(b_4P_4+b_5P_5)^n +\frac{\partial}{\partial b_5}P_i(b_4P_4+b_5P_5)^n\right]

이런 모양이 됬네요. 가장 간단한 모양입니다. 미분을 실제로 해보도록 하죠. 

\sum_{n=0}^{\infty}\sum_{i=1}^{3}\left[a_i P_i (P_4+P_5)^n +nP_iP_4(b_4P_4+b_5P_5)^{n-1} +nP_iP_5(b_4P_4+b_5P_5)^{n-1}\right]<x>=\sum_{n=0}^{\infty}\sum_{i=1}^{3}P_i\left[a_i (P_4+P_5)^n +n(P_4+P_5)(b_4P_4+b_5P_5)^{n-1} \right]

자.. 결국엔 완성이네요.. i와 n을 제외한 모든 값들은 상수 값입니다. 그리고 P들은 다 1보다 작은 값들이네요. 

하지면 여기선 문제가 하나 있습니다. 뭐나면 바로 
\sum_{n=0}^{\infty}nk^{n-1}

이런 꼴의 합이 존재하는거죠. k는 1보다 많이 작은 값이 됨니다. 하지만 결정적인 문제는 저런 급수합이 대수적(analytic)으로 풀이가 없습니다. ㅠ_ㅠ

적어도 제가 아는 중에는 풀이 방법을 모르겠는데 고수님들 혹시 아시는 분 있으시면 알려주세요~
메스메디카로 돌려본 답은 3.2759입니다. 웃긴건 항을 약간 전개해주면 2.2이 나온다는 건데요. 중간에 뭔가 알고리즘상의 하자로 인해서 값이 이상하게 나오는거 같습니다. 

다음으론 후배들이 만들어낸 아주 간단한 풀이법입니다. 수식 자체가 자기유사성(self similarity )을 가지는 플렉탈 구조이기 때문에 간단하게 풀수 있죠. 하지만 개념을 이해하기가 쉽지가 않습니다. 처음 식으로 돌아가보도록 하죠. 

여기서 \phi는 거리의 기대값<x>이라고 하죠. 

\phi=a_1P_1+a_2P_2+a_3P_3+b_4P_4\ldots+b_5P_5\ldots

딱 보면 기대값은 이런식의 값을 가지게 될것입니다. 하지만 우리는 여전히 윷이나 모가 나왔을때 어떤 일이 일어날지는 모르는거죠. 하지만 하나 확실한건 윷이나 모가 나온후에 다시 던진다는 것이고 윷이나 모가 나오면 확실하 4칸이나 5칸을 이동하는 것입니다. 그렇다면 이런식으로 바꾸어 쓸수 있습니다. 
\phi=a_1P_1+a_2P_2+a_3P_3+P_4(b_4+\phi)+P_5(b_5+\phi)

언뜻 이해가 되지 않을지도 모릅니다. 저도 이해하는데 한참 걸렸죠. 다시 한번 던칠 확률 자체가 윷과 모가 나올 확률과 동일해지는 것입니다. 그리고 다시 던지는 경우에는 확실하게 4칸이나 5칸이 진행이 되서 b옆에 확률 1이 곱해지는 것입니다. 정말 간단한 식이니 정리 해보도록 하죠.
(1-P_4-P_5)\phi=a_1P_1+a_2P_2+a_3P_3+b_4P_4+b_5P_5

\phi=\frac{a_1P_1+a_2P_2+a_3P_3+b_4P_4+b_5P_5}{1-P_4-P_5}

 

이 식의 값은 2.99242입니다. 아래 시뮬레이션한 프로그램의 값이랑 정확하게 일치하는 값이네요. 이것을 푼 메스메디카 소스도 첨부 하도록하죠.  yut(1).nb

아래 소스코드는 C로 짠 시뮬레이션 코드 입니다. 무쟈게 짧아서 좋습니다. TRY를 수정해 가면서 해보세요. 1억번은 좀 심하긴 하죠..

 

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#define TRY 100000000

 

int yut(int x);

 

int main(void)

{

        int i;

        int x=0;

        int total=0;

 

        srand(time(NULL));

 

        for(i=0; i<TRY; i++)

        {

                x=0;

                total+=yut(x);

        }

 

        printf("%lf\n", (double)(total)/(double)TRY );

 

        return 0;

}

 

int yut(int x)

{

        int i;

        int number=0;

        double direct;

 

        direct=(double)rand()/(RAND_MAX+1.0);

 

        for(i=0; i<4; i++)

        {

                if( direct > 0.4)

                {

                        number++;

                }

                direct=(double)rand()/(RAND_MAX+1.0);

        }


        if(number==0)

                x=yut(x+5);

        else if(number==4)

                x=yut(x+4);

        else if(number==1)

                x=x+1;

        else if(number==2)

                x=x+2;

        else if(number==3)

                x=x+3;


        return x;

}

 

 

이 글은 스프링노트에서 작성되었습니다.

Posted by blindfish

댓글을 달아 주세요