7
$\begingroup$

Let x be a random n-bit string, and let $I ={i_1,i_2,...,i_n}$ be the starting indexes of the longest 0-runs of x, sorted in decreasing order (so $i_1$ is the starting index of the longest (~$\log n$) 0-run, and ties are broken by lexicographic order). Note that the entropy of $I$ is at most $H(I) <= n$ bits (since $I$ is determined by $x$ and $H(x)=n$). What I'm trying to show is that "most" of this entropy is actually concentrated on a rather small number of indices with "large" entropy. More precisely, is it true that there is a subset $S \subseteq I$, $|S|=n/poly\log(n)$, s.t $H(S) > |S|*h$ , where $h >= \log^{\epsilon}n$ or even $h =\Omega(\log(\log(n)$)).

Note $H(i_1) = \log n$ by symmetry. The intuition is that $i_2,\ldots, ,i_{\Omega(\sqrt{\log n)}}$ are determined by $i_1$ since there's a gap of at least ~$\Omega(\sqrt{\log n)}$ between the first and second longest 0-runs. Then there's another discontinuous "random jump" to the next non-overlapping run, etc.

Would appreciate if anyone can point out relevant references.. Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

First I admit I am not an expert of information theory. However your problem do not seem to be too difficult. Take $S$ as the set of indices of the $0-run$ of lenght larger than $k$. We will chose $1\ll k\ll \log n$. In this regime we have $|S|=m\sim \frac{n}{2^k}$. We order the set $S=[1\leq s_1 < s_2 < s_3 <\cdots <s_m <n]$. In our regime $s_{i+1}-s_i$ behave like independent random variables of geometric law of parameter $2^{-k}$. Therefore $$H(S)\geq m H(\text{geometric}(2^{-k})) \approx m k $$ To conclude take $2^k\sim \log(n)^a$ such that $|S|\sim \frac{n}{\log(n)^a}$, we have $$H(S)\geq m\cdot\frac{a \log(\log(n))}{\log 2}$$

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for your reply, RaphaelB4! Unfortunately, s_{i+1} - s_i might not be independent of each other, for example, since the same run may appear multiple times with different cyclic shifts. However, this can happen <= \lg(n) times per run, hence I think you have the right intuition. But more importantly, the entropy of S is not invariant under permutations -- when you order the set S, the entropy can decrease (think about taking a random n-bit string and ordering it into runs of 0s followed by runs of 1s). So I don't think your H(S) is equal to my H(I). Does that make sense? Thanks! $\endgroup$
    – random guy
    Commented Jun 12, 2018 at 12:21
  • $\begingroup$ Hello random guy, I am not sure to understand your comment properly. For any run there is a unique index $s_i$. $\endgroup$
    – RaphaelB4
    Commented Jun 12, 2018 at 12:33
  • $\begingroup$ And yes the entropy decrease so I gave you a lower bound . $\endgroup$
    – RaphaelB4
    Commented Jun 12, 2018 at 12:44
  • $\begingroup$ I agree with your second point :) For the first point, maybe I wasn't clear enough -- I am sorting all $n$ cyclic shifts of x, so the same run can appear multiple times in your list S (with different shifts). For example, $s_1 - s_2 = 1$ with very high probability (since the 2nd longest run is very likely to be the 1-shift of the longest run). So, not all differences are geometrically distributed, right? But again, maybe it's possible to still use your argument -- is it trivial to see that for disjoint k-runs, consecutive distances are $~ Geom(2^{-k})$ ? thanks $\endgroup$
    – random guy
    Commented Jun 12, 2018 at 13:11
  • $\begingroup$ Ok, so once you have $s_i$ just erase all the $s_j$ with $s_j-s_i\leq k$. Starting from $s_i+k$ the rest of the string is independent. $\endgroup$
    – RaphaelB4
    Commented Jun 12, 2018 at 13:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .