Zenn
Open7

時系列データを長さ L のバッファに 確率 p で ランダムな位置のデータと置換する際の性質

Python
統計
確率
時系列
期待値
ピン留めされたアイテム
GesonAnkoGesonAnko
GesonAnkoGesonAnko

バッファの定義

バッファの長さを L (L > 0 \land L \in \mathbb{N}), 追加確率を p \in [0,1]とする。

時系列データはこのように得られる。

\{x_1, x_2, ..., x_L, ..., x_t, ... \}

ここで、 最初 L 個まではバッファに追加していき、 それ以降のデータ x_t (t > L) は 確率 p でランダムな位置のデータと置き換え、 1 - p で破棄する。

そうすると、このように実装が与えられる。

import random

L: int # > 0 の整数
p: float # [0,1]の浮動小数
buffer = []

def add(data):
    if len(buffer) < L: # 最初 L 個は追加
        buffer.append(data)
    else:
        if random.random() > p: # 追加しない
            return
        index = random.randint(0, L - 1) # ランダムな位置を取得
        buffer[index] = data
GesonAnkoGesonAnko

なぜこのようなバッファを考えるか

強化学習、オンライン学習において、経験バッファを実装する際に使うため。
バッファ長が有限であるが、過去のデータもある程度保持しておきたいといったときに、このバッファを用いる。
順序は保持せず、ただデータを持つだけの場合に使う。

GesonAnkoGesonAnko

T ステップ前のデータの生存確率

ここで、 時刻が十分に経過したとして (t \gg L)、 T ステップ前のデータがバッファに残っている確率 f(L, p, T) を計算する。

特定のスロットが時刻 t-k のデータを含む確率 q(k)

新しいデータが追加された際、確率pでランダムな位置のデータと置き換わるため、特定のスロットが選ばれる確率は \frac{p}{L} となる。

\begin{align} q(1) &= \frac{p}{L}\\ q(2) &= \left(1-\frac{p}{L}\right)\cdot\frac{p}{L}\\ q(3) &= \left(1-\frac{p}{L}\right)^2\cdot\frac{p}{L} \end{align}

一般化すると：

q(k) = \frac{p}{L}\left(1-\frac{p}{L}\right)^{k-1} \quad (k \geq 1)

あるスロットが時刻t-T以前のデータを含む確率を求める

ステップ1. 定義を代入する

\sum_{k=T}^{\infty} q(k) = \sum_{k=T}^{\infty} \frac{p}{L}\left(1-\frac{p}{L}\right)^{k-1}

これは時刻t-T以前（t-T, t-(T+1), t-(T+2), \ldots）のデータがバッファの特定のスロットに含まれる確率の合計である。

ステップ2: 定数項を取り出す

\sum_{k=T}^{\infty} \frac{p}{L}\left(1-\frac{p}{L}\right)^{k-1} = \frac{p}{L} \sum_{k=T}^{\infty} \left(1-\frac{p}{L}\right)^{k-1}

ステップ3: 記号の簡略化

計算を簡単にするために、r = \left(1-\frac{p}{L}\right)とおく:

\frac{p}{L} \sum_{k=T}^{\infty} r^{k-1}

ステップ4: 和の変形

k-1 = jと置換すると、k = j+1となるので、k = Tのときj = T-1：

\frac{p}{L} \sum_{j=T-1}^{\infty} r^{j} = \frac{p}{L} \cdot r^{T-1} \sum_{m=0}^{\infty} r^{m}

ここで、j = m + (T-1)と置き換える。

ステップ5: 無限等比級数の和の公式を適用

|r| < 1のとき、無限等比級数の和は次の公式で計算できる：

\sum_{m=0}^{\infty} r^{m} = \frac{1}{1-r}

ステップ6: 公式を代入して計算

\frac{p}{L} \cdot r^{T-1} \cdot \frac{1}{1-r} = \frac{p}{L} \cdot \frac{r^{T-1}}{1-r}

ステップ7: rを元の式に戻す

\frac{p}{L} \cdot \frac{\left(1-\frac{p}{L}\right)^{T-1}}{1-\left(1-\frac{p}{L}\right)} = \frac{p}{L} \cdot \frac{\left(1-\frac{p}{L}\right)^{T-1}}{\frac{p}{L}} = \left(1-\frac{p}{L}\right)^{T-1}

したがって、特定のスロットが時刻t-T以前のデータを含む確率は：

\sum_{k=T}^{\infty} q(k) = \left(1-\frac{p}{L}\right)^{T-1}

全L個のスロットが時刻t-T+1以降のデータのみを含む確率

全L個のスロットが時刻t-T+1以降のデータのみを含む確率、すなわち 時刻 t-T 以前のデータが残らない確率は：

\left[1-\left(1-\frac{p}{L}\right)^{T-1}\right]^L

求める関数

したがって、バッファがTステップ前までのデータを持つ確率f(L,p,T)は：

f(L,p,T) = 1-\left[1-\left(1-\frac{p}{L}\right)^{T-1}\right]^L

可視化

ソースコード
import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib

def f(L, p, T):
    """
    バッファがTステップ前までのデータを持つ確率を計算する関数
    
    引数:
    L -- バッファの長さ
    p -- 置換確率
    T -- ステップ数
    
    戻り値:
    バッファがTステップ前までのデータを持つ確率
    """
    return 1 - (1 - (1 - p/L)**(T-1))**L

# パラメータの設定
L = 10
p_values = np.arange(0.1, 1.1, 0.1)
T_max = 500
T_values = np.arange(1, T_max + 1)

# プロットの設定
plt.figure(figsize=(12, 8))

# 各pに対してグラフをプロット
for p in p_values:
    f_values = [f(L, p, T) for T in T_values]
    plt.plot(T_values, f_values, label=f'p = {p:.1f}')

# グラフの装飾
plt.title(f'バッファがTステップ前までのデータを持つ確率 (L = {L})', fontsize=14)
plt.xlabel('T (ステップ数)', fontsize=12)
plt.ylabel('f(L,p,T) (確率)', fontsize=12)
plt.grid(True, alpha=0.3)
plt.legend(loc='best')
plt.ylim(0, 1.05)

# グラフの表示
plt.tight_layout()
plt.show()

GesonAnkoGesonAnko

バッファが平均的に何ステップ前までデータを保持するか

先ほど、バッファがTステップ以前のデータを持つ確率として：

f(L,p,T) = 1-\left[1-\left(1-\frac{p}{L}\right)^{T-1}\right]^L

を導出した。

f(L,p,T) は あるデータが 時刻 T ステップ経つまでに生き残る確率、すなわち生存関数 (または相補累積分布関数) S(t), P(T \geq t) であり、累積密度関数 F(t) = \left[1-\left(1-\frac{p}{L}\right)^{T-1}\right]^Lを用いて

P(T \geq t) = S(t) = 1 - F(t)

となる。

これを用いて期待値を計算する：

E[T] = \sum_{t=1}^{\infty} P(T \geq t) = \sum_{t=1}^{\infty} \left(1-\left[1-\left(1-\frac{p}{L}\right)^{t-1}\right]^L\right)

簡略化のためにq = 1-\frac{p}{L}とおくと：

E[T] = \sum_{t=1}^{\infty} \left(1-(1-q^{t-1})^L\right)

二項定理を適用して：

\begin{align} (1 - q^{t-1})^L &= \sum_{j=0}^{L} \binom{L}{j} 1^{L-j} (-q^{t-1})^j \\ &= \sum_{j=0}^{L} \binom{L}{j} (-1)^j q^{(t-1)j} \\ &= 1 + \sum_{j=1}^{L} \binom{L}{j} (-1)^j q^{(t-1)j} \end{align}
\begin{align} E[T] &= \sum_{t=1}^{\infty} \Big( 1 - 1 - \sum_{j=1}^{L} \binom{L}{j}(-1)^{j}q^{(t-1)j} \Big) \\ &= \sum_{t=1}^{\infty} \sum_{j=1}^{L} \binom{L}{j}(-1)^{j+1}q^{(t-1)j} \end{align}

和の順序を入れ替え：

E[T] = \sum_{j=1}^{L} \binom{L}{j}(-1)^{j+1}\sum_{t=1}^{\infty}q^{(t-1)j} = \sum_{j=1}^{L} \binom{L}{j}(-1)^{j+1}\sum_{s=0}^{\infty}q^{sj}

ここでs = t-1と置換する。無限級数の和は：

\sum_{s=0}^{\infty}q^{sj} = \frac{1}{1-q^j}

したがって、期待値の厳密な式は：

E[T] = \sum_{j=1}^{L} \binom{L}{j}(-1)^{j+1}\frac{1}{1-q^j} = \sum_{j=1}^{L} \binom{L}{j}(-1)^{j+1}\frac{1}{1-(1-\frac{p}{L})^j}

GesonAnkoGesonAnko

E[T] の近似解の導出

厳密な期待値の計算は、 L が十分に小さい時 (L < 50) 程度なければ、二項定理の組み合わせが爆発することで計算できなくなってしまう。

そこで、近似値を導出する。

方法1: f が十分に小さくなるまで 足し合わせる。

これは愚直だけれども簡単な方法で、 割と大きい値まで 正確に求められる。
普通にPythonで書くと遅くて仕方がないので、 numba を使って高速化する。

ソースコード
import numba
from math import log, exp

@numba.jit(nopython=True)
def expected_oldest_data_age(L, p, max_steps, cutoff=1e-10):
    """
    バッファ内の最も古いデータの年齢の期待値を近似計算
    
    Parameters:
    L (int): バッファの長さ
    p (float): データ置換確率 (0 < p <= 1)
    max_steps (int): 最大ステップ数
    cutoff (float): 打ち切り精度
    
    Returns:
    float: 期待値 E[T]
    """
    expectation = 0.0
    q = 1 - p/L
    log_q = log(q)
    
    # 最初の項（t=1）
    expectation += 1.0  # P(T >= 1) = 1
    
    for t in range(2, max_steps + 1):
        # 効率的に確率を計算
        log_term = (t-1) * log_q
        
        # 数値アンダーフロー対策
        if log_term < -700:  # exp(-700)はほぼ0
            prob = 0
        else:
            term = exp(log_term)
            prob = 1 - (1 - term)**L
        
        expectation += prob
        
        # 確率がカットオフより小さくなったら終了
        if prob < cutoff:
            break
    
    
    return expectation, t, prob

def main():
    # パラメータ設定例
    L_values = [10, 100, 1000, 10_000, 100_000]
    p_values = [0.1, 0.5, 0.9]
    max_steps = 100_000_000
    
    print("バッファ内の最も古いデータの年齢の期待値:")
    print("-" * 100)
    
    for L in L_values:
        for p in p_values:
            expected, t, prob = expected_oldest_data_age(L, p, max_steps)
            print(f"L: {L: >7}\tp {p}\t期待値: {str(expected)[:10]}\t導出時間ステップ: {t: >10} \t打ち切り確率: {prob:.2e}")
            print("-" * 100)

if __name__ == "__main__":
    main()
実行結果
ッファ内の最も古いデータの年齢の期待値:
----------------------------------------------------------------------------------------------------
L:      10      p 0.1   期待値: 291.929888      導出時間ステップ:       2522    打ち切り確率: 9.92e-11
----------------------------------------------------------------------------------------------------
L:      10      p 0.5   期待値: 57.6023617      導出時間ステップ:        495    打ち切り確率: 9.90e-11
----------------------------------------------------------------------------------------------------
L:      10      p 0.9   期待値: 31.5565915      導出時間ステップ:        270    打ち切り確率: 9.60e-11
----------------------------------------------------------------------------------------------------
L:     100      p 0.1   期待値: 5185.28339      導出時間ステップ:      27619    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------
L:     100      p 0.5   期待値: 1035.37964      導出時間ステップ:       5514    打ち切り確率: 9.97e-11
----------------------------------------------------------------------------------------------------
L:     100      p 0.9   期待値: 574.277682      導出時間ステップ:       3058    打ち切り確率: 9.94e-11
----------------------------------------------------------------------------------------------------
L:    1000      p 0.1   期待値: 74851.4658      導出時間ステップ:     299325    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------
L:    1000      p 0.5   期待値: 14967.6986      導出時間ステップ:      59854    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------
L:    1000      p 0.9   期待値: 8313.94654      導出時間ステップ:      33246    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------
L:   10000      p 0.1   期待値: 978756.209      導出時間ステップ:    3223130    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------
L:   10000      p 0.5   期待値: 195747.726      導出時間ステップ:     644614    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------
L:   10000      p 0.9   期待値: 108746.784      導出時間ステップ:     358113    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------
L:  100000      p 0.1   期待値: 12090140.5      導出時間ステップ:   34485493    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------
L:  100000      p 0.5   期待値: 2418023.68      導出時間ステップ:    6897086    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------
L:  100000      p 0.9   期待値: 1343344.02      導出時間ステップ:    3831707    打ち切り確率: 9.99e-11
----------------------------------------------------------------------------------------------------

方法2: 近似式で求める。

どうやら、 次の式で近似的に求められるらしい (Claude曰く)

E[T] \approx \frac{L}{p}\ln{L} + \frac{L}{p}\gamma + O(1)

ここで \gamma \approx 0.5772... はオイラー・マスケローニ定数。

ただ、このまま使用するとこの近似式が正しいかどうかわからないし、おそらくいくつかの微調整項が必要だろう。

よって、 \alpha, \beta を用いて、 次のように表すこととする。

E[T] \approx \alpha \frac{L}{p}\Big(\ln{L} + \gamma \Big) + \beta

そして、 厳密な解や、先に導出した 方法1の正確な近似値を用いて、これらの定数項を最適化する。

ソースコード
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize
import numba
from math import log, exp
import time
import japanize_matplotlib

# オイラー・マスケローニ定数
gamma = 0.57721566490153286

@numba.jit(nopython=True)
def expected_oldest_data_age(L, p, max_steps, cutoff=1e-10):
    """
    バッファ内の最も古いデータの年齢の期待値を近似計算
    
    Parameters:
    L (int): バッファの長さ
    p (float): データ置換確率 (0 < p <= 1)
    max_steps (int): 最大ステップ数
    cutoff (float): 打ち切り精度
    
    Returns:
    float: 期待値 E[T]
    """
    expectation = 0.0
    q = 1 - p/L
    log_q = log(q)
    
    # 最初の項（t=1）
    expectation += 1.0  # P(T >= 1) = 1
    
    for t in range(2, max_steps + 1):
        # 効率的に確率を計算
        log_term = (t-1) * log_q
        
        # 数値アンダーフロー対策
        if log_term < -700:  # exp(-700)はほぼ0
            prob = 0
        else:
            term = exp(log_term)
            prob = 1 - (1 - term)**L
        
        expectation += prob
        
        # 確率がカットオフより小さくなったら終了
        if prob < cutoff:
            break
    
    return expectation


def generate_data():
    """より広範なL, pの組み合わせでデータを生成"""
    # 幅広いLとpの値を設定
    L_values = [10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000]
    p_values = [0.01, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.99]
    max_steps = 100_000_000
    
    results = []
    total = len(L_values) * len(p_values)
    count = 0
    
    print(f"全{total}通りの組み合わせで計算中...")
    
    start_time = time.time()
    for L in L_values:
        for p in p_values:
            count += 1
            if count % 10 == 0 or count == total:
                elapsed = time.time() - start_time
                print(f"進捗: {count}/{total} ({count/total*100:.1f}%) 経過時間: {elapsed:.1f}秒")
            
            expected = expected_oldest_data_age(L, p, max_steps)
            results.append((L, p, expected))
    
    return results


def approximation(L, p, alpha, beta):
    """近似式の計算: E[T] ≈ α(L/p)(ln(L) + γ) + β"""
    return alpha * (L/p) * (np.log(L) + gamma) + beta


def objective_function(params, data):
    """最小化する目標関数（二乗相対誤差の和）"""
    alpha, beta = params
    error_sum = 0
    
    for L, p, exact_value in data:
        predicted = approximation(L, p, alpha, beta)
        # 相対誤差の二乗を使用
        relative_error = (predicted - exact_value) / exact_value
        error_sum += relative_error ** 2
    
    return error_sum


def optimize_parameters(data):
    """最適なα, βを求める"""
    # 初期値
    initial_guess = [1.0, 0.0]
    
    # 最適化の実行
    result = minimize(
        lambda params: objective_function(params, data),
        initial_guess,
        method='Nelder-Mead',
        options={'maxiter': 1000000}
    )
    
    return result.x


def validate_approximation(data, alpha, beta):
    """近似式の精度を検証"""
    errors = []
    
    for L, p, exact_value in data:
        predicted = approximation(L, p, alpha, beta)
        error_percent = 100 * abs(predicted - exact_value) / exact_value
        errors.append(error_percent)
    
    return np.mean(errors), np.std(errors), np.max(errors), np.min(errors)


def plot_results(data, alpha, beta):
    """結果をプロット"""
    # データ整形
    L_values = sorted(list(set([d[0] for d in data])))
    p_values = sorted(list(set([d[1] for d in data])))
    
    # マーカーと色のセット
    markers = ['o', 's', '^', 'v', 'D', '*', 'p', 'h', 'X', '+']
    colors = plt.cm.tab10(np.linspace(0, 1, len(p_values)))
    
    plt.figure(figsize=(14, 8))
    
    # 各pごとにプロット
    for i, p in enumerate(p_values):
        p_data = [(L, exact) for L, p_val, exact in data if p_val == p]
        if not p_data:
            continue
            
        L_subset, exact_values = zip(*p_data)
        
        # 実際の値
        plt.scatter(L_subset, exact_values, 
                    marker=markers[i % len(markers)], 
                    color=colors[i], 
                    label=f'p={p} (実測値)')
        
        # 近似値
        L_range = np.array(L_subset)
        approx_values = [approximation(L, p, alpha, beta) for L in L_range]
        plt.plot(L_range, approx_values, '--', color=colors[i])
    
    plt.xscale('log')
    plt.yscale('log')
    plt.xlabel('バッファ長さ (L)')
    plt.ylabel('最も古いデータの期待年齢 E[T]')
    plt.title(f'バッファ内の最も古いデータの期待年齢\n近似式: E[T] ≈ {alpha:.4f}(L/p)(ln(L) + γ) + {beta:.2f}')
    plt.grid(True, which='both', linestyle='--', alpha=0.6)
    plt.legend(loc='upper left', ncol=2)
    
    plt.tight_layout()
    plt.show()


def main():
    # データ生成
    print("データを生成中...")
    data = generate_data()
    print(f"生成されたデータポイント数: {len(data)}")
    
    # パラメータ最適化
    print("最適なパラメータを計算中...")
    optimal_alpha, optimal_beta = optimize_parameters(data)
    print(f"最適なパラメータ: alpha = {optimal_alpha:.6f}, beta = {optimal_beta:.6f}")
    
    # 精度検証
    mean_error, std_error, max_error, min_error = validate_approximation(data, optimal_alpha, optimal_beta)
    print("\n近似式の精度:")
    print(f"平均相対誤差: {mean_error:.2f}%")
    print(f"標準偏差: {std_error:.2f}%")
    print(f"最大誤差: {max_error:.2f}%")
    print(f"最小誤差: {min_error:.2f}%")
    
    # 最終的な近似式
    print(f"\n最適化された近似式: E[T] ≈ {optimal_alpha:.4f} × (L/p) × (ln(L) + {gamma:.4f}) + {optimal_beta:.2f}")
    
    # L値に対する厳密値と近似値の比較表示（pごとにグループ化）
    print("\n厳密値vs近似値の比較 (サンプル):")
    p_values = sorted(list(set([d[1] for d in data])))
    L_values = sorted(list(set([d[0] for d in data])))
    L_sample = [10, 100, 1000, 10000]  # サンプル表示用
    
    for p in [0.1, 0.5, 0.9]:  # サンプル表示用
        print(f"\np = {p}:")
        print("-" * 70)
        print(f"{'L':<10}{'厳密値':<15}{'近似値':<15}{'相対誤差 (%)':<15}")
        print("-" * 70)
        
        for L in L_sample:
            # データから該当する値を検索
            exact_value = next((exact for L_val, p_val, exact in data if L_val == L and p_val == p), None)
            if exact_value is not None:
                predicted = approximation(L, p, optimal_alpha, optimal_beta)
                error_percent = 100 * abs(predicted - exact_value) / exact_value
                print(f"{L:<10}{exact_value:<15.2f}{predicted:<15.2f}{error_percent:<15.2f}")
    
    # 結果のプロット
    plot_results(data, optimal_alpha, optimal_beta)


if __name__ == "__main__":
    main()
出力
最適なパラメータ: alpha = 1.000486, beta = -0.398272

近似式の精度:
平均相対誤差: 0.19%
標準偏差: 0.29%
最大誤差: 1.61%
最小誤差: 0.01%

最適化された近似式: E[T] ≈ 1.0005 × (L/p) × (ln(L) + 0.5772) + -0.40

厳密値vs近似値の比較 (サンプル):

p = 0.1:
----------------------------------------------------------------------
L         厳密値            近似値            相対誤差 (%)       
----------------------------------------------------------------------
10        291.93         287.72         1.44           
100       5185.28        5184.51        0.01           
1000      74851.47       74885.72       0.05           
10000     978756.21      979231.29      0.05           

p = 0.5:
----------------------------------------------------------------------
L         厳密値            近似値            相対誤差 (%)       
----------------------------------------------------------------------
10        57.60          57.23          0.65           
100       1035.38        1036.58        0.12           
1000      14967.70       14976.83       0.06           
10000     195747.73      195845.94      0.05           

p = 0.9:
----------------------------------------------------------------------
L         厳密値            近似値            相対誤差 (%)       
----------------------------------------------------------------------
10        31.56          31.62          0.19           
100       574.28         575.70         0.25           
1000      8313.95        8320.28        0.08           
10000     108746.78      108803.12      0.05

\alpha = 1.0005 (大体 1.0), \beta = -0.398272 (大体 -0.40)であることが求められた。

よって、 近似値を求める際はこのようにすると良いだろう。

E[T] \approx \frac{L}{p}\Big(\ln{L} + \gamma \Big) - 0.40

ただ、どちらの値もLが大きい時に、ほとんど計算には影響しないので、使わなくても良いだろう。

Claudeに教えてもらった内容

理論的近似値 E[T] \approx \frac{L}{p}\ln{L} + O(1) の導出

この近似式の導出を詳細に解説します。これは確率論における極値理論（Extreme Value Theory）の応用例です。

1. 問題の再確認

まず、問題設定を振り返ります：

  • 長さ L のバッファがある
  • 各時刻で確率 p で新しいデータがランダムに選ばれた位置に挿入される
  • バッファ内の最も古いデータの年齢 T の期待値を求めたい

2. 個々のスロットのデータ寿命分布

各バッファスロットは、時刻ごとに確率 \frac{p}{L} で新しいデータに置き換えられます。つまり、あるスロット内のデータの寿命は幾何分布に従います：

P(X_i = k) = \left(1 - \frac{p}{L}\right)^{k-1} \cdot \frac{p}{L} \quad \text{for } k \geq 1

ここで X_i は i 番目のスロット内のデータの寿命です。

この幾何分布の期待値は：

E[X_i] = \frac{1}{p/L} = \frac{L}{p}

3. 最大値の漸近的挙動

バッファ内の最も古いデータの年齢 T は、L 個の独立な確率変数 X_1, X_2, \ldots, X_L の最大値です：

T = \max(X_1, X_2, \ldots, X_L)

この最大値の期待値の漸近的挙動を求めるために、極値理論を適用します。

4. 極値理論の適用

幾何分布は指数分布の離散版と見なせます。極値理論によると、独立同分布に従う確率変数の最大値の分布は、適切にスケーリングすると、極値分布（ここではタイプIのグンベル分布）に収束します。

幾何分布の最大値の期待値について、次の近似が成り立ちます：

E[\max(X_1, X_2, \ldots, X_L)] \approx \frac{L}{p}\ln{L} + \frac{L}{p}\gamma + O(1)

ここで \gamma \approx 0.5772... はオイラー・マスケローニ定数です。

5. 最終的な近似式

常数項をまとめて O(1) で表現すると：

E[T] \approx \frac{L}{p}\ln{L} + O(1)

という近似式が得られます。

6. 直感的な解釈

この近似式は直感的にも理解できます：

  • 各スロット単体のデータの期待寿命は \frac{L}{p}
  • L 個の独立なスロットの最大値を取ると、対数因子 \ln{L} が掛かる
  • したがって、最も古いデータの期待年齢は \frac{L}{p}\ln{L} のオーダー

関連する重要な定理

この導出に関連する重要な定理には以下があります：

  1. フィッシャー・ティペット・グネデンコの定理（Fisher-Tippett-Gnedenko theorem）：
    独立同分布に従う確率変数の最大値の分布は、適切な正規化を行うと、極値分布の一つに収束します。

  2. レンガーの定理（Rényi's theorem）：
    指数分布や幾何分布の最大値の漸近挙動を特徴づけます。

  3. オーダー統計量の理論（Order Statistics Theory）：
    確率変数を順序付けした際の統計的性質を扱う理論です。

極値理論は、洪水や地震などの極端な事象のモデリング、金融リスク管理、待ち行列理論など、様々な応用分野で重要な役割を果たしています。

GesonAnkoGesonAnko

期待生存長が T になるように 確率 p を定める

単に式変形をして、

p = \alpha \frac{L}{T - \beta } \Big (\ln L + \gamma \Big)