Что является доказательством этой нестандартной версии неравенства Азумы?

12

В Приложении B « Повышение и дифференциальная конфиденциальность » Дворка и др. Авторы приводят следующий результат без доказательств и называют его неравенством Азумы:

Пусть - действительные случайные величины, такие что для каждого ,C1,,Cki[k]

  1. Pr[|Ci|α]=1 и
  2. для каждого (c1,,ci1)Supp(C1,,Ci1) мы имеем E[CiC1=c1,,Ci1=ci1]β .

Тогда для каждого z>0 имеем Pr[i=1kCi>kβ+zkα]ez2/2 ,

У меня проблемы с доказательством. Стандартная версия неравенства Азумы говорит:

Предположим, что {X0,X1,,Xk} является мартингалом, а |XiXi1|γi почти наверняка. Тогда для всех t>0 имеем Pr[Xkt]exp(t2/(2i=1kγi2)) .

Чтобы доказать версию неравенства Азумы, изложенную Дворком и др., Я решил, что нам нужно взять X0=0 и Xi=Xi1+CiE[CiC1,C2,,Ci1] . Таким образом, я думаю, что {X0,,Xk} - мартингейл. Но все, что мы можем сказать, это то, что |XiXi1|2α почти наверняка, верно? Этот фактор в два раза вызывает проблемы, потому что это означает, что после замены мы просто обнаруживаем, что Pr[i=1kCi>kβ+zk2α]ez2/2 , что слабее, чем заключение, сформулированное Dwork et al.

Есть ли простой трюк, который я пропускаю? Является ли заявление Dwork et al. не хватает в два раза?

Уильям Хоза
источник
Утверждение в статье верно, но не следует из «обычной» версии неравенства Азумы. Проблема в том, что обычное утверждение предполагает но подойдет любой интервал той же длины; нет оснований предполагать симметричный интервал. XiXi1[a,a]
Томас поддерживает Монику

Ответы:

13

Я не могу найти ссылку, поэтому я просто набросал доказательство здесь.

Теорема. Пусть - реальные случайные величины. Пусть являются константами. Предположим, что для всех и всех в поддержке , у нас естьX1,,Xna1,,an,b1,,bni{1,,n}(x1,,xi1)(X1,,Xi1)

  1. E[Xi|X1=x1,,Xi1=xi1]0 и
  2. P[Xi[ai,bi]]=1 .

Тогда для всех ,t0

P[i=1nXit]exp(2t2i=1n(biai)2).

Доказательство. Определить . Мы утверждаем, что Для всех и у нас есть По предположению, и для всех в поддержкуYi=j=1iXj

(*)i{1,,n} λ0     E[eλYi]e18λ2j=1i(bjaj)2.
iλ
E[eλYi]=E[eλYi1eλXi]=E[eλYi1E[eλXi|Yi1]].
μ(yi1):=E[Xi|Yi1=yi1]0P[Xi[ai,bi]]=1yi1Yi1, (Обратите внимание, что .) Таким образом, по лемме Хеффдинга , для всех в поддержку и всех . Так , мы имеем, для всех , Теперь индукция дает иск (*) выше.Yi1=X1++Xi1
E[eλXi|Yi1=yi1]eλμ(yi1)+18λ2(biai)2
yi1Yi1λRμ(yi1)0λ0
E[eλYi]E[eλYi1e0+18λ2(biai)2].

Теперь мы применяем неравенство Маркова к и используем наше утверждение (*). Для всех , Наконец, установите чтобы минимизировать выражение правой руки и получить результат. eλYnt,λ>0

P[i=1nXit]=P[Ynt]=P[eλYneλt]E[eλYn]eλte18λ2i=1n(biai)2eλt.
λ=4ti=1n(biai)2

Как я упоминал в своем комментарии, ключевое отличие между этим и «обычным» утверждением о неравенстве заключается в том , что вместо требуется . Первый обеспечивает большую гибкость, и в некоторых случаях это экономит коэффициент 2.Xi[ai,bi]Xi[a,a]

Обратите внимание, что случайные величины в доказательстве являются супермартингалом. Вы можете получить обычную версию неравенства взяв мартингейл , установив и (где ) с последующим применением вышеуказанного результата.YiY1,,YnXi=YiYi1[ai,bi]=[ci,ci]P[|YiYi1|ci]=1

Томас поддерживает Монику
источник
В первой строке доказательства это, по-видимому, должно быть (верхняя граница суммы как а не ) ....Yi=j=1iXjin
Дугал
1
Доказательство также дано в монографии Дубхаши и Панконези.
Кристоффер Арнсфельт Хансен
@KristofferArnsfeltHansen: Отлично. У вас есть ссылка?
Томас поддерживает Монику