Рассматривается классическая схема Бернулли — последовательность независимых случайных величин, одинаково распределенных по мере Лебега $m$ на отрезке $[0,1]$. Пространство реализаций этой схемы есть бесконечномерный куб $\mathcal{X} = ([0, 1]^{\mathbb{N}}, \mu)$ с мерой Лебега $\mu = m^{\mathbb{N}}$. В работе доказывается существование такой функции $k( \cdot )\colon(0, 1) \to \mathbb{R}$ (можно положить $k(\varepsilon) = C/\varepsilon^5$), что для любых $n \in \mathbb{N}$, $\varepsilon \in(0, 1)$ можно выбрать такое измеримое подмножество $\mathcal{X}_{n,\varepsilon} \subset \mathcal{X}$ меры, не меньшей $1 - \varepsilon$, что для любой реализации $x=\{x_n\}_n \in \mathcal{X}_{n, \varepsilon}$ координата $x_n$ в процессе применения алгоритма RSK (Robinson–Schensted–Knuth) достигнет первого столбца $P$-таблицы Юнга в результате не более, чем $k(\varepsilon)n^2$, вставок.
Язык оригиналарусский
Страницы (с-по)78-84
ЖурналФУНКЦИОНАЛЬНЫЙ АНАЛИЗ И ЕГО ПРИЛОЖЕНИЯ
Том54
Номер выпуска2
СостояниеОпубликовано - 2020

    Области исследований

  • алгоритм RSK, перестановки, схема Бернулли

ID: 78523958