An infinite binary sequence has randomness rate at least $sigma$ if, for almost every $n$, the Kolmogorov complexity of its prefix of length $n$ is at least $sigma n$. It is known that for every rational $sigma in (0,1)$, on one hand, there exists sequences with randomness rate $sigma$ that can not be effectively transformed into a sequence with randomness rate higher than $sigma$ and, on the other hand, any two independent sequences with randomness rate $sigma$ can be transformed into a sequence with randomness rate higher than $sigma$. We show that the latter result holds even if the two input sequences have linear dependency (which, informally speaking, means that all prefixes of length $n$ of the two sequences have in common a constant fraction of their information). The similar problem is studied for finite strings. It is shown that from any two strings with sufficiently large Kolmogorov complexity and sufficiently small dependence, one can effectively construct a string that is random even conditioned by any one of the input strings.
展开▼
机译：如果几乎每个$ n $的长度为$ n $的前缀的Kolmogorov复杂度至少为$ sigma n $，则无限二进制序列的随机率至少为$ sigma $。众所周知，一方面，对于（0,1）$中的每个有理$ sigma，都存在具有随机率$ sigma $的序列，这些序列无法有效地转换为具有高于$ sigma $的随机率的序列，并且另一方面，任意两个具有随机率$ sigma $的独立序列都可以转换为随机率高于$ sigma $的序列。我们表明，即使两个输入序列具有线性相关性，后者的结果仍然成立（非正式地说，这意味着两个序列的长度为$ n $的所有前缀在其信息中都具有恒定的比例）。对于有限字符串研究了类似的问题。从任何两个具有足够大的Kolmogorov复杂度和足够小的依赖性的字符串中可以看出，一个字符串可以有效地构造一个甚至由输入字符串中的任何一个条件随机的字符串。
展开▼
