События с высокой вероятностью без координат с низкой вероятностью

9

Пусть - случайная величина, принимающая значения в (для некоторого большого алфавита ), которая имеет очень высокую энтропию - скажем,для сколь угодно малой постоянной . Пусть - событие в опоре такое что , где \ varepsilon - сколь угодно малая константа.XΣnΣH(X)(nδ)log|Σ|δESupp(X)XPr[XE]1εε

Будем говорить , что пара (i,σ) является низкая вероятность координат в E , если Pr[XE|Xi=σ]ε . Мы говорим, что строка xΣn содержит координату с низкой вероятностью E если (i,xi) является координатой с низкой вероятностью E для некоторого i .

В общем, некоторые строки в E могут содержать низкие координаты вероятностных E . Вопрос в том, можем ли мы всегда найти событие с высокой вероятностью EE такое, что ни одна строка в E содержит координаты низкой вероятности E (а не E ).

Спасибо!

Или меир
источник

Ответы:

4

Вот пример, дополняющий ответ Гарри Юэна. Для контрпримера достаточно определить соответствующие и показать, что любое большое подмножество должно иметь координату с низкой вероятностью - координата с низкой вероятностью обязательно является координатой с низкой вероятностью -координат .X,EEEEEE

Кроме того, я проигнорирую условие об энтропии - добавление независимых равномерно распределенных случайных величин к (и перевод в ) увеличитпочти до не влияя на то, существует ли такое (я не тщательно продумал это).NXEE×ΣNH(X)/(n+N)log|Σ|1E

Вот пример. Пусть - случайный элемент из такой, что каждый вектор с весом Хэмминга (т. Е. Векторы вида ) имеет вероятность и вектор единиц имеет вероятность . Пусть - множество векторов с весом Хэмминга .X{0,1}n100100(1ϵ)/n11ϵE1

Рассмотрим подмножество . Если не пустой, он содержит вектор веса Хэмминга , скажем, без потери общности. Но , что меньше если равно около .EEE11000Pr[XE|Xi=1]=(1ϵ)/n(1ϵ)/n+ϵϵn2/ϵ2

Колин Маккуиллан
источник
6

Как по сравнению с ? Если может быть , то я думаю, что мы можем выполнить то, что вы хотите. Пусть . Обратите внимание , что дается вероятностной массы под . Пусть обозначает массу вероятности, присвоенную строкам в , что я координата имеет символ .ϵnϵO(1/n)B=Supp(X)EBϵXλ(i,σ)ϵBiσ

Пусть были низкая вероятность координат для некоторых строк в . Пусть обозначает массу вероятности, назначенную этим строкам. Тогда по определению , подразумевая, что . Мы можем отбросить эти строки с низкой вероятностью, потерпев только потерю в prob. масса на .(i,σ)Eδ(i,σ)δ(i,σ)δ(i,σ)+λ(i,σ)ϵϵδ(i,σ)2λ(i,σ)ϵ2δ(i,σ)E

Продолжайте делать это для всех возможных плохих , и в конце концов мы отбрасываем не более . При этом используется тот факт, что для всех , .(i,σ)i,σδ(i,σ)iσ2λ(i,σ)ϵ22iϵ2=2nϵ2iσλ(i,σ)=1

Если вы хотите, чтобы имел вероятностную массу , то должен быть таким, чтобы или достаточно.E1γϵϵ+2nϵ2γϵ=O(γ/2n)

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

Генри Юн
источник
О, я просто понял , что вы ищете более сильное требование - а именно, что не имеет низкие координаты вероятности относительно , а не . Я вернусь к этому позже сегодня. EEE
Генри Юн
Спасибо! Я ищу эпсилон, который является постоянным, но может быть сколь угодно малым.
Или Меир