Асимптотическая локальная обратимость последовательности случайных автоматов с растущим числом внутренних состояний

В. И. Винокуров

Академия криптографии РФ

Аннотация: Изучается последовательность случайных автоматов $\aleph_n(X,Q_n,Y,F_n,\Phi_n)$ с конечными входным $X$ и выходным $Y$ алфавитами, растущим числом $|Q_n|=n$ внутренних состояний и функциями выхода и переходов внутренних состояний $f_{n,t}$ и $\varphi_{n,t}$ в каждый такт $t$ работы автомата, выбираемыми случайно и равновероятно из множеств функций $F_n$ и $\Phi_n$. Доказана возможность асимптотического локального обращения автомата $\aleph_n$. А именно, знак $x_{n,t}$ входной последовательности $\{x_{n,t}\}_{t=1}^T$ автомата в момент времени $t$ при $T,t,n\rightarrow\infty$ так, что $\sqrt{n}=o(\min(t,T-t))$ может быть восстановлен по известной выходной последовательности $\{y_{n,t}\}_{t=1}^T$ и известным последовательностях функций $\{\varphi_{n,t}\}_{t=1}^T$ и $\{f_{n,t}\}_{t=1}^T$ с вероятностью, не меньшей 1/3.

Ключевые слова: конечный автомат, цепь Маркова, стационарное распределение, предельная теорема, распределение Рэлея, распределение Пуассона, метод моментов.

УДК: 519.713.6+519.217.2

Статья поступила: 13.02.2024

DOI: 10.4213/dm1901