본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대43. 무작위로 움직이는 개미
수학동아 2020.07.01 14:11

홀수인 자연수 에 대해, 위의 왼쪽 그림과 같이 원 위에 같은 간격으로 1, 2, \cdots , n의 번호가 붙은 n개의 자리가 같은 간격으로 배치돼 있고, 개미 한마리가 처음에는 빨간색으로 표시된 1번 자리에 있다.

 

이 개미는 1초마다 자신의 양 옆자리 중 하나로 움직이는데, 시계방향으로 움직일 확률이 p, 반시계 방향으로 움직일 확률이 1-p라고 한다. (단, 0<p<1)

 

예를 들어, 1초 뒤에 2번 자리에 있을 확률이 p, n번 자리에 있을 확률이 1-p가 된다. 이때, t초 뒤에 개미가 k번 자리에 있을 확률을 p_t(k)라 하자. 예를 들어

 

p_0(1)=1, p_1(2)=p, p_1(n)=1-p

p_2(3)=p^2, p_2(n-1)=(1-p)^2, p_2(1)=2p(1-p)

 

등이 성립한다. 이때, 다음 물음에 답하여라. 

 

 

문제 1 임의의 1이상 n이하의 자연수 k에 대해 \lim_{t\rightarrow \infty } p_t(k)=\frac{1}{n}임을 증명하라. 

 

 

문제 2 음이 아닌 정수 t에 대해 d(t)를 다음과 같이 정의하자. 

 

d(t)=\sum_{k=1}^{n}\left | p_t(k)-\frac{1}{n} \right |

 

이때, d(t)<\frac{1}{2020^{2020}}이 되는 최소의 tt_0이라 하자. t_0은 n에 따라 다른 값을 가지므로 n에 대한 함수로 생각해도 무방하다. 따라서 t_0을 t_0(n)이라 쓰자. 

 

p=\frac{1}{2}라 하자. 이때, 어떤 상수 c_1, c_2가 존재해 모든 홀수인 자연수 n에 대해 다음이 성립하게 함을 증명하라.

 

c_1n^2\leq t_0(n)\leq c_2n^2

 

또한, \lim_{n\rightarrow \infty } \frac{t_0(n)}{n^2}의 값이 존재하는가? 존재한다면 이 값은 어떤 값인가?

 

 

p\neq \frac{1}{2}라 하자. 이때, 어떤 상수 c_1, c_2가 존재해 모든 홀수인 자연수 n에 대해 다음이 성립하게 함을 증명하라.

 

c_1n\leq t_0(n)\leq c_2n

 

또한, \lim_{n\rightarrow \infty } \frac{t_0(n)}{n}의 값이 존재하는가? 존재한다면 이 값은 어떤 값인가?

 

 

 

문제 3 위의 오른쪽 그림처럼, 개미가 한 번에 두 칸씩도 움직일 수 있다고 하자. 이때, 시계방향으로 한 칸 또는 두 칸을 움직일 확률이 p, 반시계 방향으로 한 칸 또는 두 칸을 움직일 확률이 1-p라 하자. 이때, 앞선 문제 1, 2의 질문에 답하라. 

 

 

 

문제 4 위의 오른쪽 그림에서, 개미가 시계방향으로 두 칸, 시계방향으로 한 칸, 반시계 방향으로 한 칸, 반시계 방향으로 두 칸 갈 확률이 각각 p, q, r, s (단, p+q+r+s=1)이라 할 때, 앞선 1, 2번 질문에 답하라. 특히 문제 2에서 ①과 ②를 나누는 기준이 무엇이 되는지 생각해 보라. 

 

 

 

  •  
    방유찬 Lv.1 2020.07.01 14:34 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    다시 도전
    여백 패르마 Lv.5 2020.07.03 16:56

    댓글 작성하기 좋아요0 댓글수8
    •  
      여백 패르마 Lv.5 2020.07.03 16:57

      1번풀이입니다

      좋아요0
    •  
      Sait2000 Lv.2 2020.07.03 20:38

      잔소리같지만 수렴한단 보장이 없습니다.

      예를 들어 문제의 조건 상 불가능하지만 n이 짝수이던가 p = 0 또는 p = 1인 경우에는 수렴하지 않는 걸 보면

      문제의 조건을 이용해서 수렴함을 보일 필요가 있을 것 같습니다.

      좋아요0
    •  
      무한대의끝을본남자 Lv.7 2020.07.05 12:22

      기분나쁘신다면 죄송하지만

      너무 복잡하게 푸신것같네요 ㅇㅅㅇ

      좋아요0
    •  
      여백 패르마 Lv.5 2020.07.05 20:52

      아...수렴성 증명을 해야 하네요...

      좋아요0
    •  
      여백 패르마 Lv.5 2020.07.05 21:30

      수렴성 증명을 했습니다!! 근디 n=짝수일 때도 포함하네요... 원래 그런 것 같은데,, 

      어떤 자연수 N에 대해 \forall 1\leq k\leq n  \left | p_N(k)-\frac{1}{n} \right |\leq \epsilon이 성립한다고 하자. 이때 t>N인 자연수 t를 고려하면, 

      \forall 1\leq k\leq n  p_t(k)=p\cdot p_{t-1}(k-1)+(1-p)\cdot p_{t-1}(k+1)이므로, 

      Min[p_{t-1}(k-1,p_{t-1}(k+1))]\leq p_t(k)\leq Max[p_{t-1}(k-1),p_{t-1}(k+1)]임을 알 수 있다. 

      결론적으로, 수학적 귀납법을 반복적으로 사용하면 \frac{1}{n}-\epsilon \leq p_{t}(k)\leq \frac{1}{n}+\epsilon이 성립하게 된다. 

      <증명 끝>

      좋아요0
    •  
      리프 Lv.6 2020.07.05 21:56

      증명을 아직 읽진 않았지만 n이 짝수면 기우성 때문에 홀수칸과 짝수칸에 동시에 존재할 수 없는데요?

      좋아요0
    •  
      리프 Lv.6 2020.07.05 22:00

      '어떤 자연수 N에 대해 \forall 1\leq k\leq n  \left | p_N(k)-\frac{1}{n} \right |\leq \epsilon이 성립한다고 하자.' 에서

      이러한 자연수 N이 반드시 존재한다는 근거가 부족한듯 합니다. 애초에 이러한 N을 잡는게 수렴성 증명 아닌가요?

      좋아요0
    •  
      최기자 Lv.4 2020.10.20 22:53

      답변이 늦어서 미안합니다..ㅠ

       

      김다인 멘토의 피드백이에요. p_k(t)이 수렴한다는 증명에서, "어떤 자연수 N에 대해 [모든 k에 대해서] |p_N(k)-1/n| <= epsilon이 성립한다고 해주셨는데 이런 N을 일반적으로 잡을 수 없다고 합니다.

      좋아요0
  •  
    다시 도전
    파스칼 Lv.6 2020.07.04 00:42

    우선 1,2번의 경우를 더 간결하게 만들어 보겠습니다(꼭 필요한 단계는 아닙니다)

    개미가 한 번 이동할 때마다 번호를 시계방향으로 2에는 1, 3에는 2, 4에는 3, ...으로 다시 붙인다고 생각하면 문제에서 개미가 시계방향으로 p, 반시계방향으로 1-p 대신 제자리에 p, 반시계방향으로 두 칸을 1-p의 확률로 간다고 생각해도 관계없다는 것을 알 수 있습니다. 또한 n이 홀수임에서, 번호를 재배치하면 제자리에 p, 반시계방향으로 한 칸을 1-p의 확률로 가는 것으로 문제를 바꿀 수 있습니다.

    이제 1번 문제를 풀어보겠습니다.

    0<p<1이며 p_{t+1}(k)=p^tp_1(k)+(1-p)^1p^{t-1}p_1(k+1)+(1-p)^2p^{t-2}p_1(k+2)+(1-p)^3p^{t-3}p_1(k+3)+...+(1-p)^tp_1(k+t)므로, t>n일 때 모든 k에 대해 p_t(k)\geq min(p,1-p)^t> 0이 됩니다. 이때 최소의 p_t(k)를 k_0라고 하면 모든 p_t(k)에서 k_0를 빼어도, 모든 p_t(k)에서 k_0은 더 이상 이동하지 않는 것이나 마찬가지이므로 이후의 상대적인 개미가 존재할 확률의 변화량에 영향을 미치지 않습니다. 이렇게 하면 다시 일부 p_t(k)가 0이 되었으며, 모든 p_t(k)가 같은 값을 가지지만 않았다면 p_t(k)들의 총합은 여전히 0보다 큽니다. 다시 전체를 1이라 생각하고 t에 n만큼을 더하면 모든 k에 대해 p_t(k)\geq min(p,1-p)^n> 0이 되며, 여기서 다시 모든 p_t(k)에서 최소의 p_t(k)를 빼내는 과정을 반복하면 확률이 변하는 부분의 총 확률이 매번 일정한 비율 이상으로 줄어드므로 결과적으로 모든 p_t(k)가 같은 값으로 수렴하게 되고, 따라서 \lim_{t\rightarrow \infty } p_t(k)=\frac{1}{n}입니다.

    댓글 작성하기 좋아요0 댓글수5
    •  
      리프 Lv.6 2020.07.05 18:26

      모든 p_t(k)에서 k_0를 빼는 시행이 이해가 되지 않네요... 수식으로 정리해서 좀 더 자세히 설명해주실 수 있나요?

      좋아요0
    •  
      파스칼 Lv.6 2020.07.06 00:05

      각 공간에 개미가 존재할 확률을 보면, 모든 곳에서의 확률을 k_0+q_t(k)로 나타낼 수 있습니다. 이 확률이 확률 p로 그곳에 남아 있고, 확률 1-p로 시계 반대방향으로 한 칸 이동하는 것입니다. 그런데 k_0는 모든 곳에 이미 존재하는 확률이므로, k_0으로 인한 확률의 변화는 커지는 양과 작아지는 양이 같아 영향을 미치지 않습니다. 즉 k_0의 확률은 확률 1로 멈춰 있고 나머지 부분인 q_t(k)만 확률 1-p로 이동한다고 생각해도 무관합니다. 그래서 저는 이렇게 '전체에 퍼져서 더 이상 이동하지 않는' 부분을 계속 제외했습니다. 그리고 t를 계속 n씩 더할 때 이런 이동하지 않는 부분을 제외한 부분, 즉 위에서는 q_t(k)의 총합이 계속 일정한 비율로 줄어든다는 것을 보였습니다. 그래서 t가 무한히 커지면 q_t(k)의 총합이 0에 가까워짐이 증명되었으므로, 결과적으로 모든 곳에 k_0, 즉 균일하게 퍼져서 더는 영향을 미치지 못하는 확률만이 남게 됩니다. 이 확률은 모든 곳에 균일하게 퍼졌으므로 모든 곳에서 1/n이 됩니다.

      대충 위와 같은 아이디어로 증명했는데.. 엄밀성이 떨어지는 부분이 있다면 말씀해주세요

      좋아요0
    •  
      구머 Lv.5 2020.07.06 00:17

      질문1. 

      p_{t+1}(k)=p^t p_1(k)+ _tC_1 (1-p)p^{t-1}p_1(k+1)+...................처럼 확률 계산 시 이항분포식을 활용하는 게 일반적인 듯 합니다.

       

      질문2.

      두 칸 가는 것을 한 칸으로 바꾼.....건 상관이 없네요

       

      질문3.

      p_t(k)에서 k_0를 뺀다는게 구체적으로 무슨 의미인가요?

      좋아요0
    •  
      파스칼 Lv.6 2020.07.06 23:03

      1. 그렇네요. 제가 잘못 생각한 것 같습니다. 그러나 모든 \binom{a}{b}는 1 이상이므로 이후의 논증에는 문제가 없어 보입니다.

      2. 상관은 없다고 하셨으나 이후에 제가 쓸 아이디어일 수도 있으므로 아이디어에 대한 설명을 하겠습니다.

      시계 반대방향으로 두 칸 이동한 곳으로 가게 되는 홀수 개의 원이 있을 때, 1을 고정하고 1에서 시계 반대방향으로 붙어있는 곳에 n-1을, 그 다음에 시계 방향으로 붙어있는 곳에 n-3을, 이런 식으로 1바로 시계방향에 3이 올 때까지 원들을 배치합니다. 원들이 홀수 개였으므로 모든 원들을 정확히 한 번씩만 배치하게 됩니다. 이렇게 배치를 바꾸는 아이디어를 생각하면 처음부터 시계 반대방향으로 한 칸씩 이동하는 것으로 생각할 수 있습니다.

      3. 예를 들자면 그림처럼 바꾸는 것입니다.

      이렇게 '전체에 고르게 퍼진 확률'은 원들에서 개미가 존재할 확률 변화에 더 이상 영향을 끼치지 않으므로 따로 분리한 것입니다.

      저는 매번 t에 n씩 더할 때마다 전체에서 일정량 이상의 비율을 차지하는 부분이 이런 '고르게 퍼진 확률'로 빠진다는 것을 증명함으로써 결과적으로 전체에 고르게 분배된 확률이 1로 수렴하여 모든 곳에 개미가 존재할 확률이 같아진다는 아이디어를 사용한 것입니다.

      틀린 부분이 있다면 또 알려주시기 바랍니다.

      좋아요0
    •  
      최기자 Lv.4 2020.10.20 22:54

      답변이 늦어서 미안합니다..

       

      김다인 멘토의 피드백은 다음과 같아요.

      "번호를 재배치"하는 것은 주의해야할 시행으로 보입니다. p_k(t)의  정의가 "k"라는 번호의 위치에 t번의 시행 후 오게 될 확률인데, 번호를 재배치하면 p_k(t)의 정의도 바뀌겠죠?p_1(k), p_1(k+t)<=1이기 때문에 바로 p_t(k) >min(p,1-p)^t라고 결론지을 수 없는 것으로 보입니다. 혹시 중간 과정이 있을까요?^^
       

      좋아요0
  •  
    무한대의끝을본남자 Lv.7 2020.07.05 12:14

    상한이랑 하한을 이용하면 수렴함을 보일수있습니다 어느 수열이 단조감소수열이면서 아래로 유계이면

    무조건 수렴하죠

     

    이것이 단조감소수열이아니라면... 진동할 가능성이 크겠죠?

    물론 위로 유계이면서 단조증가수열이여도 수렴하고요

     

     

    해석학을 보시면 나와있습니다

    댓글 작성하기 좋아요0 댓글수1
    •  
      무한대의끝을본남자 Lv.7 2020.07.05 12:15

      갑자기 리만적분의 정의를 이용하면되겠다는 느낌적인느낌이

      좋아요0
  •  
    다시 도전
    무한대의끝을본남자 Lv.7 2020.07.05 12:29

    1번풀이

    t는 일종의 "시도횟수"와 같은것으로본다

    이유는 1초를 x번 시도로도 볼 수 있기 때문이다

     

    자 그러면 일단

    시계방향으로 이동할확률은 p이므로 반시계방향으로 이동하는것을 i, k로 가정하자

    시도횟수... 시도횟수란 무서운것이다

    시도가 무한번이 된다면

    0에 수렴하는 확률도 이룰수있는것이다

    1-p >0이므로 무한이면 적어도 한번은 이루어질수있는 확률이다

    확률은 시도횟수가 증가할수록늘어난다

     

    이에반해

    p인시계방향도 이루어질수있다

     

    우리는 이루어질지 안이루어질지 모른다

    시도횟수가 무한이기때문이다

    시도횟수가 무한이라서 모든확률이 무한이된다

    따라서 n번으로 갈확률은

    하나를 택하는 

    1/n과같다

    댓글 작성하기 좋아요0 댓글수4
    •  
      무한대의끝을본남자 Lv.7 2020.07.05 12:31

      확률과 통계 저서에서

       

      어느 단위 확률 P에서 시도횟수n이 교합하면 Pn이된다는 정리에대해 확률이 발산하여 모른다는 것을 표현한것입니다

      모른다는것을 바꿔말하면

      확률이 완전무작위란 뜻이죠

      따라서 1/n이됩니다

      이런 확률이아닌

      어떤확률도 시도횟수가 무한이되면 1/n이됩니다

      좋아요0
    •  
      리프 Lv.6 2020.07.05 18:28

      이건 너무 직관적인 풀이고 엄밀하지가 않습니다. 또한 님의 풀이의 논리를 그대로 따라가면 n이 짝수인 경우에도 확률이 1/n이 되버리므로 풀이를 좀 더 보완할 필요가 있습니다.

      좋아요0
    •  
      구머 Lv.5 2020.07.06 00:05

      이번엔 그래도 어느정도 풀이 이해를 할 수 있게 설명해주셨네요! 하지만 아직 직관적인 아이디어를 엄밀하게 다듬는 연습이 부족해보입니다ㅜㅜ.

       

      무끝남님 풀이에서 시도횟수가 무한할 때 왜 모든 칸이 "완전 무작위"해지는지에 대한 더 자세한 설명이 필요해보입니다.

      좋아요0
    •  
      최기자 Lv.4 2020.10.20 22:55

      김다인 멘토의 코멘트는 다음과 같습니다. 3-1번의 풀이에도 해당하는 내용이에요.

       

       "수학적인 증명"이 무엇일지 다시한번 생각해주세요^^ 수학적인 증명이란, 한줄 한줄 "엄밀하게 논리적으로" 적어가면서 결론을 도출해내는 과정입니다.
      예를들면, "시도가 무한번이 된다면 0에 수렴하는 확률도 이룰수있는것이다"에서 "무한번"의 정의는 무엇일까요? 또 이 명제는 왜 성립할까요? 좀 더 차분하게 생각해서 다시 풀이를 가져오길 기대할게요~!
       

      좋아요0
  •  
    다시 도전
    무한대의끝을본남자 Lv.7 2020.07.05 12:37

    문제 3번에 1번문제 풀이입니다

    1번 또는 2번이라는 조건은 또는이므로 합의 법칙을 써보자

    시계방향으로 1번또는 2번으로 움직일확률은 p이다

    그러면 1번으로 움직일확률은 p*0.5, 2번은 p*0.5이다

     

    또 반시계방향도

    (1-p)*0.5, (1-p)*0.5

    이다

     

    자 이제 우리는 2칸으로만 움직인다고 가정해봅시다 

    그러면 짝수입니다

    따라서 무한대로 수렴하게되면

    0과 2/n의 확률이 생깁니다

    (0의 의미는 홀수번째 k가 될 확률)

    허허... 진동하네요

     

    글면 이가정에서 1번은 틀리겠죠?

     

    댓글 작성하기 좋아요0 댓글수1
  •  
    다시 도전
    무한대의끝을본남자 Lv.7 2020.07.05 12:41

    문제 3번에 1번문제 풀이입니다

    1번 또는 2번이라는 조건은 또는이므로 합의 법칙을 써보자

    시계방향으로 1번또는 2번으로 움직일확률은 p이다

    그러면 1번으로 움직일확률은 p*0.5, 2번은 p*0.5이다

     

    또 반시계방향도

    (1-p)*0.5, (1-p)*0.5

    이다

     

    자 이제 우리는 2칸으로만 움직인다고 가정해봅시다 

    그러면 짝수입니다

    따라서 무한대로 수렴하게되면

    0과 2/n의 확률이 생깁니다

    0이확률일 확률은 또 0.5이다

    그리고 1만하면

     

    1/n이됩니다

     

    그런데

     

    1/n에 다른 P가 붙으니

    당연히 1/n이되는것은 안되겠지요

     

     

    댓글 작성하기 좋아요0 댓글수1
    •  
      구머 Lv.5 2020.07.06 00:08

      이건 또 살짝 이해가 안되네요ㅜㅜ

       

      2칸으로만 움직일 때 짝수 칸만큼 움직이게 된다고 가정을 하셨는데, 애초에 n이 홀수라 짝수칸만큼 움직여도 짝수칸과 홀수칸 모두 도달할 수 있게 됩니다! 따라서 무끝남님 1번 풀이와 상황이 크게 달라지지가 않고, 아마 모든칸이 다 1/n 확률을 가지게 될 것 같네요

      좋아요0
  •  
    여백 패르마 Lv.5 2020.07.05 21:14

    혹시 n이 짝수일 때 수렴하지 않는 이유를 말해주실 수 있으신가요? (자명히 n이 2일 때 말고) 

    제 생각으로는 n의 기우성을 준 이유가 그렇게 해야만 p_t(k)의 실행에서 오른쪽으로 가는 횟수가 mod n에 대해 자동결정이 되기 때문인 것 같습니다. 

    댓글 작성하기 좋아요0 댓글수2
    •  
      리프 Lv.6 2020.07.05 21:58

      수렴 안하는게 아니라 특정 칸들은 확률이 0이고 나머지는 수렴 할 것 같네요. v_2(n)의 값에 따라 그건 달라질듯 합니다. (예를 들어 칸이 10개면 10번 이동해서 짝수칸에 갈 수 없잖아요)

       

      수정) 1개의 칸 기준으로 보면 0과 어떤 양수 값이 반복적으로 나오면서 진동하게 되지만 전체적으로 봤을 때 특정 칸들만 0이고 0이 아닌 위치의 확률이 특정 값에 수렴한다는 의미입니다.

      좋아요0
    •  
      무한대의끝을본남자 Lv.7 2020.07.06 13:07

      아마 진동하기 때문일겁니다

       

      짝수조건일때는 n이 홀수부분에선 확률이 0이되기떄문이죠

      좋아요0
  •  
    구머 Lv.5 2020.07.06 00:24

    1번은 직관적으로 봤을 때도 쉽게 납득이 되는 만큼, 다양한 방식의 증명이 있을 것 같습니다. 그 중에서도 제가 생각한 방법을 설명하자면...

     

    우선 p_t(k)의 값을 정확하게 유도해낼 수 있다는 점에 주목을 합시다. 구체적으로는, t번의 자리 이동 후 개미가 k에 있을 경우의 수를 모두 고려하자는 겁니다. 시계방향으로 이동한 횟수를 x, 반시계방향으로 이동한 횟수를 t-x라고 하면, (x, t-x)의 조합으로 가능한 조합은 쉽게 구할 수 있습니다. 이후에 저희가 할 것은 그저 각각의 경우들이 발생할 확률을 다 더한 후에, 이것이 1/n에 수렴하는지를 증명하면 됩니다. 실제로 계산을 해보진 않았지만 아마 그렇게 고된 계산이 필요할 것 같진 않고, 2번을 풀때도 나름 도움이 될 아이디어인 것 같습니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      리프 Lv.6 2020.07.06 21:55

      저도 처음에 그 방식으로 접근하려고 했는데 식을 정리하기가 되게 힘들더라구요... 2번을 풀기 위해서는 식 정리가 필요할 것 같은데 막막하네요 ㅠ

      좋아요0
  •  
    리프 Lv.6 2020.07.06 22:16

    어떤 형태로 1/n에 수렴하는지 알아보기 위해 f(x)=p_x(4) (n=11)라고 정의한 후, desmos를 이용하여 y=f(x)-1/11의 그래프를 그려봤습니다.

     

    그래프는 다음 식을 이용하여 그렸습니다.

    y=100\left ( \sum_{k=-1}^{150}\binom{\left \lfloor x \right \rfloor}{7-5\left \lfloor x \right \rfloor+11k}\left ( \frac{1}{3} \right )^{7-5\left \lfloor x \right \rfloor+11k} \left ( \frac{2}{3} \right )^{-7+6\left \lfloor x \right \rfloor-11k}-\frac{1}{11}\right )

     

    그래프

     

    참고) 앞에 곱한 100은 그래프를 알아보기 쉽게 하기 위해 붙인 상수입니다. 또한, 실제로는 시그마 윗부분을 무한까지 해야하지만 desmos가 x=131까지만 이 그래프를 그릴 수 있어서 무한까지 안 해도 150이하인 어떤 수 m이후로 이항계수의 값이 0이 되면서 f(x)의 값에는 영향이 없습니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      Sait2000 Lv.2 2020.07.07 21:56

      https://sagecell.sagemath.org/?z=eJx1T0FOxDAMvEfKH-aCNoFQWiSEQOIl2WgVQUBtadbbGrRS1QfwD17GS3BaruSQGWs8Y5vwhFvc4F6rXGijVS_4oBUL3NW1VlqdhDa4BmlFk3DfBFzB1wGXMFmExmo1plUKK6siUcovhibfFz1Iw-txRIs2i72qODxqBXlbIEmS9HZrr2Sfttp0whuLC-SA4u-Kf4z5LZlsw5bwzzi5IJ3Z7OjAZl7sPpf75mWf6Q9r_Hx9g9d_XnaV5A-RTe-QHciBrYNhhyGejcyw1soy03NkTuOB3o9svG8dPrfNCivLpfwxpDFyWj3B_gK-CGGo&lang=sage&interacts=eJyLjgUAARUAuQ==

      코드를 짜왔습니다 ^^

      좋아요0
  •  
    Benedict Lv.5 2020.07.18 12:35

    음... 지금 어디까지 풀렸나요?

    댓글 작성하기 좋아요0 댓글수2
    •  
      Benedict Lv.5 2020.07.18 13:28

      수렴성만 보이면 여백 패르마님의 풀이에 따라서 1번 해결인 거죠?

      좋아요0
    •  
      리프 Lv.6 2020.07.18 17:51

      잘 모르겠네요... 1번을 풀었다고 해도 파스칼님이나 여백패르마님의 접근법은 2번 푸는데 도움이 별로 안 되는 것 같아서 2번을 풀려면 1번을 다시 새로운 방식으로 풀어야 할 듯 합니다.

      좋아요0
  •  
    Sait2000 Lv.2 2020.07.21 00:10

    아무도 행렬을 그리지 않는 현실을 믿을 수가 없어서 몇 가지 포인트를 정리해보려고 합니다.

    다들 알고 계시겠지만(?) 주어진 과정은 마르코프 연쇄입니다. 즉, 행렬로 표현할 수 있습니다.

    \begin{pmatrix} p_0(k+1)\\ p_1(k+1)\\ p_2(k+1)\\ \vdots \\ p_n(k+1) \\ \end{pmatrix} = \begin{pmatrix} 0 & 1-p & 0 & \hdots & p\\ p & 0 & 1-p & \hdots & 0\\ 0 & p & 0 & \hdots & \vdots\\ \vdots & \vdots & \vdots & \ddots & 1-p \\ 1-p & 0 & \hdots & p & 0\\ \end{pmatrix} \begin{pmatrix} p_0(k)\\ p_1(k)\\ p_2(k)\\ \vdots \\ p_n(k) \\ \end{pmatrix}

    제가 마르코프 연쇄를 잘 몰라서 오랜만에 선형대수 책을 펼쳐본 결과 regular transition matrix (정사각행렬 A의 모든 열에 대해서 각각의 합이 1이면 transition matrix라고 부릅니다. 또 그런 A 중에서 어떠한 자연수 s가 존재해 A^s의 모든 원소가 양수일 때 {즉 대충 말하면 처음에 어디에서 시작해도 s번 가면 어디에든 존재할 확률이 있을때} regular transition matrix라고 부른다고 합니다. 저도 잘 모릅니다) 이면 여러 성질이 있어서 처음 확률에 관계없이 확률이 점차 행렬의 고윳값 λ = 1에 해당하는 고유벡터로 수렴한다고 합니다. 그러니까 문제 1은 대충 되는 것 같습니다.

    그래서 문제 2번을 보면 아무튼 고윳값에 대한 감이 와야 문제를 풀 수 있을 것 같으므로 믿음을 가지고 저 방정식의 특성 다항식을 계산해보면 점화식은 그렇게 어렵지 않으므로 생략하고 뤼카 다항식 비슷한 무언가가 나옵니다. 나중에 심심하면 이 부분은 정리해 보겠습니다

    그리고 고윳값을 복소평면에 찍어보면 대략 다음과 같은 느낌으로 나옵니다. 아래는 n = 31, p = 1/4일 때의 그림입니다. 제 눈에는 아무리 봐도 unit circle에 x^n - 1의 근을 찍어놓고 짧은반지름이 |1 - 2p|가 되도록 허수축을 눌러놓은 걸로밖에 안 보이지만, 실제로 그런지는 잘 모르겠습니다.

     

    댓글 작성하기 좋아요0 댓글수0
  •  
    Sait2000 Lv.2 2020.07.21 08:33

    쓰고 나니까 latex이 깨지네요 왜??

     

    =================================================================

     

    문제 1 풀이입니다. 바로 위 댓글에서는 고윳값을 구한다고 특성다항식을 구한다음 어떻게 해보겠다는 무식한 발상을 했는데 그럴 필요가 없었습니다. 고유벡터를 간단하게 구할 수 있기 때문입니다.

     

    그리고 바로 위 댓글에서는 행렬도 조금 틀렸네요. 평소 버릇이 나와서 0부터 써버렸네요... 아무튼 다음과 같습니다.

    \begin{pmatrix} p_1(k+1)\\ p_2(k+1)\\ p_3(k+1)\\ \vdots \\ p_n(k+1) \\ \end{pmatrix} = \begin{pmatrix} 0 & 1-p & 0 & \hdots & p\\ p & 0 & 1-p & \hdots & 0\\ 0 & p & 0 & \hdots & \vdots\\ \vdots & \vdots & \vdots & \ddots & 1-p \\ 1-p & 0 & \hdots & p & 0\\ \end{pmatrix} \begin{pmatrix} p_1(k)\\ p_2(k)\\ p_3(k)\\ \vdots \\ p_n(k) \\ \end{pmatrix}

     

    이제 다음과 같은 행렬을 정의합니다. S는 shift의 s라고 생각해주세요. I_n은 n × n 단위행렬을 뜻합니다.

    S = \begin{pmatrix} 0 &\hdots &\hdots &0 &1 \\ 1& 0 & \hdots &0 &0 \\ 0& 1 & \hdots &0 &\vdots \\ \vdots &\vdots &\ddots &\vdots &\vdots \\ 0& 0 &\hdots &1 &0 \end{pmatrix} =\begin{pmatrix} O & I_1\\ I_{n-1}& O \end{pmatrix}

     

    그러면 위의 행렬은 다음과 같이 쓸 수 있습니다. 편의상 위의 행렬을 A라고 하고 q = 1 - p라고 합시다.

     

    A = pS + qS^{n-1}=pS + qS^{-1}

     

    그러면 A가 S의 다항식 꼴로 나오므로 S의 고유벡터는 A의 고유벡터가 됨을 알 수 있습니다.

     

    이제 \omega=e^{\frac{2\pi}{n}i}라고 하면 (1의 n제곱근입니다) 0 이상 n 미만의 정수 k에 대해 다음이 S의 고유벡터입니다. 즉, n개의 고유벡터를 찾았습니다.

     

    S\begin{pmatrix} \omega^0\\ \omega^k\\ \omega^2k\\ \vdots \\ \omega^{(n-1)k} \end{pmatrix}=\begin{pmatrix} \omega^{(n-1)k}\\ \omega^0\\ \omega^k\\ \vdots \\ \omega^{(n-2)k} \end{pmatrix}=\omega^{(n-1)k}\begin{pmatrix} \omega^0\\ \omega^k\\ \omega^2k\\ \vdots \\ \omega^{(n-1)k} \end{pmatrix}

     

    위의 n개의 고유벡터는 선형독립입니다. 다음이 성립하기 때문입니다. 아래의 증명은 잘 하면 될 것 같습니다. 정수론이 귀찮을 것 같긴 하지만. DFT라고 검색하면 나올지도 모릅니다.

     

    \begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^1 &\omega^2 & \hdots &\omega^{n-1} \\ \omega^0 &\omega^2 &\omega^4 & \hdots &\omega^{(n-1)2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{n-1} &\omega^{2(n-1)} & \hdots & \omega^{(n-1)(n-1)} \end{pmatrix} \begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^{n-1} &\omega^{n-2} & \hdots &\omega^{1} \\ \omega^0 &\omega^{(n-1)2} &\omega^{(n-2)2} & \hdots &\omega^{2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{(n-1)(n-1)} &\omega^{(n-2)(n-1)} & \hdots & \omega^{(n-1)} \end{pmatrix}=nI_n

     

    즉, A의 선형독립인 n개의 고유벡터를 찾았습니다. 따라서 A는 대각화할 수 있습니다. 그리고 각각의 고유벡터에 대해 고유값은 다음과 같습니다.

     

    A\begin{pmatrix} \omega^0\\ \omega^k\\ \omega^2k\\ \vdots \\ \omega^{(n-1)k} \end{pmatrix} =\left( p\omega^{-k} + q\omega^{k} \right)\begin{pmatrix} \omega^0\\ \omega^k\\ \omega^2k\\ \vdots \\ \omega^{(n-1)k} \end{pmatrix}

     

    이제 0 < k < n일때 \left|p\omega^{-k}+q\omega^k\right|<1임을 보입니다.

     

    \left|p\omega^{-k}+q\omega^k\right| \\=\left|p\left(\cos \left(k\frac{2\pi}{n}\right) - i \sin \left(k\frac{2\pi}{n}\right) \right)+q\left(\cos \left(k\frac{2\pi}{n}\right) + i \sin \left(k\frac{2\pi}{n}\right) \right)\right| \\=\left|\cos \left(k\frac{2\pi}{n}\right)+i(1-2p)\sin \left(k\frac{2\pi}{n}\right)\right| \\=\sqrt{\cos^2 \left(k\frac{2\pi}{n}\right)+(1-2p)^2\sin^2 \left(k\frac{2\pi}{n}\right)} \\\leq \sqrt{\cos^2 \left(k\frac{2\pi}{n}\right)+\sin^2 \left(k\frac{2\pi}{n}\right)}=1

     

    등호는 \sin^2 \left(k\frac{2\pi}{n}\right)=0일 때, 즉 k = 0일 때만 성립합니다. (지금의 논리에서 0 < p < 1, n은 홀수라는 점이 필요합니다)

     

    정리하면 A의 고유벡터와 고윳값은 다음과 같고, 0 < k < n일 때 |λ| < 1, k = 0일 때 λ=1입니다.

     

    A\begin{pmatrix} \omega^0\\ \omega^k\\ \omega^2k\\ \vdots \\ \omega^{(n-1)k} \end{pmatrix} =\left( p\omega^{-k} + q\omega^{k} \right)\begin{pmatrix} \omega^0\\ \omega^k\\ \omega^2k\\ \vdots \\ \omega^{(n-1)k} \end{pmatrix}

     

    이제 t = 0일 때 원래 확률을 고유벡터의 선형결합으로 표현합니다. (DFT를 할 뿐입니다만)

     

    \begin{pmatrix} c_0 \\ c_1 \\c_2 \\ \vdots \\c_{n-1} \end{pmatrix}= \frac{1}{n}\begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^{n-1} &\omega^{n-2} & \hdots &\omega^{1} \\ \omega^0 &\omega^{(n-1)2} &\omega^{(n-2)2} & \hdots &\omega^{2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{(n-1)(n-1)} &\omega^{(n-2)(n-1)} & \hdots & \omega^{(n-1)} \end{pmatrix}\begin{pmatrix} p_0(1) \\p_0(2) \\p_0(3) \\ \vdots \\p_0(n) \end{pmatrix}라고 합시다. 그러면

     

    \begin{pmatrix} p_0(1) \\p_0(2) \\p_0(3) \\ \vdots \\p_0(n) \end{pmatrix} = \begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^1 &\omega^2 & \hdots &\omega^{n-1} \\ \omega^0 &\omega^2 &\omega^4 & \hdots &\omega^{(n-1)2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{n-1} &\omega^{2(n-1)} & \hdots & \omega^{(n-1)(n-1)} \end{pmatrix}\begin{pmatrix} c_0 \\ c_1 \\c_2 \\ \vdots \\c_{n-1} \end{pmatrix}입니다.

     

    이때 c_0 = \frac{1}{n}\sum_{m=1}^{n}p_0(m)=\frac{1}{n}입니다.

     

    따라서 다음과 같습니다. \lambda_k = p\omega^{-k} + q\omega^{k}입니다.

     

    \begin{pmatrix} p_t(1) \\p_t(2) \\p_t(3) \\ \vdots \\p_t(n) \end{pmatrix} = A^t\begin{pmatrix} p_0(1) \\p_0(2) \\p_0(3) \\ \vdots \\p_0(n) \end{pmatrix} = \begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^1 &\omega^2 & \hdots &\omega^{n-1} \\ \omega^0 &\omega^2 &\omega^4 & \hdots &\omega^{(n-1)2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{n-1} &\omega^{2(n-1)} & \hdots & \omega^{(n-1)(n-1)} \end{pmatrix}\begin{pmatrix} c_0 \\ \lambda_1^t c_1 \\ \lambda_2^t c_2 \\ \vdots \\\lambda_{n-1}^tc_{n-1} \end{pmatrix}

     

    \lim_{t\rightarrow \infty}\begin{pmatrix} p_t(1) \\p_t(2) \\p_t(3) \\ \vdots \\p_t(n) \end{pmatrix} \\= \lim_{t\rightarrow \infty}\begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^1 &\omega^2 & \hdots &\omega^{n-1} \\ \omega^0 &\omega^2 &\omega^4 & \hdots &\omega^{(n-1)2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{n-1} &\omega^{2(n-1)} & \hdots & \omega^{(n-1)(n-1)} \end{pmatrix}\begin{pmatrix} c_0 \\ \lambda_1^t c_1 \\ \lambda_2^t c_2 \\ \vdots \\\lambda_{n-1}^tc_{n-1} \end{pmatrix} \\=\begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^1 &\omega^2 & \hdots &\omega^{n-1} \\ \omega^0 &\omega^2 &\omega^4 & \hdots &\omega^{(n-1)2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{n-1} &\omega^{2(n-1)} & \hdots & \omega^{(n-1)(n-1)} \end{pmatrix}\begin{pmatrix} c_0 \\0 \\0 \\ \vdots \\\0\end{pmatrix} \\=\begin{pmatrix} \frac{1}{n} \\\frac{1}{n} \\\frac{1}{n} \\ \vdots \\ \frac{1}{n} \end{pmatrix}

     

     

    댓글 작성하기 좋아요0 댓글수7
    •  
      Sait2000 Lv.2 2020.07.21 12:21

      잘린 수식입니다. 노란 배경 눈 아프네요

       

      좋아요0
    •  
      Benedict Lv.5 2020.07.21 13:07

      잘 이해가 안 되는 부분 질문이요!

      질문1. 9번째 줄의 '위의 행렬'이 \begin{pmatrix} p_1(k+1)\\ p_2(k+1)\\ p_3(k+1)\\ \vdots \\ p_n(k+1) \\ \end{pmatrix} = \begin{pmatrix} 0 & 1-p & 0 & \hdots & p\\ p & 0 & 1-p & \hdots & 0\\ 0 & p & 0 & \hdots & \vdots\\ \vdots & \vdots & \vdots & \ddots & 1-p \\ 1-p & 0 & \hdots & p & 0\\ \end{pmatrix} \begin{pmatrix} p_1(k)\\ p_2(k)\\ p_3(k)\\ \vdots \\ p_n(k) \\ \end{pmatrix} 이걸 뜻하는 거죠? 그리고 이 식에서 양옆 세로로 긴 행렬 잘못된 것 같긴 한데...(시간이랑 개미 위치 바꿔 쓰신 듯?) 일단 넘어가겠습니다.

      질문2. A 구하는 식에서 pS를 더하는 것을 알겠습니다. 그런데 왜 qS^(n-1)를 더하고, 왜 S^-1과 같나요? (왜 S^n=I인가요?)

      질문3. S\begin{pmatrix} \omega^0\\ \omega^k\\ \omega^2k\\ \vdots \\ \omega^{(n-1)k} \end{pmatrix}=\begin{pmatrix} \omega^{(n-1)k}\\ \omega^0\\ \omega^k\\ \vdots \\ \omega^{(n-2)k} \end{pmatrix}=\omega^{(n-1)k}\begin{pmatrix} \omega^0\\ \omega^k\\ \omega^2k\\ \vdots \\ \omega^{(n-1)k} \end{pmatrix} 이거 수식 잘못된 거겠죠? \omega ^{2k}인 것 같습니다. 계속 반복해서 잘못 쓰여지는 부분인 듯하여 수정 부탁드립니다.

      질문4. 마지막 수식을 잘 모르겠어요 DFT 이후 무엇을 한지만 간단하게 설명 부탁드립니다.

      좋아요0
    •  
      Sait2000 Lv.2 2020.07.22 00:14

      오타가 많았네요 생각보다. 감사합니다. 고치는 건 나중에 의지가 생기면 고쳐볼게요

       

      질문 2번은 자명하다고 생각해서 대충 적었는데 좀 더 설명을 해보자면 0 <= i < n에 대해 다음과 같은 열벡터를 생각합시다. 그러니까 한 성분만 1인 열벡터입니다.

      \overrightarrow{e_i}=\begin{pmatrix} a_0\\ a_1\\ a_2\\ \vdots \\ a_{n-1} \end{pmatrix}, a_j = \left\{\begin{matrix} 1 \,(i = j)\\ 0 \,(i \neq j) \end{matrix}\right.

      그러면 e_0 ~ e_{n-1}는 기저를 이룹니다. 이제 S e_i = e_{i+1}, S e_{n-1} = e_0입니다. 따라서 S^n * e_i = e_i이고 S^n = I 입니다

       

      잘 모르겠으면 S 건너뛰고 그냥 A랑 고유벡터랑 곱하고 진짜로 고유벡터인지 확인하셔도 상관없다고 생각합니다.

       

      질문 4번은

      \begin{pmatrix} p_0(1) \\p_0(2) \\p_0(3) \\ \vdots \\p_0(n) \end{pmatrix} = \begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^1 &\omega^2 & \hdots &\omega^{n-1} \\ \omega^0 &\omega^2 &\omega^4 & \hdots &\omega^{(n-1)2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{n-1} &\omega^{2(n-1)} & \hdots & \omega^{(n-1)(n-1)} \end{pmatrix}\begin{pmatrix} c_0 \\ c_1 \\c_2 \\ \vdots \\c_{n-1} \end{pmatrix}

      여기서 우변은 행렬곱이긴 한데 사실 좌변이 우변의 행렬의 열벡터들의 선형 결합이고 그 가중치들이 c0~n-1이란 얘기를 하고 있습니다. 그 열벡터들이 A의 고유 벡터니까 A를 곱하면 가중치에 고윳값이 곱해집니다.

      좋아요0
    •  
      Benedict Lv.5 2020.07.22 12:25

      이제 알겠습니다!

      저 오메가 행렬의 각 열이 A의 고유벡터니까 A^t를 곱하면 첫 번째 열에는 \lambda _0^t, 두 번째 열에는 \lambda _1^t, ....가 곱해져서 고윳값들을 가중치에 대신 곱해줄 수 있는 거네요.

      그리고 

       

      \begin{pmatrix} c_0 \\ c_1 \\c_2 \\ \vdots \\c_{n-1} \end{pmatrix}= \frac{1}{n}\begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^{n-1} &\omega^{n-2} & \hdots &\omega^{1} \\ \omega^0 &\omega^{(n-1)2} &\omega^{(n-2)2} & \hdots &\omega^{2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{(n-1)(n-1)} &\omega^{(n-2)(n-1)} & \hdots & \omega^{(n-1)} \end{pmatrix}\begin{pmatrix} p_0(1) \\p_0(2) \\p_0(3) \\ \vdots \\p_0(n) \end{pmatrix}

      이 행렬에서 p_0(1)=1, p_0(2)=p_0(3)=\cdots =p_0(n)=0이니까 가중치를 계산해주면 c_0=c_1=\cdots = c_n =\frac{1}{n}으로 구할 수 있는 거 맞나요?

      좋아요0
    •  
      Benedict Lv.5 2020.07.23 10:17

      등호는 \sin^2 \left(k\frac{2\pi}{n}\right)=0일 때, 즉 k = 0일 때만 성립합니다. (지금의 논리에서 0 < p < 1, n은 홀수라는 점이 필요합니다)

       

       

      이 문장에서 n이 홀수라는 점이 왜 필요한 거죠?

      좋아요0
    •  
      리프 Lv.6 2020.07.23 11:16

      제가 생각하기엔 만약 n이 짝수, 즉 어떤 정수 l이 존재하여 n=2l을 만족한다면, k=l일 때, 0<k<n을 만족하면서 sin^2(k*2pi/n)=sin^2(pi)=0가 됩니다. 그래서 k=0인 경우에만 등호가 성립하려면 n이 홀수여야 하는 것 같습니다.

      좋아요0
    •  
      Benedict Lv.5 2020.07.23 12:14

      아 sin(pi)가 0이었죠 ㅋㅋㅋㅋ sin(pi)가 1인 걸로 헷갈렸어요ㅠㅠ

      좋아요0
  •  
    Benedict Lv.5 2020.07.22 13:41

    Sait2000님 풀이를 확장하면 3번도 풀 수 있을 것 같아요. 그런데 그 전에 3번에서 한 칸 이동할 확률과 두 칸 이동할 확률이 같은 건 가요? 다른 건가요?

    댓글 작성하기 좋아요0 댓글수0
  •  
    Benedict Lv.5 2020.07.26 00:18

    Sait2000님의 아이디어를 확장하여 3-(1)번을 풀겠습니다. 같은 방향으로 갈 확률은 같다고 가정했습니다. 다음과 같은 행렬을 쓸 수 있습니다. 우변의 왼쪽 행렬을 B라고 하겠습니다.

    \begin{pmatrix} p_{t+1}(1)\\ p_{t+1}(2)\\ p_{t+1}(3)\\ \vdots \\ p_{t+1}(n) \end{pmatrix}=\begin{pmatrix} 0 & \frac{1-p}{2} & \frac{1-p}{2} & 0 & \cdots & \frac{p}{2} & \frac{p}{2}\\ \frac{p}{2} & 0 & \frac{1-p}{2} & \frac{1-p}{2} & \cdots & 0 & \frac{p}{2}\\ \frac{p}{2} & \frac{p}{2} & 0 & \frac{1-p}{2} & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \frac{1-p}{2} & \frac{1-p}{2} & 0 & 0 & \cdots & \frac{p}{2} & 0 \end{pmatrix}\begin{pmatrix} p_t(1)\\ p_t(2)\\ p_t(3)\\ \vdots \\ p_t(n) \end{pmatrix}

    그리고 S를 Sait2000님과 같이 이렇게 정의합니다.

    S = \begin{pmatrix} 0 &\hdots &\hdots &0 &1 \\ 1& 0 & \hdots &0 &0 \\ 0& 1 & \hdots &0 &\vdots \\ \vdots &\vdots &\ddots &\vdots &\vdots \\ 0& 0 &\hdots &1 &0 \end{pmatrix} =\begin{pmatrix} O & I_1\\ I_{n-1}& O \end{pmatrix} 

    여기서 직접 곱해보시면 다음과 같은 식이 성립함을 알 수 있습니다.(계산 간단해요)

    B=\frac{p}{2}(S+S^2)+\frac{1-p}{2}(S^{n-1}+S^{n-2})=\frac{p}{2}(S+S^2)+\frac{1-p}{2}(S^{-1}+S^{-2})

    따라서 B도 S에 대한 다항식 꼴로 나올 수 있었습니다. 따라서 S의 고유벡터는 B의 고유벡터입니다. S는 Sait2000님과 같은 행렬을 사용했으므로 고윳값과 고유벡터도 같습니다.

     

    또한 0<k<n일 때  \left|p\omega^{-k}+q\omega^k\right|<1이므로 \frac{1}{2}\left | p\omega ^k+p\omega ^{2k}+q\omega ^{-k} +q\omega ^{-2k}\right |\leq \frac{1}{2}\left | p\omega ^k +q\omega ^{-k} \right |+\frac{1}{2}\left | p\omega ^{2k}+q\omega^{-2k} \right | \leq 1이 때 등호 성립 조건은 k=0이고, 0<k<n일 때는 좌변이 더 작습니다. 그리고 이 때 0<p<1, n은 홀수라는 가정이 필요합니다.

     

    t=0일 때 확률을 고유벡터의 선형결합으로 표현합니다.

    \begin{pmatrix} p_0(1) \\p_0(2) \\p_0(3) \\ \vdots \\p_0(n) \end{pmatrix} = \begin{pmatrix} \omega^0 &\omega^0 &\omega^0 & \hdots &\omega^0 \\ \omega^0 &\omega^1 &\omega^2 & \hdots &\omega^{n-1} \\ \omega^0 &\omega^2 &\omega^4 & \hdots &\omega^{(n-1)2} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ \omega^0 &\omega^{n-1} &\omega^{2(n-1)} & \hdots & \omega^{(n-1)(n-1)} \end{pmatrix}\begin{pmatrix} c_0 \\ c_1 \\c_2 \\ \vdots \\c_{n-1} \end{pmatrix} 

    사실 B의 고유벡터가 S와 같다는 것을 구했고 고윳값이 1보다 작거나 같다는 것을 증명했으므로 이후 과정은 같습니다.

    증명 완료.

    댓글 작성하기 좋아요0 댓글수3
    •  
      Benedict Lv.5 2020.07.26 00:25

      Sait2000님의 1번 풀이를 참고해주세요. 과정을 많이 생략했습니다.

       

      요약하자면 핵심은 다음과 같습니다.

       

      1. B의 고윳값을 구해보면 그 절댓값이 1보다 작거나 같음

      2. t=0일 때 확률을 고유벡터의 선형결합으로 표현 (고유벡터 행렬의 역행렬이랑 t=0일 때 확률인 열벡터를 곱해서 가중치를 구할 수 있고, 따라서 고유벡터 행렬과 가중치의 열벡터를 곱하면 t=0일 때 확률이 나온다.)

      3. t가 무한으로 갈 때 초기 행렬에 B를 t번 곱한다. 이 때 고유벡터 행렬의 효과로 가중치에 고윳값이 t번 곱해진다. 따라서 고윳값이 1인 첫 번째 가중치를 제외하고 고윳값의 절댓값이 1보다 작으므로 0으로 수렴, t를 무한으로 보낼 때 각각의 확률을 1/n으로 구할 수 있다.

       

      풀이를 날로 먹었네요... ㅎ 검토 부탁드립니다.

      좋아요0
    •  
      리프 Lv.6 2020.07.26 15:47

      선형대수 몰라서 날로 먹지도 못하는 1인 ㅜㅜ

      좋아요0
    •  
      Benedict Lv.5 2020.07.26 23:22

       합격하시고 시간 나시면 해보세요. 재밌어요.

       

       그나저나 선형대수가 굉장한 치트키이긴 하네요... 4번의 첫 번째 질문도 고윳값이 1보다 작다는 것만 증명하면 같은 방법으로 해결이 가능합니다! 다만 진짜 어려운 건 1,3,4번에서 2번 질문을 해결하는 거죠...

      좋아요0
  •  
    Benedict Lv.5 2020.07.26 23:15

    2번에 1번은 \lambda _k=\cos \frac{2k\pi }{n}이라는 것에 주목하면 될 것 같습니다... 식이 상당히 더럽네요. 직접 계산하기보다 범위를 찾아야겠어요. 극한값 구하는 건 어려울 것 같아요. 혹시 다른 방법이 있을까요?

    댓글 작성하기 좋아요0 댓글수0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911