Um problema combinatório simples (?) Engraçado!

Vamos fixar e um número inteiro . $0<E<1$ $t>0$

para qualquer e para qualquer vetor tal que $n$ $\bar{c} \in [0,1]^n$ $\sum_{i\in [n]} c_i \geq E \times n$

$A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \times t \}| \geq \binom{ E \times n}{ t }$

Não sei se o estatuto é verdadeiro ou falso. Eu acho que é verdade.

Minha intuição vem da observação de que, para os vetores $\bar{c} \in \{0,1\}^n$ (com a propriedade desejada sobre a soma), temos $A_{\bar{c}}= \binom{ E \times n}{t}$ ; neste caso, podemos selecionar apenas um subconjunto do conjunto $\{ i ~|~ c_i = 1 \}$ .

Nos outros casos, podemos criar um bom subconjunto (st a soma é maior que $E \times t$ ) usando a coordenada em $\{ i ~|~ c_i > E \}$ mas também, talvez, usando poucas coordenadas do conjunto $\{ i ~|~ c_i \leq E \}$ poderíamos criar outro bom conjunto!

Então, prove ou encontre o bug! esperando que possa ser um jogo divertido para você!

Motivação da pergunta :

Suponha que você tenha uma variável aleatória , uma medida típica de "quanta aleatoriedade" existe em é a min-entropia $X\in \{0,1\}^n$ $X$

$H_{\infty}(X) = min_{x} \{ -log(Pr[X = x]) \}$

Em algum sentido intuitivo, a min-entropia é o pior caso da famosa Shannon Entropy (esse é o caso médio ).

Estamos interessados em diminuir a entropia mínima da variável aleatória onde é uniformemente distribuído pelo conjunto . $(Z=X \wedge Y| Y)$ $Y$ $\{ y ~|~ \sum_i y_i = t\}$

Em termos gerais, se tivermos sorte, podemos capturar os bits de que têm "boa entropia" e, portanto, se seguida, $X$ $H_{\infty}(X)\geq En$ $H_{\infty}(Z|Y)\geq Et$

Qual é a probabilidade de termos sorte?

O problema é bem estudado e existe muita literatura, por exemplo, veja o Lema A.3. em criptografia de chave pública resiliente a vazamentos no modelo de recuperação limitada

co.combinatorics it.information-theory AntonioFa
fonte

Estou confuso com o termo . Como não é necessariamente um número inteiro, como é definido?

(\binom{E \times n}{t})

$E\times n \choose t$

E \times n

$E\times n$

Dave Clarke

Qual é a motivação?

Anthony Labarre

@ Dave Clarke, as abordagens padrão são defini-la em termos da função gama ou (dado que é inteiro) como.

t

$t$

\prod_{k = 0}^{t - 1} (E n - k) / t!

$\prod_{k=0}^{t-1}(En-k) / t!$

Peter Taylor

Os coeficientes binomiais podem ser generalizados para argumentos não integrais (a página da Wikipedia fornece alguns detalhes). Porém, pode não ser necessário neste caso: Observe que é suficiente provar isso no caso externo, onde a soma do é igual a (isto é, é a média).

c_{i}

$c_i$

E \times n

$E\times n$

E

$E$

Klaus Draeger

@ Dave: Sinto muito pela minha imprecisão, do meu ponto de vista, você pode escolher .

⌊ E n ⌋

$\lfloor En \rfloor$

AntonioFa

Respostas:

A conjectura no post não se sustenta, mas a conjectura mais fraca (com relação ao piso) mencionada nos comentários se mantém. De fato, algo mais forte vale.

Lema 1. A conjectura no post não se sustenta. Ou seja, existe uma instância que satisfaz as premissas fornecidas em que

| {S \subseteq [n] : \sum_{i \in S} c_{i} \geq E t} | < (\binom{E n}{t}) .

$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \, t \big\}\big| < \binom{ E \, n}{ t }.$

Prova. Considere o exemplo com , , e . Então . Para o lado esquerdo, temos porque qualquer subconjunto que não contém as duas quantidades de 1 para no máximo 1,7 e existem apenas dois subconjuntos ( e ) contendo os dois . E o lado direito é $n=3$ $c=(1, 1, 0.7)$ $E=2.7/3=0.9$ $t=2$ $E\, t = 1.8$

| {S \subseteq [3] : \sum_{i \in S} c_{i} \geq 1.8} | = 2

$\big|\textstyle\{ S \subseteq [3] : \sum_{i \in S}~ c_i \geq 1.8 \}\big| = 2$

S

$S$

{1, 1}

$\{1,1\}$

{1, 1, 0.7}

$\{1,1,0.7\}$

(\binom{2.7}{2}) = 2.7 \cdot 1.7 / 2 = 2.295 > 2. ◻

$\binom{ 2.7}{ 2 } = 2.7\cdot 1.7\,/\, 2 = 2.295>2. ~~~\Box$

A conjectura mais fraca sugerida nos comentários, a saber, o limite do piso, o piso o piso, se mantém. De fato, algo um pouco mais forte vale: $\lfloor E\, n \rfloor$

Lema 2. Corrija , números inteiros e o vetor com . Então $0<E<1$ $n,t>0$ $c \in [0,1]^n$ $\sum_{i\in [n]} c_i \geq E\, n$

| {S \subseteq [n] : \sum_{i \in S} c_{i} \geq E t} | > (\binom{⌊ E n ⌋}{t}) + (\binom{⌊ E n ⌋}{t + 1}) + \dots + (\binom{⌊ E n ⌋}{⌊ E n ⌋}) .

$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E\, t \big\}\big| \,>\, \binom{ \lfloor E\, n\rfloor}{ t } + \binom{ \lfloor E\, n\rfloor}{ t+1 } + \cdots + \binom{ \lfloor E\, n\rfloor}{ \lfloor E\, n\rfloor }.$

Prova. Deixe . Suponha ao WLOG que . (Caso contrário, dimensione e cada para baixo por um fator uniforme para fazê-lo. Isso mantém não altera quais subconjuntos somam pelo menos nem o limite inferior desejado do número de suponha WLOG que (caso contrário, a reivindicação é trivial). $a=\lfloor E\, n\rfloor$ $a=E\,n$ $E$ $c_i$ $\sum_i c_i \ge E\,n$ $E\,t$ $t\le a$

Considere qualquer subconjunto de tamanho pelo menos , em que . Como e contém todos, exceto no máximo elementos (cada um dos quais é no máximo 1), temos , conforme desejado. $S\subseteq [n]$ $n-d$ $d=a-\lceil a\,t/n\rceil \ge 0$ $\sum_{i\in[n]} c_i \ge a$ $S$ $d$ $\sum_{i\in S} c_i \ge a-d = \lceil a\,t/n\rceil = \lceil E\,t\rceil \ge E\,t$

O número desses subconjuntos é $S$

${n\choose n-d} + {n \choose n-d+1} + \cdots + {n \choose n-1} + {n \choose n}$

$= {n\choose d} + {n \choose d-1} + \cdots + {n \choose 1} + {n \choose 0}$

$> {a\choose d} + {a \choose d-1} + \cdots + {a \choose 1} + {a \choose 0}~~~$ (usando ) $n>a$

$= {a\choose a-d} + {a \choose a-d+1} + \cdots + {a \choose a-1} + {a \choose a}.$

Como (usando ), a última soma é pelo menos o limite inferior desejado no número de bons subconjuntos. $a-d = \lceil a\,t/n\rceil \le t$ $a/n = E < 1$ $~~\Box$

Neal Young
fonte