수열, 극한, 점근¶

import math
import numpy as np

# === (1 + 1/n)^n → e ===
ns = [10, 100, 1_000, 10_000, 100_000]
for n in ns:
    approx = (1 + 1/n)**n
    print(f"n={n:>7d}: (1+1/n)^n = {approx:.8f}, error = {abs(approx - math.e):.2e}")

# === Geometric series partial sums ===
r = 0.5
partial = np.cumsum(r ** np.arange(20))
exact = 1 / (1 - r)
print(f"\nGeometric r=0.5: S_19 = {partial[-1]:.10f}, exact = {exact}")

# === Taylor approximation of e^x at x = 0.3 ===
x = 0.3
for k in range(1, 7):
    taylor = sum(x**n / math.factorial(n) for n in range(k + 1))
    print(f"order {k}: {taylor:.8f}, exact: {math.exp(x):.8f}")

# === Demonstrating o(1/n) vs O(1/n) ===
n = np.arange(1, 50)
print("\nlog(n) / n   (o(1)? yes):", (np.log(n) / n)[-1])
print("sin(n) / n^2 (O(1/n^2)):", (np.sin(n) / n**2)[-1])

출력:

n=     10: (1+1/n)^n = 2.59374246, error = 1.25e-01
n=    100: (1+1/n)^n = 2.70481383, error = 1.35e-02
n=   1000: (1+1/n)^n = 2.71692393, error = 1.36e-03
n=  10000: (1+1/n)^n = 2.71814593, error = 1.36e-04
n= 100000: (1+1/n)^n = 2.71826824, error = 1.36e-05

Geometric r=0.5: S_19 = 1.9999980927, exact = 2.0
order 1: 1.30000000, exact: 1.34985881
order 2: 1.34500000, exact: 1.34985881
order 3: 1.34950000, exact: 1.34985881
order 4: 1.34983750, exact: 1.34985881
order 5: 1.34985775, exact: 1.34985881
order 6: 1.34985876, exact: 1.34985881

log(n) / n   (o(1)? yes): 0.07942490404307401
sin(n) / n^2 (O(1/n^2)): -0.00039723142555579834

(1) 비례상수는 \(e/2 = 1.359141\ldots\)이다. 로그를 취하고 \(\log(1+u) = u - u^2/2 + u^3/3 - \cdots\)를 \(u = 1/n\)에 쓴다.

지수를 다시 씌우면서 \(e^{-t} = 1 - t + t^2/2 - \cdots\)를 \(t = 1/(2n) - 1/(3n^2)\)에 쓰면

이다(\(1/3 + 1/8 = 11/24\)). 따라서 오차가

이고 선행항의 계수가 \(e/2\)다. 수렴은 \(\Theta(1/n)\)으로 느리다. \(n\)을 10배 늘려야 자릿수 하나를 얻는다는 출력이 바로 그 뜻이다.

(2) \(S_{19} = 2 - 2^{-19}\)이다. 유한 등비합 공식에서

이고 \(2^{-19} = 1.907349 \times 10^{-6}\)이므로 \(S_{19} = 1.99999809265\ldots\)다. 열째 자리로 끊으면 \(1.9999980927\)로 출력과 정확히 같다. 이쪽 수렴은 기하적이어서 항을 하나 더할 때마다 오차가 절반으로 줄고, 20항만으로 여섯 자리를 얻는다. (1)의 \(\Theta(1/n)\)과 견주면 차이가 분명하다.

(3) 차수를 하나 올리면 오차가 약 \((k+2)/x\)분의 1로 줄어든다. 차수 \(k\) 근사의 절단오차는 남은 항들의 합이고 그 선행항이 \(x^{k+1}/(k+1)!\)이다.

그러므로 \(k \to k+1\)에서 선행항의 비가 \(x/(k+2)\), 곧 오차는 \((k+2)/x\)분의 1이 된다. \(x = 0.3\)이니 \(k = 1 \to 2\)에서 \(3/0.3 = 10\)배, \(k = 2 \to 3\)에서 \(4/0.3 = 13.3\)배, \(k = 4 \to 5\)에서 \(6/0.3 = 20\)배다. 출력의 오차를 차례로 재면 \(4.986\times10^{-2}\), \(4.859\times10^{-3}\), \(3.588\times10^{-4}\), \(2.131\times10^{-5}\), \(1.058\times10^{-6}\), \(4.508\times10^{-8}\)이고 연속한 비가 \(10.3\), \(13.5\), \(16.8\), \(20.1\), \(23.5\)다. 예측 \(10\), \(13.3\), \(16.7\), \(20\), \(23.3\)과 맞는다. 실제 오차는 선행항보다 조금 크며(\(k = 5\)에서 비가 \(1.0445\)) 뒤따르는 항들 때문이다. 차수가 올라갈수록 그 비가 1로 간다.

(4) 아니다. \(\log n / n\)은 \(O(1/n)\)이 아니다. \(O(1/n)\)이라면 어떤 상수 \(C\)에 대해 \(\log n / n \le C/n\), 곧 \(\log n \le C\)가 모든 \(n\)에서 성립해야 한다. \(\log n\)은 무한히 커지므로 그런 \(C\)는 없다. 비를 재 보면 \(n = 49\)에서 \(3.89\), \(n = 10^6\)에서 \(13.82\), \(n = 10^{12}\)에서 \(27.63\)으로 계속 자란다. 올바른 분류는

이다. 코드 안의 주석 (o(1)? yes)는 맞고, 머리글의 o(1/n)은 이 수열에 해당하지 않는다. \(o(1/n)\)에 해당하는 것은 둘째 수열이다. \(\lvert \sin n \rvert \le 1\)이므로 \(\lvert \sin(n)/n^2 \rvert \le 1/n^2\)이고, \(n^2\)로 나눈 것이 \(1/n\)보다 한 차수 빠르므로

이다. 다만 \(\Theta(1/n^2)\)은 아니다. \(n \bmod 2\pi\)가 \([0, 2\pi)\)에 고르게 퍼지므로 \(\sin n\)이 0에 얼마든지 가까워지는 \(n\)이 있고, 그때 분자가 함께 작아진다. 출력의 \(n = 49\)에서는 \(\sin 49 = -0.9538\)이 마침 \(\pm 1\) 근처라 상한에 거의 닿아 있어 \(-3.972\times10^{-4} \approx -0.954/2401\)이지만, \(n = 10^6\)에서는 \(\lvert \sin n \rvert = 0.350\)으로 세 배 작다. 점근 표기에서 상한과 정확한 차수를 구별해야 하는 자리가 이런 곳이다.

import math

# === (1 + 1/n)^n 의 오차가 e/(2n) 인가 ===
print(f"e/2 = {math.e / 2:.6f}")
for n in [10, 100, 1_000, 10_000, 100_000]:
    err = math.e - (1 + 1 / n) ** n
    print(f"n={n:>7d}:  오차 {err:.3e}   n*오차 {n * err:.5f}   "
          f"두 항 예측 {math.e * (1 / (2 * n) - 11 / (24 * n ** 2)):.3e}")

# === 등비급수 부분합은 2 - 2^-19 이다 ===
S19 = sum(0.5 ** k for k in range(20))
print(f"\n2 - 2^-19 = {2 - 2.0 ** -19:.10f}   코드의 S_19 = {S19:.10f}   "
      f"2^-19 = {2.0 ** -19:.6e}")

# === 테일러 절단오차의 선행항은 x^(k+1)/(k+1)! 이다 ===
x = 0.3
for k in range(1, 7):
    taylor = sum(x ** n / math.factorial(n) for n in range(k + 1))
    err = math.exp(x) - taylor
    lead = x ** (k + 1) / math.factorial(k + 1)
    print(f"order {k}: 오차 {err:.3e}  선행항 x^{k + 1}/{k + 1}! = {lead:.3e}  "
          f"비 {err / lead:.4f}")

# === log(n)/n 은 O(1/n) 이 아니다 ===
for n in [49, 10 ** 3, 10 ** 6, 10 ** 12]:
    print(f"n={n:>13d}:  n*log(n)/n = log n = {math.log(n):.4f}   "
          f"n^2*|sin n|/n^2 = |sin n| = {abs(math.sin(n)):.4f}")

출력:

e/2 = 1.359141
n=     10:  오차 1.245e-01   n*오차 1.24539   두 항 예측 1.235e-01
n=    100:  오차 1.347e-02   n*오차 1.34680   두 항 예측 1.347e-02
n=   1000:  오차 1.358e-03   n*오차 1.35790   두 항 예측 1.358e-03
n=  10000:  오차 1.359e-04   n*오차 1.35902   두 항 예측 1.359e-04
n= 100000:  오차 1.359e-05   n*오차 1.35913   두 항 예측 1.359e-05

2 - 2^-19 = 1.9999980927   코드의 S_19 = 1.9999980927   2^-19 = 1.907349e-06
order 1: 오차 4.986e-02  선행항 x^2/2! = 4.500e-02  비 1.1080
order 2: 오차 4.859e-03  선행항 x^3/3! = 4.500e-03  비 1.0797
order 3: 오차 3.588e-04  선행항 x^4/4! = 3.375e-04  비 1.0631
order 4: 오차 2.131e-05  선행항 x^5/5! = 2.025e-05  비 1.0522
order 5: 오차 1.058e-06  선행항 x^6/6! = 1.012e-06  비 1.0445
order 6: 오차 4.508e-08  선행항 x^7/7! = 4.339e-08  비 1.0388
n=           49:  n*log(n)/n = log n = 3.8918   n^2*|sin n|/n^2 = |sin n| = 0.9538
n=         1000:  n*log(n)/n = log n = 6.9078   n^2*|sin n|/n^2 = |sin n| = 0.8269
n=      1000000:  n*log(n)/n = log n = 13.8155   n^2*|sin n|/n^2 = |sin n| = 0.3500
n=1000000000000:  n*log(n)/n = log n = 27.6310   n^2*|sin n|/n^2 = |sin n| = 0.6112

\(n \cdot (\text{오차})\)가 \(1.2454 \to 1.3591\)로 \(e/2 = 1.359141\)에 올라붙고, 두 항까지 맞춘 예측은 \(n \ge 100\)에서 네 자리가 모두 일치한다. \(n = 10\)에서만 \(1.235\) 대 \(1.245\)로 어긋나는데, 버린 \(O(n^{-3})\)항이 거기서는 아직 무시할 만큼 작지 않기 때문이다. 점근식은 \(n\)이 커질 때의 진술이고, 작은 \(n\)에서 맞는다는 보장은 어디에도 없다. 9장 이후의 점근 신뢰구간을 작은 표본에 쓸 때 되풀이될 경고가 이것이다.

계산하면

이다. \(\varepsilon > 0\)이 주어지면 \(N = \lceil 5/\varepsilon - 2 \rceil\)로 두자. 그러면 모든 \(n > N\)에 대해

이다. 따라서 \(|a_n - 3| < \varepsilon\)이다. \(\square\)

(a) 부분합은

이다. \(|r| < 1\)이면 \(r^{n+1} \to 0\)이므로 \(S_n \to 1/(1 - r)\)이다. \(|r| \ge 1\)이면 \(|r^k|\)가 0으로 가지 않아 발산 판정법에 걸리므로 급수가 발산한다.

(b)

로그를 취한다. 고정된 \(x\)와, \(x/n\)이 \(\ln(1 + \cdot)\)의 정의역에 들어갈 만큼 큰 \(n\)에 대해,

이다. 여기서 \(u = 0\) 주위의 \(\ln(1 + u)\)의 테일러 전개를 썼다. 우변은 \(x\)로 수렴하고 \(\exp\)는 연속이므로

이다. \(\square\)

\(\varepsilon > 0\)이라 하자. \(n > N_1 \Rightarrow |a_n - L| < \varepsilon\)인 \(N_1\)과 \(n > N_2 \Rightarrow |c_n - L| < \varepsilon\)인 \(N_2\)를 고른다. \(a_n \le b_n \le c_n\)이 성립하기 시작하는 경계를 \(N_3\)이라 하고 \(N = \max(N_1, N_2, N_3)\)으로 두자.

\(n > N\)에 대해

이므로 \(|b_n - L| < \varepsilon\)이다. \(\square\)

중심극한정리에 의해 \(\sqrt{n}(\bar{X}_n - p) \xrightarrow{d} N(0, p(1 - p))\)이다. 델타 방법을 쓰면

이다. \(g(p) = 2 \arcsin(\sqrt{p})\)를 미분하면

이다. 따라서 모든 \(p \in (0, 1)\)에 대해 \([g'(p)]^2 \cdot p(1-p) = 1\)이므로 극한은 \(N(0, 1)\)이다. \(\square\)

비대칭 예: \(f(n) = 1\), \(g(n) = n\). 그러면 \(f(n) = O(g(n))\)이지만(\(C = 1\)로 두면 된다) \(g(n)/f(n) = n \to \infty\)이므로 \(g(n) \ne O(f(n))\)이다.

동치관계: \(f \asymp g\)(곧 \(f = \Theta(g)\))일 필요충분조건은 어떤 \(0 < c_1 \le c_2 < \infty\)와 \(N\)이 있어 \(n > N\)에 대해 \(c_1 |g(n)| \le |f(n)| \le c_2 |g(n)|\)이 성립하는 것이다. 이 관계는 반사적이고 (정의상) 대칭이며 추이적이다. "같은 증가 차수"를 포착한다.

\(f \asymp g\)이지만 \(f \not\sim g\): \(f(n) = n\), \(g(n) = 2n\)을 잡자. \(c_1 = 1/2\), \(c_2 = 2\)가 통하므로 \(f \asymp g\)이다. 그러나 \(f(n)/g(n) = 1/2 \ne 1\)이므로 점근적으로 동치는 아니다. \(\square\)

\(\varepsilon > 0\)이라 하자. \(n > N_1\)이면 \(|a_n - L| < \varepsilon/2\)인 \(N_1\)을 고른다. \(n > N_1\)에 대해

이다. 두 번째 합은 \(\frac{n - N_1}{n}\cdot\frac{\varepsilon}{2} < \frac{\varepsilon}{2}\)로 눌린다. 첫 번째 합의 분자 \(\sum_{k \le N_1}|a_k - L|\)는 \(n\)과 무관한 고정된 상수 \(C\)이므로, \(n > 2C/\varepsilon\)이면 \(C/n < \varepsilon/2\)이다. 따라서 \(N = \max(N_1, \lceil 2C/\varepsilon\rceil)\)로 두면 \(n > N\)일 때 \(|\bar{a}_n - L| < \varepsilon\)이다. \(\square\)

증명의 구조를 보아 두라. 수열의 앞부분은 아무리 나빠도 개수가 유한하므로 \(1/n\)에 씻겨 내려가고, 뒷부분은 이미 \(L\)에 가깝다. 유한개의 나쁜 항은 평균에 해를 끼치지 못한다는 이 논법은 큰수의 법칙 증명에서 그대로 되풀이된다.

역은 거짓이다. \(a_n = (-1)^n\)은 발산하지만 부분합이 \(-1\)과 \(0\) 사이를 오갈 뿐이므로 \(\bar{a}_n \to 0\)이다.

import numpy as np

n = np.arange(1, 100_001)
for a, name in [(1 / n, "1/n"), ((-1.0) ** n, "(-1)^n")]:
    cesaro = np.cumsum(a) / n
    print(f"{name:>8}:  a_100000 = {a[-1]:>10.6f}   "
          f"체사로 평균 = {cesaro[-1]:.8f}")

출력:

     1/n:  a_100000 =   0.000010   체사로 평균 = 0.00012090
  (-1)^n:  a_100000 =   1.000000   체사로 평균 = 0.00000000

\(a_n = 1/n\)일 때 체사로 평균은 \(\approx (\ln n)/n\)이라 \(0\)으로 가되 원래 수열보다 훨씬 느리다(\(10^{-5}\) 대 \(1.2 \times 10^{-4}\)). 평균을 취하는 것은 수렴을 안정시키지만 빠르게 하지는 않는다.

\(\theta\) 주위에서 2차까지 전개하면 \(g'(\theta) = 0\)이므로 1차항이 사라지고

이 남는다. 양변에 \(n\)을 곱하면

이다. 중심극한정리로 \(\sqrt{n}(\bar{X}_n - \theta) \xrightarrow{d} N(0, \sigma^2)\)이고, 연속사상정리를 제곱함수에 적용하면 그 제곱이 \(\sigma^2\chi^2_1\)로 수렴한다. \(\square\)

속도가 달라진 점에 주목하라. 정규화 상수가 \(\sqrt{n}\)이 아니라 \(n\)이다. \(g'(\theta) = 0\)이면 \(g\)가 \(\theta\) 근처에서 평평해서 오차를 눌러 주므로, \(g(\bar{X}_n)\)이 \(g(\theta)\)에 더 빨리 수렴한다. 대가는 극한분포가 정규가 아니라 한쪽으로 치우친 카이제곱이라는 것이다.

import numpy as np
from scipy import stats

rng = np.random.default_rng(0)
n, B = 2_000, 200_000
xbar = rng.binomial(n, 0.5, size=B) / n
T = n * (xbar * (1 - xbar) - 0.25)       # g(p) = p(1-p), p = 1/2

# g''(p) = -2, sigma^2 = p(1-p) = 1/4  =>  극한은 -(1/4) chi^2_1
print(f"모의  평균 {T.mean():>8.4f}   분산 {T.var():.4f}")
print(f"이론  평균 {-0.25:>8.4f}   분산 {2 * 0.25**2:.4f}")

print("\n분위수(5%, 50%, 95%)")
print("  모의:", np.quantile(T, [.05, .5, .95]).round(4))
print("  이론:", (-0.25 * stats.chi2.ppf([.95, .5, .05], 1)).round(4))

출력:

모의  평균  -0.2506   분산 0.1254
이론  평균  -0.2500   분산 0.1250

분위수(5%, 50%, 95%)
  모의: [-9.680e-01 -1.125e-01 -5.000e-04]
  이론: [-0.9604 -0.1137 -0.001 ]

이론 분위수에서 확률이 뒤집혀 있는(\(0.95 \to 0.05\)) 이유는 \(g''< 0\)이라 \(-1/4\)을 곱하면서 부호가 바뀌기 때문이다. 극한분포 전체가 음수 쪽에 있는데, 이는 \(p = 1/2\)가 \(p(1-p)\)의 최댓값이라 어떤 추정값을 넣어도 \(0.25\)를 넘을 수 없기 때문이다. 표본분산의 편향과 같은 종류의 현상이다.

스털링 근사를 세 번 쓰면

이다.

import math

print("스털링 근사의 상대오차")
for k in (1, 5, 10, 50, 100):
    s = math.sqrt(2 * math.pi * k) * (k / math.e) ** k
    rel = abs(s - math.factorial(k)) / math.factorial(k)
    print(f"  n={k:>3}:  상대오차 {rel:.3e}   1/(12n) = {1 / (12 * k):.3e}")

print("\n중심이항계수")
for k in (10, 100, 1000):
    log_exact = math.lgamma(2 * k + 1) - 2 * math.lgamma(k + 1)
    log_approx = k * math.log(4) - 0.5 * math.log(math.pi * k)
    print(f"  n={k:>4}:  근사/정확 = {math.exp(log_approx - log_exact):.6f}")

출력:

스털링 근사의 상대오차
  n=  1:  상대오차 7.786e-02   1/(12n) = 8.333e-02
  n=  5:  상대오차 1.651e-02   1/(12n) = 1.667e-02
  n= 10:  상대오차 8.296e-03   1/(12n) = 8.333e-03
  n= 50:  상대오차 1.665e-03   1/(12n) = 1.667e-03
  n=100:  상대오차 8.330e-04   1/(12n) = 8.333e-04

중심이항계수
  n=  10:  근사/정확 = 1.012573
  n= 100:  근사/정확 = 1.001251
  n=1000:  근사/정확 = 1.000125

\(n = 1\)에서도 상대오차가 \(8\%\)에 불과하고, 그 오차가 \(1/(12n)\)과 소수점 셋째 자리까지 맞는다. 이는 우연이 아니라 스털링 급수의 다음 항이다.

확률적 의미. 공정한 동전을 \(2n\)번 던져 앞면이 정확히 절반 나올 확률은

이다. 가장 있음직한 결과조차 확률이 \(0\)으로 간다. 이것이 중심극한정리를 밀도의 언어로 본 모습이다. 확률질량이 폭 \(\sqrt{n}\)에 걸쳐 퍼지므로 개별 점의 확률은 \(n^{-1/2}\)로 줄어든다. \(n = 50\)번 던져 앞면이 정확히 \(25\)번일 확률은 약 \(1/\sqrt{25\pi} \approx 0.113\)이다. \(\square\)

큰 계승을 다룰 때는 위 코드처럼 로그 공간에서 계산하라. \(4^{1000}\)은 배정밀도 부동소수점에서 넘침을 일으키지만 math.lgamma는 아무 문제가 없다.

(a) \(|f_n| \le C_1|a_n|\), \(|g_n| \le C_2|b_n|\)이 \(n > N\)에서 성립한다고 하자. \(m_n = \max(|a_n|, |b_n|)\)이라 두면

이므로 상수 \(C_1 + C_2\)가 통한다.

(b) \(f_n/a_n \to 0\)이고 \(|g_n| \le C|b_n|\)이라 하자. 그러면

이다.

(c) \(|f_n| \le Cn^{-1/2}\)이면 \(|f_n^2| \le C^2 n^{-1}\)이다. 상수가 \(C^2\)으로 바뀔 뿐 차수는 제곱된다.

(c)는 델타 방법의 테일러 전개에서 2차 나머지항을 버릴 수 있는 근거다. 오차가 \(O_p(n^{-1/2})\)이면 그 제곱은 \(O_p(n^{-1})\)이라 한 차수 작다.

import numpy as np

print(f"{'n':>10} {'n^-1/2':>12} {'n^-1':>12} {'1/log n':>12}")
for n in (10, 100, 10_000, 1_000_000):
    print(f"{n:>10} {n ** -0.5:>12.6f} {1 / n:>12.6f} {1 / np.log(n):>12.6f}")

# 오차를 1/10로 줄이려면 표본이 얼마나 더 필요한가
print("\n오차를 1/10로 줄이는 데 필요한 표본 크기 (n = 10^6 에서 출발)")
n0 = 10 ** 6
print(f"  n^-1/2  속도: n -> 100 n      = {100 * n0:.3e}")
print(f"  n^-1    속도: n -> 10 n       = {10 * n0:.3e}")
print(f"  1/log n 속도: n -> n^10       = 10^{10 * 6}")

출력:

         n       n^-1/2         n^-1      1/log n
        10     0.316228     0.100000     0.434294
       100     0.100000     0.010000     0.217147
     10000     0.010000     0.000100     0.108574
   1000000     0.001000     0.000001     0.072382

오차를 1/10로 줄이는 데 필요한 표본 크기 (n = 10^6 에서 출발)
  n^-1/2  속도: n -> 100 n      = 1.000e+08
  n^-1    속도: n -> 10 n       = 1.000e+07
  1/log n 속도: n -> n^10       = 10^60

해석. \(n^{-1/2}\)은 정칙 모수추정의 표준 속도다. 정밀도를 한 자릿수 올리려면 자료가 \(100\)배 필요하다. \(n^{-1}\)은 초효율 속도로, 균등분포 \(U(0,\theta)\)에서 \(\hat\theta = \max_i X_i\)가 이 속도를 낸다. 지지집합의 경계가 정보를 특별히 많이 주기 때문이다.

\(1/\log n\)은 재앙에 가깝다. 표본이 \(10^6\)개여도 오차가 \(0.072\)에 머문다. 더 나쁜 것은 개선의 값이다. 오차를 열 배 줄이려면 \(\log n\)을 열 배로 만들어야 하므로 \(n \to n^{10}\), 곧 표본이 \(10^{60}\)개 필요하다. 앞의 두 속도처럼 일정한 배수로 해결되는 문제가 아니다. 고차원 비모수 추정에서 이런 속도가 나타나며, 차원의 저주를 정량화한 것이 바로 이것이다. 문제를 모수적으로 좁히는 것이 단순한 편의가 아니라 실현 가능성의 문제인 이유다. \(\square\)