1
$\begingroup$

Given two strings $x$, $y$, both of length $n$, what is the probability that $K(x|y,n)=K(x|n)$ ? (Bounds on this probability would be very interesting too). Here $K$ is Kolmogorov complexity, $x$ and $y$ are sampled from uniform probability distribution over strings of length $n$, i.e. $P(x)=\frac{1}{2^n}$ for all $x$. Informally, what is the probability that two random strings carry no information about one another?

$\endgroup$
  • $\begingroup$ What description language does your K use? ​ ​ $\endgroup$ – user12859 May 8 '17 at 20:10
  • $\begingroup$ Ricky, I don't think this matters. I suspect the probability is zero in the limit of large n (this is not clear to me however). Since re-defining the universal machine changes $K$ by an additive constant, the asymptotics will stay the same. It's really the asymptotics I am after, and I would be surprised if it depended on the reference machine. Not sure how to show this though... $\endgroup$ – P. Trinli May 8 '17 at 20:31
  • $\begingroup$ Do you have a citation or argument for ​ "re-defining the universal machine changes $K$ by an additive constant" ? ​ ​ ​ I thought nothing significantly better was known than ​ "changes $K$ by an additive O(1)" . ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 May 8 '17 at 23:31
  • $\begingroup$ Sorry!! $O(1)$ was what I meant. $\endgroup$ – P. Trinli May 8 '17 at 23:37
  • $\begingroup$ Well, your K-equality is definitely not independent of additive O(1) changes in K, and I don't see any argument for why such changes in K can't infinitely-often change the probability by more than, for example, 1/9. ​ ​ $\endgroup$ – user12859 May 8 '17 at 23:40

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.