간단할 수도 있고 - 풀이

문제는 https://arca.live/b/math/45513676

기대값이 1/4 로 보인다는 Bremsstrahlung 님의 실험: https://arca.live/b/math/45559631

----------------------------------------------------------------------------------------

다음과 같은 작업을 한다고 하자.

비어있는 문자열이 있다. ' '

여기서 다음 작업을 무한히 반복한다.

1/3의 확률로 문자열 뒤에 숫자 1을 붙인다.

1/3의 확률로 문자열 뒤에 기호 -를 붙인다.

1/3의 확률로 그만둔다.

이때 식의 마지막이 -로 끝나면 추가로 0을 붙인다고 하자.

예를 들어, 과정 1 -> 2 -> 1 -> 3을 거쳤을 경우, 문자열은 '1 - 1'가 되어 0의 값을 갖는다.

과정 1 -> 1 -> 2 -> 1 -> 3을 거쳤을 경우, '11 - 1'이 되어 10의 값을 갖는다.

11, 111 등을 다룰 때 10진법은 복잡하니 1진법을 사용하여 11(1) = 2, 111(1) = 3, ... 이라고 하자.

이 작업을 반복할 때, 수식의 값의 기댓값을 구하시오.

단, 텅 빈 식의 값은 0이다.

----------------------------------------------------------------------------------------

편의상 "1/3의 확률로 그만둔다" 를 "1/3의 확률로 EOL 이 나온다" 고 표현하기로 하자.

문자열이 1로 시작할 때, -나 EOL 이 나올 때까지 나오는 1의 숫자(첫 번째 1도 포함해서)의 기대값을 A 라 하자.

A = 1 + 1/3 + 1/9 + ... = 3/2

문자열이 -로 시작할 때의 수식의 기대값을 T 라 하자. 문자열이 - 로 시작할 때의 경우들을 보면

(1) 처음의 연속한 -들 끝에 EOL 이 나오는 경우: 1/2

(2) 처음의 연속한 -들 끝에 1이 나오는 경우: 1/2

(2-1) 처음의 연속한 -들 끝에 1이 나오고 그 1들 끝에 EOL 이 나오는 경우: 1/2 * 1/2

(2-2) 처음의 연속한 -들 끝에 1이 나오고 그 1들 끝에 - 가 나오는 경우: 1/2 * 1/2

따라서 T = 1/2 ( ((처음의 - 숫자가 짝수일 확률) - (처음의 - 숫자가 홀수일 확률)) A + (1/2) T)

처음의 연속한 - 숫자가 홀수일 확률은 1 * 2/3 + 1 * 1/9 * 2/3 + ... = 2/3 * 9/8 = 3/4 로 계산할 수 있다. 혹은 - 숫자가 2일 확률은 1일 확률의 1/3, - 숫자가 4일 확률은 3 일 확률의 1/3, ... 임을 통해서 홀수일 확률이 짝수일 확률의 3배라고 직관적으로 계산할 수도 있다.

따라서 T = 1/2 ( (-1/2) A + (1/2) T) = 1/4 (-A + T)

고로 T = (-1/3)A

전체 수식의 경우들을 보면

(1) 처음 문자가 EOL 인 경우: 기대값 0

(2) 처음 문자가 - 인 경우: 기대값 T

(3) 처음 문자가 1 인 경우

(3-1) 처음의 연속한 1들 끝에 EOL 이 나오는 경우: 기대값 A

(3-2) 처음의 연속한 1들 끝에 - 가 나오는 경우: 기대값 A + T

따라서 수식의 기대값은

(1/3) T + (1/3) ((1/2)A + (1/2)(A + T))

= (1/3) (A+ (3/2)T)

= (1/6) A