주어진 조건에서 지시 확률변수(Indicator Random Variable)의 함수를 계산하는 Python 프로그램

두 개의 값 k와 n이 주어져 있다고 가정해 보겠습니다. 자연수 1, 2, ..., n에 대한 임의의 순열 p₁, p₂, ..., p_n을 하나 생각하고, 다음과 같이 정의되는 값 F를 계산하려고 합니다.

F = (X₂ + X₃ + ... + X_n-1)^k

여기서 X_i는 지시 확률변수(indicator random variable)로, 다음 두 조건 중 하나를 만족할 때만 1의 값을 가집니다.

p_i-1 < p_i > p_i+1 → p_i가 양쪽 이웃보다 큰 경우(국소 최댓값)
p_i-1 > p_i < p_i+1 → p_i가 양쪽 이웃보다 작은 경우(국소 최솟값)

어느 조건도 만족하지 않으면 X_i는 0입니다. 우리가 구해야 할 것은 바로 이 F의 기댓값입니다. 예를 들어 입력이 k = 1, n = 1000이라면 결과는 1996/3이 됩니다.

핵심 아이디어

무작위 순열에서 연속한 세 원소 p_i-1, p_i, p_i+1의 상대적인 순서는 총 3! = 6가지가 모두 같은 확률로 나타납니다. 이 중 가운데 원소가 양쪽보다 크거나 작은 경우는 4가지이므로, 각 X_i가 1이 될 확률은 4/6 = 2/3입니다. 즉 E[X_i] = 2/3이며, k = 1일 때는 기댓값의 선형성에 의해 E[F] = 2(n−2)/3이 됩니다. 예제 입력 n = 1000에 대입하면 2 × 998 / 3 = 1996/3으로, 프로그램의 출력과 정확히 일치합니다.

k ≥ 2인 경우에는 X_i들 사이의 공분산 항까지 고려해야 하므로 식이 복잡해지지만, 그 결과는 n에 대한 다항식 형태로 닫혀 있기 때문에 차수별 공식을 미리 정의해 두면 매우 빠르게 계산할 수 있습니다.

풀이 절차

이 문제는 다음 단계를 거쳐 해결할 수 있습니다.

exp_factor() 함수를 정의합니다. 이 함수는 n과 k를 인자로 받습니다.
k = 1이면 (2·(n−2), 3)을 반환합니다.
k = 2이면 (40n² − 144n + 131, 90)을 반환합니다.
k = 3이면 (280n³ − 1344n² + 2063n − 1038, 945)를 반환합니다.
k = 4이면 (2800n⁴ − 15680n³ + 28844n² − 19288n + 4263, 14175)를 반환합니다.
k = 5이면 (12320n⁵ − 73920n⁴ + 130328n³ − 29568n² − 64150n − 5124, 93555)를 반환합니다.
그 외의 경우에는 1.0을 반환합니다.

메인 루틴에서는 다음을 수행합니다.

M := n − 2
p := 2/3, q := 1 − p
(num, den) := exp_factor(n, k)
g := gcd(num, den)
(num/g)/(den/g) 형태의 기약분수를 문자열로 반환합니다.

구현 예제

다음 구현을 통해 더 잘 이해해 보겠습니다.

from math import gcd

def exp_factor(n, k):
    if k == 1:
        return (2*(n-2), 3)
    elif k == 2:
        return (40*n**2 - 144*n + 131, 90)
    elif k == 3:
        return (280*n**3 - 1344*n**2 + 2063*n - 1038, 945)
    elif k == 4:
        return (2800*n**4 - 15680*n**3 + 28844*n**2 - 19288*n + 4263, 14175)
    elif k == 5:
        return (12320*n**5 - 73920*n**4 + 130328*n**3 - 29568*n**2 - 64150*n - 5124, 93555)
    return 1.0

def solve(k, n):
    M = n - 2
    p = 2.0/3
    q = 1 - p

    num, den = exp_factor(n, k)
    g = gcd(num, den)
    return str(int(num/g)) + '/' + str(int(den/g))

k = 1
n = 1000
print(solve(k, n))

입력

1, 1000

출력

1996/3

k = 1, n = 1000을 대입하면 분자는 2 × (1000 − 2) = 1996, 분모는 3이 되어 최종적으로 1996/3이 출력됩니다. 이처럼 차수별 다항식 공식과 최대공약수(gcd)를 활용하면 시뮬레이션 없이도 정확한 기약분수 형태의 기댓값을 손쉽게 구할 수 있습니다.