9
$\begingroup$

Consider a random $m$ by $n$ partial circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$ and let $m < n$. Now consider a random $n$ dimensional vector $v$ whose entries are also chosen independently and uniformly from $\{0,1\}$. Let $N = Mv$ where multiplication is performed over the reals.

The matrices $M$ and $N$ are discrete random variables. Recall that the Shannon entropy for a discrete random variable $Z$ is $H(Z) = -\sum_z P(Z=z)\log_2{P(Z=z)}$. In the case where $P(Z=z)=0$ for some values $z$, the corresponding term in the sum is taken to be $0$.

We therefore know that the (base $2$) Shannon entropy $H(M) = H(v) = n$. The fact that $H(M) = n$ is a direct result of the fact that the entire matrix is defined by its first row.

If $m = \lfloor 10n/\ln{n} \rfloor$ then I would like to make the following conjecture.

Conjecture: For all sufficiently large $n$, $H(N) \geq n/10$.

The value $10$ is chosen somewhat arbitrarily to be a sufficiently large constant.

Is this a known problem and/or can anyone see a way to approach it? Is it in fact true?

$\endgroup$
  • $\begingroup$ Do you insist that $M$ has the first $m$ rows of the circulant matrix, or are you fine with $M$ having random $m$ rows of the full matrix? $\endgroup$ – Mert Sağlam Apr 19 '16 at 19:48
  • $\begingroup$ @MertSaglam It should be the first $m$ rows of a full matrix. $\endgroup$ – Anush Apr 20 '16 at 7:58
  • $\begingroup$ Just in case this question is coming from another source, I realized talking with a colleague today that this precise question also appears in streaming algorithms literature. If so, I can point to the paper conjecturing this when it becomes available. $\endgroup$ – Mert Sağlam Apr 22 '16 at 22:21
2
$\begingroup$

This is not an answer, just a long comment.

As pointed out by John Mangual, this game is similar to Mastermind. In fact, it is even more similar to the game defined by Erdos and Renyi here: http://www.renyi.hu/~p_erdos/1963-12.pdf. In your language their game is the following: We are given the first row of the matrix $M$, denoted by $M'$, (so $m=1$) but what we multiply it with, $X$, is not a vector, but an $n\times a$ matrix. Our goal is to reconstruct $M$ from $N=M'X$. They show that this can be done whp if $X$ is a random matrix and $a\ge 10n/\log n$. Of course if $M$ can be reconstructed whp, that also implies that $H(N)\ge (1-\epsilon)n$.

So one possible way to answer your question would be to show that their theorem holds even in the case when $X$ is a circulant matrix, as this is equivalent to $X$ being a vector and $M$ being circulant.

new part

So suppose we want to compute the probability that for two different random vectors, denoted by $v$ and $u$, multiplying them with the rotations of a random vector $r$ we get the same values, i.e., if the rotations of $r$ are denote by $r_1,\ldots,r_k$, then what is the chance that for all $i$ we have $vr_i=ur_i$. For any $i$, this is like a random walk, as $v$ and $u$ are also random, so $Pr[vr_i=ur_i]\approx 1/\sqrt n$. Now I claim that this statement is true even in the following conditional form if $k$ is small enough: $Pr[vr_i=ur_i\mid \forall j\ne i: vr_j=ur_j]\approx 1/\sqrt n.$

I don't think this is that hard to prove, but I cannot see a solution now.

$\endgroup$
  • $\begingroup$ A very nice observation but do you have any ideas for how to try to show their theorem holds when $X$ is circulant? This seems highly un-obvious, at least to me. $\endgroup$ – felix Jul 30 '14 at 16:12
  • $\begingroup$ @felix: No, at least until now. $\endgroup$ – domotorp Jul 30 '14 at 17:42
  • 1
    $\begingroup$ Your "new part" looks like the core of the problem but I have to admit, looks no easier to me. It will be great if you (or anyone) has any ideas about this new formulation. $\endgroup$ – Anush Aug 3 '14 at 20:29
  • $\begingroup$ Do you think it would be acceptable to pose your formulation as a new question? I have no ideas for how to approach it. $\endgroup$ – Anush Aug 26 '14 at 14:53
  • 2
    $\begingroup$ @domotorp Looks like it wasn't so simple after all! $\endgroup$ – felix Sep 17 '14 at 20:47
0
$\begingroup$

This reminds me a bit of the game of mastermind.


Since your matrix is circulant, this entire matrix is determined by the first row ${\bf m}$, the vector $X$ and the shift map taking $T:(m_1, \dots, m_n) \mapsto (m_2, \dots, m_n, m_1)$

You are given $m$ numbers (please excuse the notation clash): $T^i({\bf m})\cdot {\bf X}$ for $i = 1, \dots, m$ so there are at most $m \log n$ bits of information.

The bound $ \log n \cdot \tfrac{10n}{\log n} \geq H(N) \geq \tfrac{n}{10}$ is consistent with your problem, at least.

$\endgroup$
  • $\begingroup$ There is a trivial upper bound of $H(N) \leq 2n$. $\endgroup$ – felix Jul 28 '14 at 17:47
0
$\begingroup$

One approach is computer exploration: write a program to plot a few points, and plot of the functions you want to compare to on the same graphics.

I wrote a quick Sage program to compute and plot the entropy H(Z(n,m)) for all 0 <= m <= n <= 10, and I added the plots of (x=t, y=t, z=t) and (x=t, y=sqrt(t), z=t/10). You can add a plot for (x=t, y=t/ln(t), z=t/10), and/or modify the others to find something closer to the graph.

You can find it and try it on the Sage Cell Server.

For n > 10 plotting points from exhaustive computations becomes very slow...

Massive speedups are certainly possible with a better program and/or using Cython or a faster programming language, but in any case the number of cases grows so fast that more efficient code will only get you so far.

The next trick is to replace exhaustive enumeration by random sampling, which might give you a rough idea of the graph in a larger range.

Of course, besides this exploration, a clever way to estimate H(Z(n,m)), in general or along a curve (n, m(n)), would better answer your question, but failing that, pictures are always nice.

In case it's any interest, Here is the Sage code I wrote.

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()
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.