Публикация:McDiarmid 2002 Concentration for Independent Permutations

Материал из MachineLearning.

McDiarmid, C. Concentration for Independent Permutations // Comb. Probab. Comput.. — Cambridge University Press, 2002. — Vol. 11. — No. 2. — Pp. 163-178.

BibTeX:

 @article{mcdiarmid2002concentration,
   author = "McDiarmid, C.",
   title = "Concentration for Independent Permutations",
   journal = "Comb. Probab. Comput.",
   publisher = "Cambridge University Press",
   volume = "11",
   number = "2",
   pages = "163-178",
   url = "http://www.machinelearning.ru/wiki/images/3/32/Mcdiarmid2002concentration.pdf",
   year = "2002",
   language = english
 }

Содержание

1 Аннотация
2 Реферат
- 2.1 Основной результат
- 2.2 Доказательство неравенства
3 Литература

Аннотация

В статье представлено неравенство концентрации меры, затрагивающее семейство независимых случайных перестановок.

Реферат

Основной результат

Вкратце основной результат, представленный в статье, можно сформулировать следующим образом:

пусть $Z = h(Y),\; Y=(X, \pi)\in \Omega \times G,\; \textstyle{\Omega=\prod_i \Omega_i,\; G = \prod_j \mathrm{Sym}(B_j)},$

где $\mathrm{Sym}(B_j)$ - симетрическая группа конечного множества $B_j$ ; случайная величина $X$ и случайная перестановка $\pi$ независимы.

Пусть функция $h$ удовлетворяет следующим условиям:

Перестановка любых двух координат случайной величины $X$ , а также транспозиция любых двух элементов перестановки $\pi\in G$ меняют значение $h(X,\pi)$ не более, чем на $2c$ и $c$ соответственно (для некоторой $c\geq 0$ );
Если $h(X,\pi)=s$ , то можно указать не более $rs$ координат ( $r$ — положительная константа), таких что $h(X',\pi')\geq s$ для любых пар $(X',\pi')\in \Omega$ , значения которых совпадают с $(X,\pi)$ по этим координатам.

Тогда для любого неотрицательного $t$ выполнено:

$P(Z\geq m+t) \leq 2\exp\biggl(-\frac{t^2}{16rc^2(m+t)}\biggr);$

$P(Z\leq m-t) \leq 2\exp\biggl(-\frac{t^2}{16rc^2m}\biggr),$

где $m$ — медиана случайной величины $Z$ .

Доказательство неравенства

Доказательство сформулированного выше утверждения во всей красе использует индуктивный метод, разработанный Талаграном (Michel Talagrand) в ходе его исследования парадокса концентрации меры (concentration of measure). Оно опирается на (уже классической в теории статистического обучения) теореме Талаграна (торема 4.1.1, [1]), связывающей меру подмножества $A \subset \Omega^N$ с расстоянием от случайного элемента $x\in\Omega^N$ до этого подмножества: