# Kolmogorov complexity of a random string conditioned on another random string

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?

• What description language does your K use? ​ ​ – user12859 May 8 '17 at 20:10
• 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... – P. Trinli May 8 '17 at 20:31
• 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)" . ​ ​ ​ ​ ​ ​ ​ – user12859 May 8 '17 at 23:31
• Sorry!! $O(1)$ was what I meant. – P. Trinli May 8 '17 at 23:37
• 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. ​ ​ – user12859 May 8 '17 at 23:40