4
$\begingroup$

I call a language $L$ a random-seeming language of length $n$ and weight $k$ if $L\subset\{0,1\}^n$, $s\in L \rightarrow (s \text{ has } k \;1\text{'s})$, and $$\forall _{I\subset[n]}\forall_{m\le \min\left(k,|I|\right)} \left(S=\{s \in L: \sum_{i\in I}b_i(s)=m\}\rightarrow\forall_{i\in I}\left[|\{s\in S:b_i(s)=1\}|=\frac {m|S|} {|I|}\right]\right)$$where $b_i(s)$ is the $i^\text{th}$ bit of $s$.

Obviously the language $L_\max=\left\{s\in\{0,1\}^n:\sum_{i\in \left[n\right]}b_i(s)=k\right\}$ is random-seeming, but are there any random-seeming languages of length $n$ and weight $k$ smaller than $L_\max$? More generally, given an integer $l \le |L_\max|$, what is the smallest $\epsilon\ge 0$ such that $$\exists _{L\subset L_\max}\forall _{I\subset[n]}\forall_{m\le \min\left(k,|I|\right)} \left(\left|L\right|\le l \wedge S=\{s \in L: \sum_{i\in I}b_i(s)=m\}\rightarrow\forall_{i\in I}\left[\left|\left|\left\{s\in S:b_i(s)=1\right\}\right|-\frac {m|S|} {|I|}\right|\le\epsilon\right]\right)$$

Note: I included the probability tag because this is essentially a probability question in my mind: a language $L$ is "random-seeming" iff for every set of set of digits $I$ and integer $m\le k$, the probability that a random string $s\in \{0,1\}^n$ with $m$ $1$'s in $I$ will be in $L$ is independent of the distribution of the $1$'s in $I$, and in the general problem, $\epsilon$ represents the maximum deviation such a probability can have from the mean probability for any given distribution of $1$'s in any given $I$. At least, that is what I intended it to mean. It's possible that I messed up the formal statement above (though I'm pretty sure I got it right), but the point of being random-seeming, is that the number of $1$'s among some of the digits tells you nothing (or in the general case, little) about the distribution of $1$'s in the rest of the digits, only their total number.

$\endgroup$
  • $\begingroup$ Don't forget about the empty set. More importantly, note that the group $S_n$ of permutations of $[n]$ acts transitively on $\{0,1\}^n$. Perhaps, random-seemingness already implies $S_n$-invariance? In this case, the only two random-seeming languages would be the maximal and the empty one. $\endgroup$ – Ben Nov 18 '16 at 3:46
  • $\begingroup$ Right, of course the empty set would be random-seeming. I'm looking for non-trivial examples though. I'm a curious as to how $S_n$ acts transitively on $\{0,1\}^n$, though, as the natural group action which occurs to me (rearranging the bits) isn't transitive. Do you mean that $S_n$ acts transitively on $\{s \in \{0,1\}^n : s \text{ has } k \;1 \text{'s}\}$, or is there some less obvious action of $S_n$ which is transitive on all of $\{0,1\}^n$? In any case, I suspect that the answer to the strict question is no, which is why I asked the general question about approximating random-seeming. $\endgroup$ – Gabriel Burns Nov 28 '16 at 16:36
  • $\begingroup$ Dear @GabrielBurns, you're right, the action of the symmetric group isn't transitive on $\{0,1\}^n$ but the maximal language of weight $k$, sorry. Anyways, that idea doesn't seem to be useful at all. I also expect that the empty and maximal language are the only random-seeming ones, and I'd bet that there is a collection of your conditions which allows an induction and thus to reduce to a trivial case. The question about approximations seems pretty hard to me. Have you computed it for small $n$? $\endgroup$ – Ben Nov 28 '16 at 19:00
  • $\begingroup$ @Ben, not yet. I'll try that when I have time, and see if I find any sort of pattern. $\endgroup$ – Gabriel Burns Nov 28 '16 at 21:01

Your Answer

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

Browse other questions tagged or ask your own question.