TTH는 요전 글에 계산한 것이 맞나본데 HTH 계산이 잘못돼서 다시 넣습니다.


각 셀의 값이 의미하는 바는 다음과 같습니다.

a(cases) : 이번 회차 던질 때 나오는 경우의 수. n-1차에서 넘어온 각각에 대해 H,T가 뒤에 붙으므로 = (윗행 e) * 2

b("-H") : 이번 회차 던진 것 중 H로 끝나는 것의 수. 이번에 던진 것 중 절반은 H가 나오니 당연히 = a/2 = (윗행 e)

c("-HT") : 이번 회차 던진 것 중 HT로 끝나는 것의 수. 윗행에서 H로 끝나는 것 중 HTH로 끝나지 않는 것이 넘어오면 다시 이번에 던져서 T가 붙은 것. = (윗행 b) - (윗행 d)

d("HTH") : 이번 회차 던진 것 중 HTH로 끝나는 것의 수. 윗행에서 HT로 넘어온 다음 이번에 H가 붙으면 됨. = (윗행 c)

e(rest) : 이번에 HTH가 안나와서 다음번으로 넘어가는 것의 수. = a - d


n=1일 때에 대해 a b c d에 초기값을 넣어 계산했습니다.

P(n) = d / 2^n

기대값은 n*P(n)의 무한급수인데 n=200까지 계산하니 10 - 1.2E-09
아마 10이겠지요.

구해야되는 값은 d(H열)죠.
d_n = c_(n-1)  ---- 식(1)
c_n = b_(n-1) - d_(n-1)
b_n = a_n / 2 = e_(n-1)
e_n = a_n - d_n = 2 * e_(n-1) - d_n  ---- 식(2)

식(1)에 그 아래 식들을 차례로 대입해나가면
d_n = c_(n-1) = b_(n-2) - d_(n-2) = e_(n-3) - d_(n-2)
즉, d_n = e_(n-3) - d_(n-2)  ---- 식(3)

그런데 식(2)에서
d_n = 2 * e_(n-1) - e_n
이며 다시 식(3)에 넣으면

2 * e_(n-1) - e_n = e_(n-3) - 2 * e_(n-5) + e_(n-2)

어우 뻐킹 개구림. 안해.



아래는 마찬가지로 계산한 TTH의 기대값.
200까지 계산했을 때 8 - sum(n*P(n)) ~ 0

여기는 TT가 윗행의 T값, TTH는 윗행의 TT값

a: case
b: T
c: TT
d: TTH
e: rest

d_n = c_(n-1)
c_n = b_(n-1)
b_n = a_n / 2 = e_(n-1)
e_n = a_n - d_n = 2 * e_(n-1) - d_n

마지막 식에 죄다 대입하면
e_n = 2 * e_(n-1) - c_(n-1) = 2 * e_(n-1) - b_(n-2) = 2 * e_(n-1) - e_(n-3)
즉, e_n = 2 * e_(n-1) - e_(n-3)

이건 좀 덜 뻐킹

e_n - e_(n-1) = e_(n-1) - e_(n-2) + e_(n-2) - e_(n-3)
e_1 = 2
e_2 = 4
e_3 = 7

e의 계차를 f라 하면 f_n = e_(n+1) - e_n 이니까 (단, f_1 = 2, f_2 = 3)

f_(n-1) = f_(n-2) + f_(n-3)
즉,
f_(n+2) = f_n + f_(n-1) -> Fibonacci!!!

계차가 피보나치면 원래 수열도 피보나치가 될건데 d_n의 계차도 0, 1로 시작하는 피보나치 수열이네요.

d_(n+1) - d_n = Fib_n

d_n = d_1 + Σ _k=1 ^n-1 ( Fib(n) )
d_1 = 0이고 피보나치 성질에 의해서 다시

d_n = Fib(n+1) - 1 (where d_1 = 0)

원하는 기대값은

Σ _k=1 ^inf ( k * ( Fib(k+1) - 1 ) / 2^k )