Maximizar la curiosa función simétrica de combinatoria simple

Question

Una curiosa simétrica de la función se cruzó en mi camino en algunos de los cálculos de la mecánica cuántica, y estoy interesada en su valor máximo (para lo cual tengo una conjetura). (Esta pregunta ha sido publicado en MathOverflow en 13.12.2014; la cuestión se ha resuelto de una manera muy agradable allí.)

El problema

Hay $n$ diferentes objetos de $A_1,...,A_n$, y que hay conjuntos que contengan $m$ diferentes $A_i$s: $C_i=(A_{i_1}, A_{i_2}, ..., A_{i_m})$. Hay $i_{max}=\binom{n}{m}$ diferentes combinaciones de $C_i$. Cada combinación de $C_i$ tiene una probabilidad $p_i$ ($\sum_{i=1}^{i_{max}} p_i=1$).

La definición de la función

Para un determinado par de objetos $A_k$$A_l$:

• $f_1(k,l)$ contiene todas las probabilidades de $p_i$ de los conjuntos de $C_i$, que contiene objetos de $A_k$$A_l$.
• $f_2(k,l)$ contiene todas las probabilidades de $p_i$ de los conjuntos de $C_i$, que contiene el objeto $A_k$ o $A_l$ (si contiene ambos elementos, añadimos $p_i$ dos veces).
• $F(k,l)=\frac{f_1(k,l)}{f_2(k,l)}$

Con eso, conseguimos que la principal función de $$D^{(n,m)}=\sum_{k=1}^{n-1} \sum_{l=k+1}^{n} F(k,l)$$

¿Cuál es el máximo de $D^{(n,m)}$, dado que la suma de todas las probabilidades de $p_i$ es 1?

Casos especiales

n=2, m=2

Este es un caso trivial. Tenemos dos objetos $A_1$$A_2$, y sólo un conjunto de combinaciones de $C_1=(A_1,A_2)$$p_1$.

Así $f_1(1,2)=p_1$, $f_2(1,2)=p_1+p_1$. Esto conduce a $D^{(2,2)}=F(1,2)=\frac{1}{2}$.

Cualquier otro caso, se con $n=m$ puede ser resuelto fácilmente por $D^{(n,m)}=\frac{1}{n}$

---

n=3, m=2

Este caso es simple (pero no trivial) y he encontrado una solución:

Tenemos n=3 objetos $A_1$, $A_2$ y $A_3$, y combinaciones de $C_i$ m=2 objetos $C_1$=($A_1$, $A_2$), $C_2$=($A_1$, $A_3$), $C_3$=($A_2$, $A_3$), con $p_1$, $p_2$, $p_3$ respectivly.

Para k=1, l=2 tenemos $f_1(1,2)=p_1$ (debido a que sólo $C_1$ contiene $A_1$$A_2$), y $f_2(1,2)=2p_1+p_2+p_3$ (debido a $A_1$ está contenido en $C_1$$C_2$$A_2$$C_1$$C_3$).

Así, obtenemos $$D^{(3,2)}=F(1,2) + F(1,3) + F(2,3) = \frac{p_1}{2p_1+p_2+p_3} + \frac{p_2}{p_1+2p_2+p_3} + \frac{p_3}{p_1+p_2+2p_3}$$ Como máximo se pueden encontrar con facilidad (debido a la normalización de la $p_1+p_2+p_3=1$): $$D^{(3,2)} = \frac{p_1}{1+p_1} + \frac{p_2}{1+p_2} + \frac{p_3}{1+p_3}$$ so each term can be maximized individually, which gives $D^{(3,2)}=\frac{3}{4}$ for $p_1=p_2=p_3$.

---

n=4, m=2

Tenemos cuatro objetos $A_1$, $A_2$, $A_3$, $A_4$, y seis combinaciones $C_1=(A_1,A_2)$, $C_2=(A_1,A_3)$, ..., $C_6=(A_3, A_4)$.

Por lo tanto, tenemos: $$D^{(4,2)} = \frac{p_1}{2p_1+p_2+p_3+p_4+p_5} + \frac{p_2}{p_1+2p_2+p_3+p_4+p_6} + \frac{p_3}{p_1+p_2+3p_3+p_5+p_6} + \frac{p_4}{p_1+p_2+2p_4+p_5+p_6} + \frac{p_5}{p_1+p_3+p_4+2p_5+p_6} + \frac{p_6}{p_2+p_3+p_4+p_5+2p_6}$$

Yo no era capaz de encontrar un método para probar la existencia de un máximo global.

---

n=4, m=3

Tenemos $C_1=(A_1,A_2,A_3)$, $C_2=(A_1,A_2,A_4)$, $C_3=(A_1,A_3,A_4)$, $C_4=(A_2,A_3,A_4)$, lo que da

$$D^{(4,3)}=\frac{p_1+p_2}{2p_1+2p_2+p_3+p_4}+\frac{p_1+p_3}{2p_1+p_2+2p_3+p_4}+\frac{p_1+p_4}{2p_1+p_2+p_3+2p_4}+\frac{p_2+p_3}{p_1+2p_2+2p_3+p_4}+\frac{p_2+p_4}{p_1+2p_2+p_3+2p_4}+\frac{p_3+p_4}{p_1+p_2+2p_3+2p_4}$$

Este caso se puede simplificar así, similar a $n=3,m=2$ caso $$D^{(4,3)}=\frac{p_1+p_2}{1+p_1+p_2}+\frac{p_1+p_3}{1+p_1+p_3}+\frac{p_1+p_4}{1+p_1+p_4}+\frac{p_2+p_3}{1+p_2+p_3}+\frac{p_2+p_4}{1+p_2+p_4}+\frac{p_3+p_4}{1+p_3+p_4}$$

pero yo no soy capaz de encontrar cualquier método para calcular el máximo.

Conjetura

Los dos casos que he resuelto tuvo un máximo en igual $p_i=\frac{1}{\binom{n}{m}}$. Además, la función de $D^{(n,m)}$ es muy simétrico, por lo que espero que el máximo es siempre a $p_1=p_2=...=p_i$. Numérico de búsqueda hasta n=7 confirma mis expectativas (pero no estoy 100% seguro de mi Mathematica basado en la maximización numérica).

Preguntas

1. ¿Cómo se puede demostrar (o refutar) que el máximo de $D^{(n,m)}$ arbitrarias $n$ $m$ está siempre a $p_1=p_2=...=p_i$?
2. Hay literatura sobre problemas similares, o es esta función se conoce aún? Tiene similitud con la de Shapiro desigualdad de cierta importancia o es sólo una coincidencia?
3. Existe una mejor (tal vez geométricas) la interpretación de esta función?
4. Puede usted encontrar soluciones para cualquier otro caso especial de $n=m$ (siempre trivial) y $n=3,m=2$?

Answer 1

Partal solución:

---

El caso de $m=n-1$ puede ser resuelto fácilmente.

Es fácil comprobar que $$D^{(n,n-1)} = \sum_{1\le i < j \le n} \frac{p_1+\cdots + p_{i-1}+p_{i+1}+\cdots+p_{j-1}+p_{j+1}+\cdots +p_n}{2p_1+\cdots + 2p_{i-1}+p_i+2p_{i+1}+\cdots+2p_{j-1}+p_j+2p_{j+1}+\cdots +2p_n} \\ =\sum_{1\le i < j \le n} \frac{1-p_i-p_j}{2-p_i-p_j}$$

Ahora desde $f(x)=\frac{1-x}{2-x}$ es cóncava, podemos aplicar la desigualdad de Jensen para obtener $$\sum_{1\le i < j \le n} \frac{1-p_i-p_j}{2-p_i-p_j} \le \frac{1-2/n}{2-2/n} = \frac{n-2}{2n-2}$$ since the average of the $p_i+p_j$s is $\frac{2}{n}$. Equality holds if and only if $p_1=\cdots = p_n=1/n$.

---

El caso de $m=2,n=4$ también no es tan difícil de resolver.

Vamos a probar, primero, que el $\frac{a}{1+a-b} + \frac{b}{1+b-a} \le a+b$ si $a+b \le 1$. Esta desigualdad es verdadera, ya que es equivalente a $(1-a-b)(a-b)^2 \ge 0$ después de la expansión. Ahora $$D^{(4,2)} = \frac{p_1}{2p_1+p_2+p_3+p_4+p_5} + \frac{p_2}{p_1+2p_2+p_3+p_4+p_6} + \frac{p_3}{p_1+p_2+2p_3+p_5+p_6} + \frac{p_4}{p_1+p_2+2p_4+p_5+p_6} + \frac{p_5}{p_1+p_3+p_4+2p_5+p_6} + \frac{p_6}{p_2+p_3+p_4+p_5+2p_6} \\ = \sum_{i=1}^{3} \left(\frac{p_i}{1+p_i-p_{i+3}} + \frac{p_{i+3}}{1+p_{i+3}-p_i} \right) \le \sum_{i=1}^{3} p_i+p_{i+3} = 1$$ Equality obviously holds if $p_1=p_2=\cdots=p_6$, but there are other cases of equality such as $(p_1,\cdots,p_6)=(k,0,0,1-k,0,0)$ or $(a,b,c,a,b,c)$.

---

Sin embargo, creo que va a ser muy complicado para empujarlo más por estos tipos de métodos de fuerza bruta.

Answer 2

No es una respuesta - En caso de que esta ayuda:

Deje $T$ ser el indicador de $c \times n$ matriz, con $c = {n\choose m}$, e $T_{i,j} \in \{0,1\}$

A continuación, $$f_1(k,j)=\sum_{i=1}^c p_i T_{i,k} T_{i,j}

$$f_2(k,j)=\sum_{i=1}^c p_i (T_{i,k} + T_{i,j})$$

$$D = \sum_{k<j}\frac{\sum_{i=1}^c p_i T_{i,k} T_{i,j}}{\sum_{i=1}^c p_i (T_{i,k} + T_{i,j})}=\sum_{\ell}\frac{a_\ell}{b_\ell} \tag{1}$$ aquí $\ell$ los índices de todos los pares $(j<k)$.

Observe que $A=\sum_\ell a_\ell= \#\ell \, \langle T_{i,j} T_{i,k}\rangle$ donde $\#\ell=n(n-1)/2$ $$\langle T_{i,j} T_{i,k} \rangle=\frac{m (m-1)}{n (n-1)} es un promedio sobre todos los pares de $(j<k)$ y todas las filas (aviso que no depende de $p_i$).

Del mismo modo $B=\sum_\ell b_\ell= \#\ell \, \langle T_{i,j}+ T_{i,k}\rangle$, con $$\langle T_{i,j} + T_{i,k}\rangle=\frac{2 m }{n}$$

Además, cuando se $p_i=1/c$ obtenemos $$D_0 =\#\ell \frac{\langle T_{i,j} T_{i,k} \rangle}{\langle T_{i,j} +T_{i,k}\rangle}= \#\ell \frac{A}{B}= \frac{n(n-1)}{2} \frac{m-1}{2(n-1)} = \frac{n(m-1)}{4}$$

Así, para la conjetura para ser verdad, tendríamos que demostrar que $(1)$ es cóncava en a $p_i$ o

$$\sum_{\ell}\frac{a_\ell}{b_\ell}\le \#\ell \frac{A}{B}=\#\ell \frac{\sum_{\ell} a_\ell}{\sum_{\ell} b_\ell}$$

o

$$\langle \frac{a_\ell}{b_\ell} \rangle \le \frac{\langle a_\ell \rangle }{\langle b_\ell \rangle}$$

Actualización: La expresión $(1)$ no parece ser cóncava en $p$ - por lo que la conjetura de stands sin resolver.

Para el registro, he evaluado $D_e$ como el valor límite de la probabilidad concentrada en un único valor, y tengo

$$D_e=\frac{n}{(m-1)4}\frac{1-\frac{1}{n}+\frac{2}{n\,\left( n-m\right) }}{1+\frac{2}{m\,\left( n-m\right) }} < D_0$$

Aunque este extremo es menor que la conjetura máximo $D_0$, observe que la diferencia se desvanece como $n,m$ crecer.