Гийом Шапюи — Композиция случайных функций и реконструкция слов.

Эта лекция была частью тематической программы «Статистическая механика и комбинаторика дискретных плоских структур», проходившей в ESI с 14 сентября по 30 октября 2026 года. Даны две функции a:[n]→[n] и b:[n]→[n], выбранные равномерно случайным образом. Любое слово w длины k на множестве {a,b} порождает случайную функцию w:[n]→[n] путем композиции. Мы изучаем следующий вопрос: предполагая, что w фиксировано, но неизвестно, и n стремится к бесконечности, содержит ли случайная функция w достаточно информации, чтобы (частично) восстановить слово w с достаточно высокой вероятностью в одной или нескольких независимых одинаково распределенных выборках? Мы показываем, что это возможно с конечным числом выборок с достаточно высокой вероятностью, но оставляем открытым вопрос о том, можно ли это сделать в одной выборке. На техническом уровне большая часть работы посвящена изучению количества листьев в некоторых «самоперекрывающихся» случайных деревьях, а также некоторым трансцендентным свойствам башен экспоненциальных функций, связанным с гипотезой Шануэля из теории чисел. Это совместная работа с Гильемом Перарно.