Una conjetura sobre la entropía de los productos de matrices por vectores

Question

Considere una matriz circular parcial aleatoria $m$ por $n$ $M$ cuyas entradas se eligen de manera independiente y uniforme de $\{0,1\}$ y sea $m < n$. Ahora considere un vector aleatorio de $n$ dimensiones $v$ cuyas entradas también se eligen de manera independiente y uniforme de $\{0,1\}$. Sea $N = Mv$ donde la multiplicación se realiza sobre los reales.

Las matrices $M$ y $N$ son variables aleatorias discretas. Recordemos que la entropía de Shannon para una variable aleatoria discreta $Z$ es $H(Z) = -\sum_z P(Z=z)\log_2{P(Z=z)}$. En el caso en que $P(Z=z)=0$ para algunos valores $z$, el término correspondiente en la suma se toma como $0$.

Por lo tanto, sabemos que la entropía de Shannon (base $2$) $H(M) = H(v) = n$. El hecho de que $H(M) = n$ es un resultado directo del hecho de que toda la matriz está definida por su primera fila.

Si $m = \lfloor 10n/\ln{n} \rfloor$ entonces me gustaría hacer la siguiente conjetura.

Conjetura: Para todo $n$ suficientemente grande, $H(N) \geq n/10$.

El valor $10$ se elige de manera algo arbitraria para ser una constante suficientemente grande.

¿Es este un problema conocido y/o alguien puede ver una manera de abordarlo? ¿Es en realidad cierto?

Answer 1

Esto me recuerda un poco al juego de Mastermind.

---

Dado que tu matriz es circulante, toda esta matriz está determinada por la primera fila ${\bf m}$, el vector $X$ y el mapa de desplazamiento que toma $T:(m_1, \dots, m_n) \mapsto (m_2, \dots, m_n, m_1)$

Se te dan $m$ números (por favor, disculpa el choque de notaciones): $T^i({\bf m})\cdot {\bf X}$ para $i = 1, \dots, m$ por lo que hay como máximo $m \log n$ bits de información.

La cota $ \log n \cdot \tfrac{10n}{\log n} \geq H(N) \geq \tfrac{n}{10}$ es consistente con tu problema, al menos.

Answer 2

Esto no es una respuesta, solo un comentario largo.

Como señaló John Mangual, este juego es similar a Mastermind. De hecho, es aún más similar al juego definido por Erdos y Renyi aquí: http://www.renyi.hu/~p_erdos/1963-12.pdf. En su idioma, su juego es el siguiente: Nos dan la primera fila de la matriz $M$, denotada por $M'$, (así que $m=1$) pero con qué la multiplicamos, $X$, no es un vector, sino una matriz de $n\times a$. Nuestro objetivo es reconstruir $M$ a partir de $N=M'X. Ellos muestran que esto se puede hacer con alta probabilidad si $X$ es una matriz aleatoria y $a\ge 10n/\log n$. Por supuesto, si $M$ puede reconstruirse con alta probabilidad, eso también implica que $H(N)\ge (1-\epsilon)n.

Entonces, una posible forma de responder tu pregunta sería mostrar que su teorema se cumple incluso en el caso en que $X$ es una matriz circulante, ya que esto es equivalente a $X$ siendo un vector y $M$ siendo circulante.

nueva parte

Entonces supongamos que queremos calcular la probabilidad de que para dos vectores aleatorios diferentes, denotados por $v$ y $u$, multiplicándolos con las rotaciones de un vector aleatorio $r$ obtengamos los mismos valores, es decir, si las rotaciones de $r$ se denotan por $r_1,\ldots,r_k$, entonces cuál es la posibilidad de que para todos los $i$ tengamos $vr_i=ur_i. Para cualquier $i$, esto es como un paseo aleatorio, ya que $v$ y $u$ también son aleatorios, entonces $Pr[vr_i=ur_i]\approx 1/\sqrt n. Ahora afirmo que esta afirmación es verdadera incluso en la siguiente forma condicional si $k$ es lo suficientemente pequeño: $Pr[vr_i=ur_i\mid \forall j\ne i: vr_j=ur_j]\approx 1/\sqrt n.

No creo que sea tan difícil de probar, pero no puedo ver una solución ahora.

Answer 3

Un enfoque es la exploración informática: escribir un programa para trazar algunos puntos y graficar las funciones que deseas comparar en la misma gráfica.

Escribí un programa rápido en Sage para calcular y graficar la entropía H(Z(n,m)) para todos los 0 <= m <= n <= 10, y añadí las gráficas de (x=t, y=t, z=t) y (x=t, y=sqrt(t), z=t/10). Puedes agregar una gráfica para (x=t, y=t/ln(t), z=t/10), y/o modificar las otras para encontrar algo más cercano al gráfico.

Puedes encuéntralo e intentalo en el Servidor Sage Cell.

Para n > 10 trazar puntos a partir de cálculos exhaustivos se vuelve muy lento...

Es posible lograr mejoras significativas de velocidad con un mejor programa y/o utilizando Cython o un lenguaje de programación más rápido, pero en cualquier caso, la cantidad de casos crece tan rápido que un código más eficiente solo te llevará hasta cierto punto.

El siguiente truco es reemplazar la enumeración exhaustiva por muestreo aleatorio, lo cual podría darte una idea aproximada del gráfico en un rango mayor.

Por supuesto, además de esta exploración, una manera inteligente de estimar H(Z(n,m)), en general o a lo largo de una curva (n, m(n)), respondería mejor tu pregunta, pero en caso de que eso falle, las imágenes siempre son agradables.

En caso de que sea de interés, aquì tienes el código de Sage que escribí.

from collections import defaultdict

def h(d):
    sn = 0r
    sl = 0r
    for n in d.itervalues():
        if n:
            nn = RDF(n)
            sl += nn * nn.log2()
            sn += nn
    if sn:
        return sn.log2() - sl/sn
    return RDF.one()

def hh(n):
    xn = xrange(n)
    xnn = xrange(n+1)
    cp = CartesianProduct(*((0r,1r),)*n)
    dd = [defaultdict(int) for _ in xnn]
    for y in cp:
        for x in cp:
            z = tuple(sum(x[(i+k)%n]*y[i] for i in xn) for k in xn)
            for m in xnn:
                dd[m][z[:m]] += 1r
    return [h(d) for d in dd]

hhh = []
nmax = 10
for k in xrange(nmax):
    hhh.append(hh(k))

ph = []
for n,hh in enumerate(hhh):
    for m, h in enumerate(hh):
        ph.append((n,m,h))

fx = lambda x: x
fy = lambda x: sqrt(x)
fz = lambda x: x/10

gx = lambda x: x
gy = lambda x: x
gz = lambda x: x

Gf = parametric_plot3d((fx,fy,fz),(0,n),color='red')
Gg = parametric_plot3d((gx,gy,gz),(0,n),color='red')
Gh = point3d(ph,size=3)
G = Gf + Gg + Gh
G.show(viewer='tachyon')
G.show()