НИУ ВШЭ, 2021 - Предельные распределения, возникающие в задаче восстановления отдельных отрезков

Утверждение 2: Ожидаемое количество ограниченных отрезков длины s в сообщении длиной N символов: (N − s + 1) ∙ P( s li ∙ li ∙ … ∙ li ≤ L .1 2 s ) Вероятность появления ограниченных отрезков Утверждение 3: а) Условная вероятность появления ограниченного отрезка при условии, что предыдущий отрезок ограничен: s ∬ f(x, y)dxdy lim P(Si < s   S 0i−1 < s) = s → ∞ Φ( s − sμ ,     ) sσ 2 2 1 − 1 (x − μ) 2(. [...] 2πσ2 1 − ρ2 s б) Ожидаемая средняя геометрическая величина следующего отрезка при условии ограниченности предыдущего: φ( s − sμs − 1 sσ ) lim E(Si   Si−1 < s) = μ − σ , s → ∞ s Φ( s − sμsσ ) где φ – плотность стандартного нормального распределения, Φ – функция Гаусса. [...] Вероятность появления ограниченных отрезков Утверждение 4: Вероятность того, что все отрезки сообщения одновременно являются ограниченными, стремится к многомерному sμ → → → нормальному распределению lim P(S1 < s,   S2 < s,  …,   SN−s+1 < s) = lim P S < s = N θ , Σs , где θ = sμ… – вектор s → ∞ s → ∞ ( ) ( ) sμ средних значений sσ2 ⋯ σS1, SN−s+1 Σs = ⋮ ⋱ ⋮ - ковариационная матрица, на пересечении. [...] C iN 10 15 20 25 Утверждение 5: Если восстановлению подвергается участок сообщения на русском языке 8 3 1 1 1 (мощность алфавита – 35 символов) длиной s символов со среднем числом 10 24 1 1 1 вариантов знаков li, то вероятность появления ki осмысленных вариантов восстановления данного отрезка: 12 143 2 1 1 14 667 11 1 1 2Hs∙s! ∙ (35s − 2Hs∙s)! ∙ lsi ! ∙ (35s − lsP(k ) = i ) ! i   16 2534 80 1 1k !. [...] Утверждение 6: Вероятность найти ровно 1 осмысленный текст (истинный) при s → ∞: s P(1) ≈ e−2( l ⋅ 2 H 35 ) Утверждение 7: Если количество осмысленных текстов k = 2s⋅ β, тогда вероятность получить k осмысленных текстов при восстановлении отрезка длиной s → ∞: 1 ((H − β + log l2 35 )s+log βs β 12e)⋅2 − 2 s− 2 P(k = 2βs) ≈ 2.