본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[대한수학회] 대69. 무작위 걸음 문제
수학동아 2022.08.31 20:44 조회 776

대한수학회 69번

 

 

무작위 걸음 문제

 

 

남경식 KAIST 수리과학과 교수

 

 

 

 

 

 정수로 이뤄진 일직선을 생각해보세요. 원점에 개구리가 있는데, 이 개구리는 매 시간마다 왼쪽 또는 오른쪽의 인접한 칸으로 각각\frac{1}{2}의 확률로 점프해요.

 

 

 

 

 

 

 

질문 : 개구리가 "A=10의 위치" 또는 "B=-5의 위치"에 도착할 때 움직임을 멈춘다고 하자. 이때, 멈춘 지점이 A일 확률은 얼마인가?

 

 

 

 

 

 이 문제의 해결을 위해서는 '마팅게일'이라는 개념이 필요해요. 마팅게일이란, 현재까지의 모든 정보가 주어질 때, 미래의 기댓값은 현재의 주어진 값과 동일하다는 뜻이에요.

 

 

 이 예시에서는 개구리의 위치가 마팅게일이에요. 이를 살펴보기 위해, 현재시간 t에서의 개구리의 위치를 X_{t}라 할게요. 이때, 다음 시간 t+1에서의 위치는 \frac{1}{2}의 확률로 X_{t}+1 이고 \frac{1}{2}의 확률로 X_{t}-1 이에요. 이 기대값은 X_{t}가 되기 때문에, 현재시간 t에서의 위치 X_{t}와 일치하지요.

 

 

 마팅게일에 관련된 중요 성질 중 하나는 '멈춤 정리'인데, 멈추는 시점에서의 기댓값은 초기 시점에서의 기댓값과 항상 같다는 것이에요. 이 사실을 위 문제로 응용해볼게요.

 

 

 원점에서 출발한 개구리가 A또는 B에서 멈추는 시간을 T라고 할게요. 개구리의 위치는 마팅게일이기 때문에, 멈춤 정리에 의해 X_{T}의 기댓값은 초기 위치의 기댓값과 같아요. 초기시점에서의 위치는 0이기 때문에, X_{T}의 기댓값 역시 0이지요. 따라서,

 

 

( A에서 멈출 확률) × ( A의 위치) + ( B에서 멈출 확률) × ( B의 위치) = 0

 

 

이에요. 이 사실과

 

 

( A에서 멈출 확률) + ( B에서 멈출 확률) = 1

 

 

을 함께 종합하면, A에서 멈출 확률이 \frac{5}{15}=\frac{1}{3} 이라는 사실을 도출할 수 있어요.

 

 

위와 같이 마팅게일 개념을 이용하여, 다음의 문제를 해결해 보세요.

 

 

 

 

상황

개구리가 왼쪽 및 오른쪽 칸으로 움직이는 확률이 \frac{1}{2}가 아니라, 왼쪽 칸으로 뛸 확률이 \frac{1}{3}이고 오른쪽 칸으로 뛸 확률이 \frac{2}{3}라고 하자.

 

 

 

 

 

 

문제 1. 개구리가 위치 “A = 10의 위치”에 도착하기까지 점프한 횟수의 기댓값은 얼마인가요?

 

(힌트: 오른쪽으로 점프할 확률이 왼쪽보다 크기 때문에, 개구리 위치의 기댓값은 시간의 흐름에 따라 오른쪽으로 치우쳐요. 즉, 기댓값이 계속 증가하기 때문에 개구리의 위치는 더이상 마팅게일이 아니에요. 이를 해결하기 위해서는, 개구리의 위치를 시간의 흐름에 따라 적절히 보정해야 하지요.)

 

 

 

 

문제 2. 개구리가 “B= 15의 위치” 또는 “C = -10의 위치” 에 도착할 때 움직임을 멈춘다고 한다면 이때 멈춘 지점이 B일 확률은 얼마인가요?

 

(힌트: 시간 t에서의 위치를 X_{t}라 할 때, (\frac{1}2{})^{X_{t}}가 마팅게일인가요?)

 

 

 

 

문제 3. 개구리가 “D = -50의 위치” 에 영원히 도착하지 않을 확률은 얼마인가요?

 

(힌트: “A_{n} = n의 위치”를 가상으로 생각하여, 두 점 D A_{n}에 대해 문제 2를 먼저 해결해 보세요.)

 

 

 

 

 

 

 

 

※ 소문제 2번과 3번 문제를 RedoC 회원님이 풀었습니다! 소문제 1번만 해결되면 남경식 교수님의 최종 확인 후 남 교수님께 멘토링을 받을 수 있어요~!

 

 

 

 

 

  •  
    다시 도전
    수냥이 Lv.5 2022.09.02 07:32

    1.

    현재 뛴 횟수가 t번 일 때

    t=x+y라고 하자. (x=왼쪽으로 간 횟수, y=오른쪽으로 간 횟수)

    여기서 y-x=10

    그리고 왼쪽으로 뛴 확률=오른쪽으로 뛴 확률/2이다.

    기대값을 구하려고 하기 때문에 y=2x라고 하면

    y-x=10

    y=2x

    -> x=10, y=20이다.

    그러면 t의 기댓값은 30이다.

    답: 30회

    댓글 작성하기 좋아요0 댓글수3
    •  
      수냥이 Lv.5 2022.09.02 07:32

      1번만 했습니다.

      좋아요0
    •  
      RedoC Lv.6 2022.09.05 18:47

      맞는 것 같습니다. 시뮬레이션을 돌렸을 때도 30에 거의 근접하는 횟수로 나옵니다.

      좋아요0
    •  
      김다인(멘토) Lv.15 2022.09.21 10:53

      수냥이 친구에게,

       

      기댓값의 정의를 생각해보거나 마팅게일의 의미를 다시 곱씹어보세요!

       

      이 상황에서는 y=2x와 같은 논리를 펼칠 수 없답니다.

       

      다인 멘토 드림

      좋아요0
  •  
    수냥이 Lv.5 2022.09.02 07:41

    2.

    뛴 횟수: t번

    ( C에서 멈출 확률) × ( C의 위치) + ( B에서 멈출 확률) × ( B의 위치) = 2t 

     

    C에서 멈출 확률) + ( B에서 멈출 확률) = 1 을 종합하면

    15( B에서 멈출 확률)-10( C에서 멈출 확률)=2t

    B에서 멈출 확률)+( C에서 멈출 확률)=1

    인 것 같은데.... 어떻게 해야할까요?

    댓글 작성하기 좋아요0 댓글수0
  •  
    부분해결
    RedoC Lv.6 2022.09.02 17:39 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수6
    •  
      RedoC Lv.6 2022.09.02 22:08

      맞았는지 틀렸는지 감이 잘 안 잡혀서 문제 2 풀이를 공개합니다.

      X_t를 시간 t에서의 위치라고 정의하며 Y_t := \left ( \frac{1}{2} \right )^{X_t}라고 정의한다.

      먼저 Y_t가 마팅게일임을 보이자. E(Y_{t+1}) = \frac{1}{3} \left ( \frac{1}{2} \right )^{X_t-1} + \frac{2}{3} \left ( \frac{1}{2} \right )^{X_t+1} = \left ( \frac{1}{2} \right ) ^{X_t}=Y_t이므로 간단히 보일 수 있다.

       

      이제 원점에서 출발한 개구리가 B에서 멈출 확률을 x(즉 A에서 멈출 확률이 1-x)라고 두고 A 또는 B에서 멈추는 시간을 T라고 할 때 \mathbb{E}(Y_T)에 대한 식을 구해보면

      \mathbb{E}(Y_T) = \left ( \frac{1}{2} \right )^{15}x +\left ( \frac{1}{2} \right )^{-10} (1-x) = Y_0 = 1

      이를 x에 대해 풀면

      \\ x +2 ^{25} (1-x) = 2^{15} \\ (2^{25}-1)x = 2^{25}-2^{15} \\ x = \frac{2^{25}-2^{15}}{2^{25}-1}

      즉 멈춘 지점이 B일 확률은 \frac{2^{25}-2^{15}}{2^{25}-1}

      좋아요0
    •  
      수냥이 Lv.5 2022.09.04 17:03

      그런데 E(x)가 무슨 뜻 인가요?

      좋아요0
    •  
      RedoC Lv.6 2022.09.04 17:06

      기댓값입니다.

      좋아요0
    •  
      RedoC Lv.6 2022.09.04 23:42

      오타가 있네요. 'A 또는 B' 가 아니라 'B 또는 C'입니다.

      좋아요0
    •  
      김다인(멘토) Lv.15 2022.09.21 10:58

      RedoC 친구에게,

       

      잘 풀었습니다! 마팅게일을 제대로 이해했네요.

       

      다인 멘토 드림

      좋아요0
    •  
      유지연_매니저 Lv.15 2022.09.23 11:38

      RedoC님, 안녕하세요~!

      문제 잘 풀어주셨네요~

      소문제를 맞혀 주셔서 부분해결 드립니다~

      기존에 해결 딱지는 잘못 붙여진 것이라 포인트는 자동으로 부분해결 포인트로 적용됩니다.

      혼란을 드려 죄송합니다.

      소문제 1번까지 다인 멘토님께서 확인하시면

      문제 출제해 주신 남경식 교수님께 최종 확인 후 멘토링 진행 예정입니다~

      감사합니다.

      좋아요0
  •  
    부분해결
    RedoC Lv.6 2022.09.05 18:18

    문제 3 풀이입니다.

    일단 \small D(-50)에 영원히 도착하지 않으려면 개구리는 왼쪽으로 갈 수 있되 궁극적으로 오른쪽으로 무한히 발산해야 한다.

    따라서 이 문제는 개구리가 \small D(-50) 또는 \small E(n)  \small (n \rightarrow \infty )에 도착할 때 움직임을 멈춘다고 하면 멈춘 지점이 \small E일 확률은 얼마인지를 구하면 해결된다.

     

    먼저 멈춘 지점이 \small E일 확률 \small x를 \small n에 대한 식으로 나타내자. 문제 2 풀이를 빌려 간략하게 적는다.

    \small \left ( \frac{1}{2} \right )^{n}x + \left ( \frac{1}{2} \right )^{-50} (1-x) = 1

    \small x = \frac{2^{50+n}-2^n}{2^{50+n}-1} = 1 - \frac{2^n - 1}{2^{50+n}-1}

    이제 \small n \rightarrow \infty일 때의 \small x를 구해보자.

    \small \lim_{n \rightarrow \infty} x = 1 - \frac{1}{2^{50}} = \frac{1125899906842623}{1125899906842624}

     

    즉 멈춘 지점이 \small E일 확률이자 \small D(-50)에 영원히 도착하지 않을 확률은 \small \frac{1125899906842623}{1125899906842624}

     

    댓글 작성하기 좋아요0 댓글수4
    •  
      수냥이 Lv.5 2022.09.05 21:23

      엌 제가 먼저 하려고 했는데 ㅋㅋㅋ (학원에 있어서 못함)

      좋아요0
    •  
      수냥이 Lv.5 2022.09.06 08:47

      RedoC님의 풀이에서 (조금 간단하게)

      \lim_{n \to \infty }(\frac{1}{2})^nx+(\frac{1}{2})^{-50}(1-x)=1

      (1/2)^n은 0에 수렴

      따라서 (2^50)(1-x)=1

      x=\frac{2^{50}-1}{2^{50}}

       

      좋아요0
    •  
      김다인(멘토) Lv.15 2022.09.21 20:25

      RedoC 친구에게,

       

      잘 풀었습니다! 구하신 limit이 왜 문제에서 원하는 확률과 같은지에 대한 논의가 조금 더 들어가면 더 좋을 수 있습니다. 이 부분은 나중에 수학을 더 공부한 다음에 혹시 생각난다면 다시 이 풀이로 돌아와서 생각해보세요:)

       

      수고 많았습니다~~

       

      다인 멘토 드림

      좋아요1
    •  
      RedoC Lv.6 2022.09.21 20:56

      @김다인(멘토) 제가 엄밀하지 못하다고 생각하고 있던 포인트를 정확히 지적해주셨네요. 감사합니다!

      좋아요0
  •  
    다시 도전
    RedoC Lv.6 2022.09.22 16:57 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      김다인(멘토) Lv.15 2022.09.26 08:20 비밀댓글
      비밀 댓글이 등록 되었습니다!
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911