- •13.4 Shift complex sets
- •13.5 Partial randomness
- •13.9.1 Dimension in h-spaces
- •13.10 C-independence and Zimand’s Theorem
- •13.11 Other notions of dimension
- •13.11.1 Box counting dimension
- •13.11.3 Packing dimension
- •13.12 Packing dimension and complexity extraction
- •13.13 Clumpy trees and minimal degrees
- •13.14 Building sets of high packing dimension
- •13.15 Computable dimension and Schnorr dimension
- •13.15.1 Basics
- •13.15.2 Examples of Schnorr dimension
- •13.15.3 A machine characterization of Schnorr dimension
- •13.15.4 Schnorr dimension and computable enumerability
- •13.16 Kolmogorov complexity and the dimensions of individual strings
13.10. C-independence and Zimand’s Theorem |
627 |
13.10 C-independence and Zimand’s Theorem
By Miller’s Theorem 13.8.1, we cannot always extract a sequence of arbitrarily high e ective Hausdor dimension from one of nonzero e ective Hausdor dimension. In this section we prove Zimand’s theorem that such extraction is possible from two su ciently independent sources of positive e ective Hausdor dimension.
We begin by briefly discussing the notion of independence of sources. This notion dates back at least to Chaitin [62], who suggested that objects x and y should be independent in terms of their information if I(x)−I(x | y) and I(y) − I(y | x) are small, where I is some kind of information content measure in the wide sense, such as C or K. For 1-random sets A and B, we could regard A and B as being independent iff they are mutually 1-random.
But what about nonrandom sets? For example, suppose that A and B have positive e ective Hausdor dimension but are not 1-random. What would it mean to say that A and B are independent? The theory here is largely undeveloped, but the following notions of independence are useful for our purposes. In this section, we will regard log factors as being small. We will say a little more about this convention below.10
Definition 13.10.1 (Zimand [424], Calude and Zimand [53]).
(i) X and Y are C-independent 11 if
C((X m) (Y n)) C(X m) + C(Y n) − O(log m + log n).
(ii) X and Y are globally independent if
CX (Y n) C(Y n) − O(log n)
and
CY (X n) C(X n) − O(log n).
Since C and K are within an O(log) factor of each other, both definitions remain the same if we replace C by K. Note also that C((X m) (Y n)) and C((Y n) (X m)) are the same up to an O(log m + log n) factor, so the first definition does not depend on the order of X and Y .
As pointed out by Calude and Zimand [53], other notions of smallness are possible. For example, in (i) we could have O(C(m) + C(n)) in place of O(log m + log n), in which case the definition might be di erent for C and
10In general, working up to O(log n) instead of O(1) smooths out many issues, eliding the di erence between various versions of Kolmogorov complexity, for example. The price one pays is losing the many important phenomena hiding in those log factors, such as K-triviality, the unrelativized complexity characterizations of 2-randomness, and so on.
11Calude and Zimand [53] called this notion finitarily independent. We choose what we feel is a more descriptive name.
628 13. Algorithmic Dimension
for K. These modified concepts remain to be explored. We will stick to log factors, as they give enough independence for the results of this section.
Clearly, if X and Y are mutually 1-random, then they are globally independent, so global independence can be seen as an extension of the notion of mutual randomness. If X is K-trivial, then X and Y are globally independent for all Y , since K(X n) O(log n) and X is low for K, so KX (Y n) = K(Y n) ± O(1). Using Lemma 13.10.2 (ii) below, this observation can be extended to show that if C(X m) O(log m), as is the case for an n-c.e. set, for instance, then X and Y are globally independent for all Y .
The following result is an easy application of symmetry of information (see Section 3.3).
Lemma 13.10.2 (Zimand [424], Calude and Zimand [53]). The following are equivalent.
(i)X and Y are C-independent.
(ii)C(X m | Y n) C(X m) − O(log m + log n).
(iii)C((X n) (Y n)) C(X n) + C(Y n) − O(log n).
(iv)C(X n | Y n) C(X n) − O(log n).
The same holds for K in place of C.
Theorem 13.10.3 (Calude and Zimand [53]). If X and Y are globally independent, then X and Y are C-independent.
Proof. If we have Y as an oracle, we can describe X n by giving n and
a description of X n from Y n, so CY (X n) C(X n | |
Y |
||||
n) + O Y |
|
n |
| |
Y |
|
(log n). So if X and Y are globally independent, then C(X |
|
|
|
n) C (X n) − O(log n) C(X n) − O(log n), and hence item (iv) of Lemma 13.10.2 holds
Stephan (see [53]) showed that the converse fails: there are C- independent X and Y that are not globally independent. He also showed the following.
Theorem 13.10.4 (Stephan, see |
[53]). If X and |
Y are |
left-c.e. |
re- |
als of positive e ective Hausdor |
dimension, then |
X and |
Y are |
not |
C-independent. |
|
|
|
|
Proof. Without loss of generality, there are infinitely many n such that, for the least s for which Ys n = Y n, we also have Xs n = X n. For all such n, we have C(X n | Y n) = O(1). But then, since dim(X) > 0, item (iv) of Lemma 13.10.2 cannot hold.
Theorem 13.10.5 (Calude and Zimand [53]). If Y is 1-random relative to X, then X and Y are C-independent.
13.10. C-independence and Zimand’s Theorem |
629 |
Proof. By the same argument as in the proof of Theorem 13.10.3, KX (Y n) K(Y n | X n) + 2 log n + O(1). If X and Y are not C-independent then there are infinitely many n with K(Y n | X n) < K(Y n) −
5 log n < n − 3 log n. For such n, we have KX (Y n) n − log n + O(1), contradicting the fact that Y is 1-random relative to X.
We now turn to the task of amplifying the complexity of two C-independent sources.
Theorem 13.10.6 (Zimand [424]). For any rational q > 0, there is a truth table reduction Ψ such that if X and Y are C-independent and have e ective Hausdor dimension greater than q, then dim(ΨX Y ) = 1. Moreover, an index for Ψ can be determined computably from q.
The idea of the proof will be to chop X and Y into suitable bits and reassemble them. A technical combinatorial lemma (Lemma 13.10.14) will be at the heart of the proof. It will use a well-known tool from probability theory, Cherno bounds, which can be found in any standard probability textbook, such as Feller [144].
We give a brief introduction to the main ideas of the proof, following Zimand [424]. Suppose that we have two independent strings σ and τ of length n with C(σ) and C(τ ) both equal to qn for a positive rational q. (The independence here means that C(στ ) is approximately C(σ)+C(τ ) = 2qn.) Suppose further that we can construct a function E : 2n ×2n → 2m for some suitable m, such that E is regular, in the sense that for each su ciently
large rectangle B |
|
|
|
n |
|
n |
function E maps about the same |
||||||||||
1 |
× B2 2 |
|
|
× 2 , the |
|||||||||||||
|
|
|
|
|
|
|
|
|
2 |
m |
. Then for a su ciently large |
||||||
number of pairs in B1 × B2 to each τ |
|
||||||||||||||||
B × B 2 |
qn |
× 2 |
qn |
, any τ 2 |
m |
has about |
|B×B| |
many preimages, and any |
|||||||||
|
|
|
|
|
|
2m |
|||||||||||
A 2 |
m |
has about |
|B×B| |
|A| many preimages. |
|
||||||||||||
|
2m |
|
We claim that if ρ = E(σ, τ ) then the C-complexity of ρ must be large. Assume for a contradiction that C(ρ) < (1 − ε)m for a fairly large ε. We have the following facts.
(i)The set B = {σ 2n : C(σ) = qn} has size approximately 2qn.
(ii)The set A = {τ 2m : C(τ ) < (1 − ε)m} has size less than 2(1−ε)m.
(iii)(σ, τ ) E−1(A) ∩ B × B.
qn 2
Thus |E−1(A)∩B ×B| (22εm) , approximately. If we e ectively enumerate E−1(A) ∩ B × B, then each pair of strings in that set can be described by its position in that enumeration, so C(σ, τ ) 2qn − εm, approximately, which violates the independence hypothesis on σ and τ .
Now the above argument is not quite true, as a function E with the necessary properties may not exist, but in Lemma 13.10.14 we will construct a function that makes the above argument “true enough” to prove the theorem.
630 13. Algorithmic Dimension
Proof of Theorem 13.10.6. Note that, by hypothesis, C(X n) > qn and C(Y n) > qn for all su ciently large n.
Lemma 13.10.7. Let r be a rational such that 0 < r < q. For any su ciently large n0, we can compute an n1 > n0 such that
C(X (n0, n1) | X n0) > r(n1 − n0).
Proof. Let 0 < r < q − r and let n1 = 1r−r n0. Suppose that C(X (n0, n1) | X n0) r(n1 − n0). The string X n1 can be described by
giving a description of X n0 and a description of X (n0, n1) given X n0. Thus, for su ciently large n0, we have
C(X n1) n0 + O(log n0) + r(n1 − n0)
rn1 + (1 − r)n0 + O(log n0) rn1 + r n1 + O(log n0) < qn1.
We use Lemma 13.10.7 to split up X and Y into blocks X1X2 . . .
and Y1Y2 . . . , respectively. Each Xi is chosen based on the conditional complexity given the previous blocks, and similarly for the Yi.
Let a be a number such that Lemma 13.10.7 holds for all n0 a. Let b be the constant 1r−r in the proof of Lemma 13.10.7. Let t0 = 0, let ti = a, and let ti+1 = b(t0 + ··· + ti) for i > 0. For i 1, let Xi = X [ti−1, ti)
|
|
. . . Yi. Note that |
and Yi = Y [ti−1, ti). Let Xi = X1 |
. . . Xi and Yi = Y1 |
ti = ab(1 + b)i−2 for i 2 and |Xi| = |Yi| = ab2(1 + b)i−3 for i 3.
The following lemma follows immediately from the definitions and Lemma 13.10.7.
Lemma 13.10.8. The following hold for all i.
| | |
(i) C(Xi Xi−1) > r Xi .
| | | |
(ii) log Xi i and log Xi i.
The same holds for the Yi.
The following inequalities follow easily by symmetry of information.
Lemma 13.10.9. For all σ and τ ,
(i)C(στ ) C(σ) + C(τ ) + O(log C(σ) + log C(τ )),
(ii)C(τ σ) C(σ) + C(τ | σ) − O(log C(σ) + log C(τ )), and
(iii)|C(σ | τ ) − (C(στ ) − C(τ ))| < O(log |σ| + log |τ |).
Now we assemble some facts about the Xi and Yi.
Lemma 13.10.10. For all i and j,
| − |
(i) C(YiXj ) (C(Yi) + C(Xj )) O(i + j),
|
|
|
13.10. |
C-independence and Zimand’s Theorem |
631 |
||||
|
|
|
|
|
|
|
|
|
|
(ii) |C(XiYj ) − (C(Xi) + C(Yj ))| O(i + j), |
|
|
|||||||
(iii) |C(Xi | |
|
|
|
|
|
|
|
|
|
Xi−1Yj ) − C(Xi |
| Xi−1)| O(i + j), and |
|
|||||||
|
|
|
|
|
|
|
|
|
|
(iv) |C(Yi | Xj Yi−1) − C(Yi | Yi−1))| O(i + j). |
|
|
|||||||
Proof. By Lemmas 13.10.9 and 13.10.8, |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
C(YiXj ) C(Yi) + C(Xj ) + O(log C(Yi) + log C(Xj )) |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C(Yi) + C(Xj ) + O(i + j) |
||
and |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C(YiXj ) C(Yi) + C(Xj ) − O(log C(Yi) + log C(Xj )) |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C(Yi) + C(Xj ) − O(i + j). |
||
Putting these two inequalities together gives (i), and (ii) is similar. |
|
||||||||
Now for (iii), by Lemma 13.10.9 (iii), |
|
|
|
|
|||||
|
|
|
|
|
|
− |
|
|
|
|C(Xi | Xi−1Yj ) − (C(XiXi−1Yj ) |
(C(Xi−1Yj )))| O(i + j). |
|
|||||||
|
|
|
|
|
± O(i), and hence |
|
|||
Now, C(XiXi−1Yj ) = C(Xi−1XiYj ) |
|
||||||||
|C(Xi | |
|
|
|
|
|
|
|
|
(13.2) |
Xi−1Yj ) − (C(XiYj ) − (C(Xi−1Yj )))| O(i + j). |
|||||||||
|
|
|
|
|
|
|
|
|
|
By Lemma 13.10.10 (i) and (ii), |C(XiYj ) − (C(Xi) + C(Yj ))| O(i + j) |
|||||||||
|
|
|
|
|
|
O(i + j). Combining these facts |
|||
and |C(Xi−1Yj ) |
− (C(Xi−1) + C(Yj ))| |
||||||||
with (13.2), we have |
|
|
|
|
|
|
|
||
|C(Xi | |
|
|
|
|
|
|
|
(13.3) |
|
Xi−1Yj ) − (C(Xi) − C(Xi−1))| O(i + j). |
|||||||||
By Lemma 13.10.9 (iii), |C(Xi |
|
|
|
|
|
|
|||
| Xi−1)−(C(XiXi−1)−C(Xi−1))| O(i+j). |
|||||||||
|
|
|
|
|
|
|
|
|
|
Thus, since |C(XiXi−1) − C(Xi−1Xi)| O(1), we have |
|
||||||||
|
|C(Xi | |
|
|
|
|
|
|
|
|
|
Xi−1) − (C(Xi) − C(Xi−1))| O(i + j), |
|
and the result now follows by combining this inequality with (13.3). The argument for (iv) is analogous.
The final preparatory lemma is the following. |
|
|
Lemma 13.10.11. For all i, |
|
|
|
|
|
C(XiYi | Xi−1Yi−1) C(Xi | Xi−1Yi−1) + C(Yi | Xi−1Yi−1) − O(i).
Proof. Since C(Xi) |Xi| + O(1) and similarly for Yi, if we apply Lemma 13.10.9 (ii) in conditional form, we get
|
|
|
|
|
|
C(XiYi | Xi−1Yi−1) |
C(Xi | Xi−1Yi−1) + C(Yi | |
XiXi−1Yi−1) − O(i). |
|||
|
|
|
|
|
|
Since C(Yi | XiXi−1Yi−1) = C(Yi | XiYi−1) ± O(1), we have |
|||||
|
|
|
|
|
|
C(XiYi | Xi−1Yi−1) C(Xi | Xi−1Yi−1) + C(Yi | XiYi−1) − O(i).
632 |
13. Algorithmic Dimension |
|
|
|
|
|
|
|
|
But C(Yi | XiYi−1) C(Yi | Yi−1) − O(i) C(Yi | Xi−1Yi−1) − O(i), by Lemma 13.10.10 (iv).
We now come to the combinatorial heart of the proof. Let ni = |Xi| =
| |
Y |
sequence of uniformly computable functions E and |
||||||
i|. We will define a |
|
ni |
× 2 |
ni |
→ 2 |
mi |
i |
|
numbers mi, with Ei : 2 |
|
|
|
. We will then let Zi = E(Xi, Yi). |
||||
|
|
|
|
|
|
|
|
|
The pair (Ei, mi) will be chosen so that C(Zi | Xi−1Yi−1) > (1 − ε)mi,
|
which will imply that C(Zi Zi−1) is also close to mi. We will then be able to show that if we define Z = Z1Z2 . . . , then C(Z k) is su ciently close to k for all k.
The exact method of choosing Ei and mi comes from the theory of randomness extractors and hashing. The proof below uses what is known as the probabilistic method.
Definition 13.10.12. A function E : 2n × 2n → 2m is r-regular if for every B1, B2 2n with |Bi| rn for i = 1, 2 and every σ 2m,
|E−1(σ) ∩ (B1 × B2)| 2−m+1|B1 × B2|.
The function E is weakly r-regular if it obeys the above definition when we consider only Bi with |B1| = |B2| = rn .
Lemma 13.10.13. If E : 2n × 2n → 2m is weakly r-regular then E is regular.
Proof. Let k = rn and suppose that for all B1, B2 with |Bi| = 2k and all σ 2m, we have |E−1(σ) ∩ (B1 × B2)| 2−m+1|B1 × B2| = 2−m+1+2k.
Let k1, k2 k and let B1 and B2 be such that |Bi| = 2ki . Partition each
|
|
|
|
|
|
i |
i |
|
|
i |
|
k |
. Then |
|
|
Bi into pairwise disjoint sets A0, A1 |
, . . . , A2ki −k−1 of size 2 |
|
|
||||||||||||
E−1 |
(σ) |
∩ |
(B |
1 × |
B ) = |
E−1(σ) |
∩ |
(A1 |
A2) |
|
|
|
|
||
| |
|
|
2 | |
| |
|
i × |
j | |
|
|
|
|
||||
|
|
|
|
|
|
i,j si |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2k1+k2−2k2−m+1+2k |
= 2−m+12k1+k2 = 2−m+1 B |
B . |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
× 2 |
| |
Lemma 13.10.14. For each r > 0, if 2m < r2.99n then with positive
probability, a randomly chosen function E : 2n |
×2 |
n |
→ 2 |
m |
will be r-regular. |
||||||
In particular, an r-regular E : 2 |
n |
×2 |
n |
→ 2 |
m |
|
|
|
|||
|
|
|
exists (and hence can be found |
e ectively by searching).
Proof. By the previous lemma, it is enough to show that E is weakly r- regular. Let N = 2n and M = 2m (as numbers).
Choose B1, B2 2n with |Bi| = N r (ignoring rounding for simplicity). Let j1 B1 × B2 and j2 2m. We think of 2n × 2n as a table with N rows and N columns, of 2m as colors, and of E as specifying a coloring. Then B1 × B2 is a rectangle in this table, j1 is a cell in this rectangle, and j2 is one of M possible colors for this cell. Clearly Prob(E(j1) = j2) = M1 .
13.10. C-independence and Zimand’s Theorem |
633 |
be the number of j2-colored cells in B1 × B2. If there is no rectangle B1 × B2 and j2 such that − M1 > M1 , then E is weakly r-regular, so it is enough to show that this event has positive probability.
Applying the Cherno bounds mentioned above, we have
|
|
|
|
|
|
Prob |
|
Cj |
|
1 |
1 |
|
|
|
|
N 2r |
||||||||||||
|
|
|
|
|
|
|
2 |
|
− |
|
|
> |
|
|
|
|
< e− 3M . |
|||||||||||
|
|
|
|
|
|
|
N 2r |
|
M |
M |
|
|
||||||||||||||||
The probability that |
Cj2 |
−m |
1 |
|
> |
1 |
|
for some j2 2m is less than or equal |
||||||||||||||||||||
N 2r |
M |
M |
||||||||||||||||||||||||||
to |
the sum over all j |
|
|
of the above probability, and hence less than |
||||||||||||||||||||||||
|
N 2r |
2 2 |
|
|
||||||||||||||||||||||||
M e− |
3M . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
The number of rectangles B1 × B2 is |
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
N |
2 |
|
|
eN |
N r |
|
|
|
|
r |
r |
|
|
|
|||||||||
|
|
|
|
|
N r |
|
|
|
N r |
|
|
|
|
= e2N |
|
e2N |
(1−r) ln N . |
|||||||||||
Thus, to argue that there is no rectangle B |
|
|
|
|
|
Cj2 |
|
|||||||||||||||||||||
1 |
× B2 and j2 such that N 2r − |
|||||||||||||||||||||||||||
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
> |
|
|
, and hence E is weakly r-regular, it is enough to show that |
|||||||||||||||||||||||
|
M |
M |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
2r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
M e−N3M e2N r e2N r (1−r) ln N < 1. |
Straightforward manipulation shows that this task is the same as showing that N3M2r −ln M > 2N r +2N r(1−r) ln N , which holds when M < N .99r.
We are finally ready to build Z. We proceed as follows.
1. Split X = X1X2 . . . and Y = Y1Y2 . . . as above, using the parameters
r = |
q |
and r = |
q |
to define a and b. Note that for each i, we have |
|
2 |
|
4 |
|
C(Xi |
|
|||
| Xi−1) > rni and C(Yi | Yi−1) > rni. |
2.For the parameters ni = |Xi| = |Yi| and mi = i2, find an r2 -regular function Ei. Let Zi = Ei(Xi, Yi).
3.Let Z = Z1Z2 . . . .
Lemma 13.10.15. For all ε > 0 and all su ciently large i, we have
C(Zi | |
|
|
|
|
|
|
|
|
|
|
|
Xi−1Yi−1) (1 − ε)mi. |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
− ε)mi, let |
|
|
||
Proof. If C(Zi | Xi−1Yi−1) < (1 |
|
|
|||||||||
|
|
|
A = {σ 2 |
mi |
|
|
|
|
|
|
|
|
|
|
|
| C(σ | Xi−1Yi−1) < (1 − ε)mi}. |
|||||||
Then |A| < 2(1−ε)mi . Let t1 |
= C(Xi | |
Xi−1Yi−1) and t2 = C(Yi | |
|||||||||
|
|
|
|
|
|
|
= {σ |
2 |
ni |
|
|
Xi−1Yi−1). For j = 1, 2, let Bj |
|
| C(σ | Xi−1Yi−1) tj }. By |
Lemma 13.10.9 (iii) and (iv), if i is su ciently large then tj > rni −O(i) >
r |
|
|
2 ni for j = 1, 2, since C(Xi | |
Xi−1) > rni |
and C(Yi | Yi−1) > rni. |
Now, |Bj | 2tj +1, so we can choose Bj |
Bj of size 2tj +1. The bounds |
|
on the tj imply that the Bj |
are large enough to allow us to invoke the |
634 13. Algorithmic Dimension
bounds for the regularity of Ei. Therefore, for any σ 2mi ,
|E−1(σ) ∩ (B1 × B2)| 2−mi+1|B1 × B2|.
Thus
|E−1(A) ∩ (B1 × B2)| |E−1(A) ∩ (B1 × B2)|
|E−1(σ) ∩ (B1 × B2)| 2t1+t2−εmi+3.
σ A
Since E−1(A) ∩ (B1 × B2) can be e ectively listed given the parameters
− −1 ∩ ×
Xi−1, Yi−1, (1 ε)mi, t1, t2, for any (σ, τ ) E (A) (B1 B2), we have
|
|
|
t1 |
+ t2 − εmi + 2(log(1 − ε)mi + log t1 + log t2) + O(1). |
||||||
C(στ | Xi−1Yi−1) |
||||||||||
Using the facts that mi = i2 and log ti |
= O(i), we see that there is a δ > 0 |
|||||||||
such that C(στ | |
|
|
|
+ t2 |
− δi |
2 |
for all su ciently large i. In |
|||
Xi−1Yi−1) t1 |
|
|||||||||
particular, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
) |
|
|
|
C(XiYi | Xi−1Yi−1) |
t1 + t2 − δ(i |
||||||
for all su ciently large i. However, by Lemma 13.10.11, |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
C(XiYi | Xi−1Yi−1) |
C(Xi | Xi−1Yi−1) + C(Yi | Xi−1Yi−1) − O(i) |
= t1 + t2 − O(i).
For su ciently large i, we have a contradiction.
Lemma 13.10.16. For any δ > 0 and n, we have C(Z n) (1 − δ)n − O(1). Hence Z has e ective Hausdor dimension 1.
Proof. Let ε = |
δ |
|
|
|
|
4 . By Lemma 13.10.15, C(Zi | Xi−1Yi−1) (1 − ε)mi for |
|||||
|
|
|
|
− ε)mi − O(1), since we can compute |
|
almost all i. Thus (Zi | Zi−1) (1 |
|||||
|
|
|
|
|
|
Zi−1 |
from Xi−1Yi−1. A straightforward induction shows that C(Zi) (1 − |
||||
3ε)(m1 + · · · + mi) for su ciently large i. |
|
||||
|
|
|
|
|
|
Now take σ = Z n between Zi 1 |
and Zi, and assume for a contradiction |
||||
|
|
|
− |
|
by giving a description |
that C(σ) (1 − δ)|σ|. Then we can describe Zi−1 |
of σ, which takes (1 −4ε)|σ| < (1 −4ε)(m1 + · · ·+ mi) many bits, the string
|
|
| mi many bits, |
τ such that σ = Zi−1 |
τ , which takes a further |σ| − |Zi−1 |
and O(log mi) many further bits to separate the descriptions of σ and τ . Therefore, for su ciently large i,
i−1) (1 − 4ε)(m1 + · · · + mi) + mi + O(log mi)
Z
(
C
=(1 − 4ε)(m1 + · · · + mi−1) + (2 − 4ε)mi + O(log mi)
<(1 − 3ε)(m1 + · · · + mi−1),
the last inequality holding because limi |
mi |
= 0. Thus we have a |
m1+···+mi−1 |
contradiction, and hence C(Z n) > (1 − δ)n for almost all n.