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?
5
-
$\begingroup$ What description language does your K use? $\endgroup$– user12859Commented May 8, 2017 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. TrinliCommented May 8, 2017 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$– user12859Commented May 8, 2017 at 23:31
-
$\begingroup$ Sorry!! $O(1)$ was what I meant. $\endgroup$– P. TrinliCommented May 8, 2017 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$– user12859Commented May 8, 2017 at 23:40
Add a comment
|