Изменения

===Блуждания по экспандеру===

Согласно границе Чернова<ref>[https://en.wikipedia.org/wiki/Chernoff_bound]</ref>, если выбирать много независимых случайных значений из интервала <tex>[-1, 1]</tex>, с большой степенью вероятности среднее выбранных значений будет близко к [[Математическое ожидание случайной величины|математическому ожиданию]] случайной переменной. Лемма о блуждании по экспандеру, согласно статьям Аджтари, Комлоша и Семереди<ref>[M. Ajtai,J. Komlós,E. Szemerédi Proceedings of the 19th Annual ACM Symposium on Theory of Computing // ACM. — 1987. — С. 132–140. — ISBN 0-89791-221-7. — DOI:10.1145/28395.28410]</ref> и Гилмана<ref>[D. Gillman A Chernoff Bound for Random Walks on Expander Graphs // SIAM Journal on Computing. — Society for Industrial and Applied Mathematics, 1998. — Т. 27, вып. 4,. — С. 1203–1220. — DOI:10.1137/S0097539794268765]</ref>, утверждает, что то же самое верно и для блужданий по экспандеру. Это полезно в теории дерандомизации<ref>[https://en.wikipedia.org/wiki/Randomized_algorithm]</ref>, поскольку блуждание по экспандеру использует много меньше случайных бит, чем случайная независимая выборка.

==Примечания==