RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды МИАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Тр. МИАН, 2011, том 274, страницы 41–102 (Mi tm3322)  

Эта публикация цитируется в 14 научных статьях (всего в 14 статьях)

Алгоритмические тесты и случайность относительно классов мер

Л. Биенвенюa, П. Гачb, М. Хойрупc, К. Рохасd, А. Шеньef

a Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA), CNRS UMR 7089 & Université Paris Diderot, Paris Cedex, France
b Department of Computer Science, Boston University, Boston, MA, USA
c Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Vandœuvre-lés-Nancy, France
d Department of Mathematics, University of Toronto, Toronto, Ontario, Canada
e Laboratoire d'Informatique Fondamentale de Marseille (LIF), Université Aix–Marseille, CNRS UMR 6166, Marseille Cedex, France
f Институт проблем передачи информации им. А. А. Харкевича РАН, Москва, Россия

Аннотация: Приводятся некоторые новые результаты об алгоритмической случайности по отношению к классам мер, а также подробно излагаются известные (но не опубликованные подробно) результаты об алгоритмических тестах случайности. Мы начинаем с переформулировки определения случайности по Мартин-Лёфу в терминах тестов случайности (функций, измеряющих степень “неслучайности” последовательностей). Приводится формула, выражающая значение универсального теста в терминах префиксной сложности. Рассматриваются также варианты определения дефекта случайности для конечных слов, связанные с универсальным тестом. Далее рассматривается (введенное еще Мартин-Лёфом) понятие бернуллиевой последовательности (как последовательности, не противоречащей гипотезе о том, что все испытания независимы и имеют одинаковую вероятность успеха). Показано, что определение с помощью универсального теста эквивалентно первоначальному определению Мартин-Лёфа и что последовательность является бернуллиевой тогда и только тогда, когда она случайна по Мартин-Лёфу относительно бернуллиевой меры $B_p$ при некотором $p$ (с оракулом для $p$). Затем этот же вопрос (о сравнении тестов относительно классов мер и тестов как функции двух аргументов – последовательности и меры) применяется к произвольным эффективно замкнутым классам мер в канторовском пространстве. Для бернуллиевых мер $B_p$ значение $p$ можно восстановить, глядя на произвольную случайную относительно $B_p$ последовательность (свойство ортогональности). Изучаются свойства ортогональных классов мер, и указываются предположения, в которых два понятия случайности (равномерная и безоракульная) совпадают. В заключение рассматриваются обобщения некоторых из указанных результатов на случай произвольных метрических пространств.

Полный текст: PDF файл (561 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics, 2011, 274, 34–89

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.5
Поступило в марте 2011 г.

Образец цитирования: Л. Биенвеню, П. Гач, М. Хойруп, К. Рохас, А. Шень, “Алгоритмические тесты и случайность относительно классов мер”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 41–102; Proc. Steklov Inst. Math., 274 (2011), 34–89

Цитирование в формате AMSBIB
\RBibitem{BieGacHoy11}
\by Л.~Биенвеню, П.~Гач, М.~Хойруп, К.~Рохас, А.~Шень
\paper Алгоритмические тесты и случайность относительно классов мер
\inbook Алгоритмические вопросы алгебры и логики
\bookinfo Сборник статей. К~80-летию со дня рождения академика Сергея Ивановича Адяна
\serial Тр. МИАН
\yr 2011
\vol 274
\pages 41--102
\publ МАИК «Наука/Интерпериодика»
\publaddr М.
\mathnet{http://mi.mathnet.ru/tm3322}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2962935}
\elib{http://elibrary.ru/item.asp?id=16766472}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2011
\vol 274
\pages 34--89
\crossref{https://doi.org/10.1134/S0081543811060058}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000295983200004}
\elib{http://elibrary.ru/item.asp?id=23965230}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84912053480}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tm3322
  • http://mi.mathnet.ru/rus/tm/v274/p41

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Bienvenu L., Monin B., “Von Neumann's Biased Coin Revisited”, 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science (Lics), IEEE Symposium on Logic in Computer Science, IEEE, 2012, 145–154  crossref  mathscinet  zmath  isi
    2. Bienvenu L., Romashchenko A., Shen A., Taveneaux A., Vermeeren S., “The Axiomatic Power of Kolmogorov Complexity”, Ann. Pure Appl. Log., 165:9, SI (2014), 1380–1402  crossref  mathscinet  zmath  isi  elib
    3. Weihrauch K., Tavana N.R., “Representations of Measurable Sets in Computable Measure Theory”, Log. Meth. Comput. Sci., 10:3 (2014), 7  crossref  mathscinet  zmath  isi  elib
    4. Bauwens B., “Prefix and Plain Kolmogorov Complexity Characterizations of 2-Randomness: Simple Proofs”, Arch. Math. Log., 54:5-6 (2015), 615–629  crossref  mathscinet  zmath  isi  elib
    5. Rute J., “Computable randomness and betting for computable probability spaces”, Math. Log. Q., 62:4-5 (2016), 335–366  crossref  mathscinet  zmath  isi  elib  scopus
    6. Rute J., When does randomness come from randomness?, Theor. Comput. Sci., 635 (2016), 35–50  crossref  mathscinet  zmath  isi  elib  scopus
    7. Andreev M., Kumok A., “The Sum $2^{ KM(x)-K(x)}$ Over All Prefixes $x$ of Some Binary Sequence Can be Infinite”, Theor. Comput. Syst., 58:3, SI (2016), 424–440  crossref  mathscinet  zmath  isi  elib  scopus
    8. Bauwens B., “Relating and Contrasting Plain and Prefix Kolmogorov Complexity”, Theor. Comput. Syst., 58:3, SI (2016), 482–501  crossref  mathscinet  zmath  isi  elib  scopus
    9. Bauwens B., Shen A., Takahashi H., “Conditional Probabilities and Van Lambalgen'S Theorem Revisited”, Theor. Comput. Syst., 61:4, SI (2017), 1315–1336  crossref  mathscinet  zmath  isi
    10. Bienvenu L., Hoyrup M., Shen A., “Layerwise Computability and Image Randomness”, Theor. Comput. Syst., 61:4, SI (2017), 1353–1375  crossref  mathscinet  zmath  isi
    11. Vereshchagin N., Shen A., “Algorithmic Statistics: Forty Years Later”, Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60Th Birthday, Lecture Notes in Computer Science, 10010, eds. Day A., Fellows M., Greenberg N., Khoussainov B., Melnikov A., Rosamond F., Springer International Publishing Ag, 2017, 669–737  crossref  mathscinet  zmath  isi
    12. Novikov G., “Randomness Deficiencies”, Unveiling Dynamics and Complexity, Cie 2017, Lecture Notes in Computer Science, 10307, eds. Kari J., Manea F., Petre I., Springer International Publishing Ag, 2017, 338–350  crossref  mathscinet  zmath  isi  scopus
    13. Rute J., “Schnorr Randomness For Noncomputable Measures”, Inf. Comput., 258 (2018), 50–78  crossref  mathscinet  zmath  isi
    14. Bienvenu L., Figueira S., Monin B., Shen A., “Algorithmic Identification of Probabilities Is Hard”, J. Comput. Syst. Sci., 95 (2018), 98–108  crossref  mathscinet  zmath  isi
  • Труды Математического института им. В. А. Стеклова Proceedings of the Steklov Institute of Mathematics
    Просмотров:
    Эта страница:519
    Полный текст:26
    Литература:62
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019