Какой вопрос решают
Как сгенерировать целочисленную таблицу, сохранив суммы по строкам и столбцам? Например, синтетические количества поставок между складами и магазинами. Должны ли все допустимые таблицы иметь одинаковую вероятность? Это отдельный выбор модели.
Одна работа заявляет точную равномерную выборку обычных таблиц с произвольными полями за ожидаемое полиномиальное битовое время. Другая — FPRAS для числа таблиц с индивидуальными верхними границами ячеек, включая нулевые запреты.
Почему выбрано: Доступная инженерная задача с важным и наглядным риском неправильной вероятностной интерпретации.
До и после
Предшественники охватывали, в частности, фиксированное число строк или специальные режимы полей; нулевые/единичные ограничения связывают задачу с двудольными паросочетаниями. Стандартный scipy.stats.random_table моделирует условную независимость, а не равномерность по таблицам: вероятность пропорциональна 1/∏Xᵢⱼ!, если поля фиксированы.
Внешние первичные источники: SciPy: scipy.stats.random_table · Dyer, Kannan, Mount — Sampling contingency tables.
Точное утверждение и условия
115-01, теорема 1.1, PDF с. 1: неотрицательные целые поля r,c с общей суммой N, обе размерности переменны. Приближённый генератор имеет TV-ошибку ≤2⁻ᵏ и полиномиальное время от m,n,log(N+1),k на каждом запуске. Точный генератор завершается почти наверное, а полиномиальна только ожидаемая стоимость. 115-02, теорема 1.1, с. 1: вход включает целые 0≤Xᵢⱼ≤bᵢⱼ, все числа в двоичном виде; относительная ошибка ε с вероятностью ≥1−δ, каждый запуск полиномиален по L,ε⁻¹,log δ⁻¹; при невозможности точный ноль.
Источник: указанные теоремы в локальных PDF ниже. Формулировка пересказана, но ключевые кванторы, модель и оговорки сохранены.
Три уровня объяснения
Следующие аналогии и объяснения — наша интерпретация, не дополнительные теоремы.
Загрузка локального эксперимента…
Архитектура доказательства
Пересказ вводного обзора, а не построчная проверка доказательства.
Для обычных таблиц получить быстро смешиваемое взвешенное представление и приблизительную условную выборку с контролем ошибки в битах точности.
Добиться точного закона редкой корректирующей ветвью; она объясняет отличие ожидаемого времени от ограничения каждого исполнения.
Для ограниченных таблиц разделить малые и большие ёмкости, интегрировать большие координаты через лес и оценить отношения нормировок. Это отдельное доказательство, не автоматическое расширение точного генератора.
Что известно о проверке
Описания охвата содержат утверждения о выборке и подсчёте, но не заменяют исходники. Важно сопоставлять отдельные теоремы: точная выборка без запретных ячеек не равна точной выборке при произвольных bᵢⱼ.
Читать локальное описание формального охвата
Наличие PDF, извлечение текста, успешный маленький эксперимент и внешний результат-предшественник — разные виды свидетельств. Ни один из них здесь не отмечен как независимое подтверждение всей новой теоремы.
Практика: наш вывод, не обещание автора
Нулевые модели и генератор тестовых данных с явно выбранным законом. MVP на малых размерах может использовать полный перебор; для условной независимости — существующий генератор. Подмена одной модели другой способна изменить статистический вывод.
Ограничения переноса
У точного генератора возможны крайне дорогие редкие исполнения. В тексте есть заведомо большие степени параметров. Дополнительные запреты, вещественные значения, приватность и статистическая пригодность не следуют из основной теоремы. Практическое ускорение не измерено.
Планы проверки: Генератор таблиц с явно выбранной вероятностной моделью.
Исходники и реальный охват чтения
Номера страниц относятся к физическим страницам PDF, начиная с 1. Ссылки на GitHub не закреплены на текущем commit; воспроизводимый источник — локальный путь и SHA-256.
115-01 · Exact Uniform Sampling of Contingency Tables with Arbitrary Margins
Реальный охват: Просмотрены PDF с. 1–3: Теорема и начальная архитектура. Полный объём PDF: 31 с.
math_sources/math_research_07_of_08/preprints/Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins-September-24-2026/main.pdfSHA-256: be1d677ab515ceb23e7ee9fd369d705345ec0c9254585ac96ded3aa97732cd89Каталог: context/CONTENTS.md, строка 2829. Путь и хеш относятся к загруженной версии.
115-02 · An FPRAS for Cell-Bounded Contingency Tables
Реальный охват: Просмотрены PDF с. 1–3: Точная модель, история, отдельные последствия и конструкция больших ячеек. Полный объём PDF: 47 с.
math_sources/math_research_07_of_08/preprints/An-FPRAS-for-Cell-Bounded-Contingency-Tables-September-24-2026/main.pdfSHA-256: 10bad4277d11b9d1c69842fd8e9028c67edb9ebce6092ad6332703975c8fd7e7Каталог: context/CONTENTS.md, строка 2838. Путь и хеш относятся к загруженной версии.
Семейство в CONTENTS.md, строка 2822. Структурированные заметки · Журнал внешней сверки.