Простая (?) Смешная комбинаторная задача!

11

Пусть мы зафиксируем 0<E<1 и целое число t>0 .

для любого n и для любого вектора c¯[0,1]n такого, что i[n]ciE×n

Ac¯:=|{S[n]:iS ciE×t}|(E×nt)

Я не знаю, верно ли это утверждение или ложь. Я думаю, что это правда.

Моя интуиция исходит из наблюдения, что для векторов (с желаемым свойством относительно суммы) мы имеем ; в этом случае мы можем выбрать только подмножество из набора .c¯{0,1}nAc¯=(E×nt){i | ci=1}

В другом случае мы можем создать хорошее подмножество (st сумма больше, чем ), используя координаты в но также, возможно, используя несколько координат из набора мы могли бы создать другой хороший набор!E×t{i | ci>E}{i | ciE}

Итак, докажите это или найдите ошибку! надеясь, что это может быть забавная игра для вас!

Мотивация вопроса :

Предположим, у вас есть случайная величина , типичная мера «сколько случайности» в - это минимальная энтропияX{0,1}nX

H(X)=minx{log(Pr[X=x])}

В некотором интуитивном смысле мин-энтропия является худшим случаем знаменитой энтропии Шеннона (это средний случай ).

Нам интересно ограничить минимальную энтропию случайной величины где равномерно распределено по множеству .(Z=XY|Y)Y{y | iyi=t}

Грубо говоря, если нам повезет, мы можем поймать биты которые имеют «хорошую энтропию», и поэтому мы, если то XH(X)EnH(Z|Y)Et

Какова вероятность того, что нам повезло?

Проблема хорошо изучена, и существует много литературы, например, см. Лемму А.3. в устойчивой к утечкам криптографии с открытым ключом в модели с ограниченным поиском

AntonioFa
источник
3
Я смущен термином . Поскольку не обязательно является целым числом, как оно определяется? (E×nt)E×n
Дэйв Кларк
2
Какова мотивация?
Энтони Лабарр
6
@ Дэйв Кларк, стандартные подходы - определить его в терминах гамма-функции или (учитывая, что является целым числом) как, tk=0t1(Enk)/t!
Питер Тейлор
2
Биномиальные коэффициенты могут быть обобщены до нецелых аргументов (страница Википедии содержит довольно много деталей). Однако в этом случае это может быть необязательным: обратите внимание, что этого достаточно, чтобы доказать это в экстремальном случае, когда сумма равна (т.е. - их среднее значение). ciE×nE
Клаус Дрегер
1
@Dave: извините за мою неточность, с моей точки зрения вы можете выбрать . En
AntonioFa

Ответы:

2

Гипотеза в посте не верна, но более слабая гипотеза (по отношению к полу), упомянутая в комментариях, остается верной. На самом деле что-то сильнее держит.


Лемма 1. Гипотеза в посте не имеет места. То есть есть экземпляр, удовлетворяющий данным предположениям, где

|{S[n]:iS ciEt}|<(Ent).

Доказательство. Рассмотрим случай с , , и . Тогда . Для левой части мы имеем потому что любое подмножество которое не содержит обеих сумм 1, не превышает 1.7, и есть только два подмножества ( и ), содержащие оба 1. И правая часть - этоn=3c=(1,1,0.7)E=2.7/3=0.9t=2Et=1.8

|{S[3]:iS ci1.8}|=2
S{1,1}{1,1,0.7}(2.72)=2.71.7/2=2.295>2.   

Более слабая гипотеза, предложенная в комментариях, а именно граница с полом, , имеет место. На самом деле что-то чуть сильнее держит:En

Лемма 2. Зафиксируем , целые числа и вектор с помощью . Тогда 0<E<1n,t>0c[0,1]ni[n]ciEn

|{S[n]:iS ciEt}|>(Ent)+(Ent+1)++(EnEn).

Доказательство. Пусть . Предположим, что WLOG . (В противном случае масштабируйте и каждый вниз на единообразный коэффициент, чтобы сделать это так. Это поддерживает и не изменяет ни сумму подмножеств как минимум ни желаемую нижнюю границу числа таких подмножеств.) Предположим, что WLOG (в противном случае утверждение выполняется тривиально).a=Ena=EnEciiciEnEtta

Рассмотрим любое подмножество размером не менее , где . Поскольку и содержит все, кроме не более элементов (каждый из которых не более 1), мы имеем , по желанию.S[n]ndd=aat/n0i[n]ciaSdiSciad=at/n=EtEt

Количество таких подмножеств равноS

(nnd)+(nnd+1)++(nn1)+(nn)

=(nd)+(nd1)++(n1)+(n0)

>(ad)+(ad1)++(a1)+(a0)    (используя )n>a

=(aad)+(aad+1)++(aa1)+(aa).

Но (используя ), поэтому последняя сумма является как минимум желаемой нижней границей для числа хороших подмножеств. ad=at/nta/n=E<1  

Нил Янг
источник