동전을 던져 같은 면이 연속 n번 나오려면 몇 번 던져야 하는가

댓글이 길어져서 새로 글을 씁니다.

같은 면이 연속 i번 나온 상태를 "상태 i"라고 해봅시다. 예를 들어 동전을 던져서 이렇게 나왔다면,

짝 홀 홀 짝 홀 짝 짝 짝

각각은 차례대로 상태 1, 1, 2, 1, 1, 1, 2, 3이 됩니다(설명하기 어렵네요;;).

그렇다면 다음과 같은 성질을 발견할 수 있습니다.

상태 1에서는 상태 1 또는 상태 2로 갈 수 있다.

상태 2에서는 상태 1 또는 상태 3으로 갈 수 있다.

상태 3에서는 상태 1 또는 상태 4로 갈 수 있다.

...

동전 앞뒷면 나올 확률이 같으니까 모두 확률은 반반입니다.

따라서 구해야 할 것은 몇 번을 던져야 처음으로 "상태 n"까지 갈 수 있느냐죠.

이걸 An이라 합시다.

처음 던지면 당연히 상태 1입니다. 여기서 바로 상태 n까지 갔다고 해봅시다. n번만 던지면 끝나게 됩니다.

이렇게 되는 경우의 수는 짝짝...짝/홀홀...홀 총 2가지이고, 확률은 2*(1/2)^n 입니다.

두 번째로 던졌는데 첫 번째와 다르면 상태 1에서 또 상태 1로 간 게 됩니다.

이렇게 될 확률은 1/2이고, 두 번째에서 출발해 상태 n까지 가는데 An번 걸리니 An+1번 던지면 끝나게 됩니다.

처음과 두 번째는 같은데 세 번째가 다르면 상태 2까지 갔다가 상태 1로 간 겁니다.

확률은 (1/2)^2이고, 세 번째에서 출발해 상태 n까지 가는데 An번 걸리니 An+2번 던지면 끝나게 됩니다.

...

처음부터 n-1번째까지는 같은데 n번째가 다르면 상태 n-1까지 갔다가 상태 1로 간 겁니다.

확률은 (1/2)^(n-1)이고, n번째에서 출발해 상태 n까지 가는데 An번 걸리니 An+n-1번 던지면 끝나게 됩니다.

따라서 상태 n까지 가는데 필요한 평균 동전 던지기 횟수는

n*2*(1/2)^n + (An+1)*(1/2) + (An+2)*(1/2)^2 + ... + (An+n-1)*(1/2)^(n-1)

인데 이게 An입니다.

따라서 열심히 정리해서 An을 구하면 An = 2^n-1이 됩니다.

다 쓰고 보니 뭔가 상당히 야매...(?)같네요...