An Introduction To Kolmogorov Complexity And Its Applications 4th Edition Ming Li, Paul Vitányi - Solutions

Discover comprehensive resources for "An Introduction To Kolmogorov Complexity And Its Applications, 4th Edition" by Ming Li and Paul Vitányi. Access the complete online answers key and solutions manual, offering step-by-step answers and solved problems for in-depth understanding. Our solutions PDF includes test bank questions and answers, along with chapter solutions and an instructor manual for educators. This essential textbook is complemented by free download options, ensuring that learners have all the tools they need for mastering Kolmogorov Complexity. Dive into detailed explanations and enhance your knowledge with our expertly crafted content.

A box contains 6 green and 11 yellow balls. Three are chosen at random. The first and third balls are yellow. Which method of sampling—with replacement or without replacement—gives the higher probability of this event?
A marksman, whose probability of hitting a moving target is 0.6, fires three shots.Suppose the shots are independent.(a) What is the probability the target is hit?(b) How many shots must be fired to make the probability at least 0.99 that the target will be hit?
A box contains 8 red, 3 white, and 9 blue balls. Three balls are to be drawn, without replacement. What is the probability that more blues than whites are drawn?
Suppose A and B are events. Explain why P(exactly one of events A, B occurs) =P(A) + P(B) − 2P(A ∩ B).
A machine is composed of two components, A and B, which function (or fail) independently.The machine works only if both components work. It is known that component A is 98% reliable and the machine is 95% reliable. How reliable is component B?
A lot of 24 tubes contains 13 defective ones. The lot is randomly divided into two equal groups, and each group is placed in a box.(a) What is the probability that one box contains only defective tubes?(b) Suppose the tubes were divided so that one box contains only defective tubes. A box is chosen
How many tosses of a fair coin are needed so that the probability of at least one head is at least 0.99?
Show that if A and B are independent, then A and B are independent.
How many lines are determined by 8 points, no three of which are collinear?
Two good transistors become mixed up with three defective transistors. A person is assigned to sampling the mixture by drawing out three items without replacement.However, the instructions are not followed and the first item is replaced, but the second and third items are not replaced.(a) What is
Given: A and B are events with P(A) = 0.3, P(B) = 0.7 and P(A ∪ B) = 0.9. Find(a) P(A ∩ B)(b) P(B|A).
An oil wildcatter thinks there is a 50-50 chance that oil is on the property he purchased.He has a test for oil that is 80% reliable: that is, if there is oil, it indicates this with probability 0.80 and if there is no oil, it indicates that with probability 0.80. The test indicates oil on the
In a roll of a pair of dice (one red and one green), let A be the event “red die shows 3, 4, or 5,” B the event “green die shows a 1 or a 2,” and C the event “dice total 7.” Show that A, B, and C are independent.
A committee of 50 politicians is to be chosen from the 100 US Senators (2 are from each state). If the selection is done at random, what is the probability that each state will be represented?
Suppose 0.1% of the population is infected with a certain disease. On a medical test for the disease, 98% of those infected give a positive result while 1% of those not infected give a positive result. If a randomly chosen person is tested and gives a positive result, what is the probability the
What is the probability a bridge hand is missing cards in at least one suit?
An individual tried by a three-judge panel is declared guilty if at least two judges cast votes of guilty. Suppose that when the defendant is, in fact, guilty, each judge will independently vote guilty with probability 0.7 but, if the defendant is, in fact, innocent, each judge will independently
A box contains 6 good and 8 defective light bulbs. The bulbs are drawn out one at a time, without replacement, and tested. What is the probability that the fifth good item is found on the ninth test?
What is the probability a poker hand contains exactly one pair?
An experiment consists of choosing two numbers without replacement from the set{1, 2, 3, 4, 5, 6} with the restriction that the second number chosen must be greater than the first.(a) Describe the sample space.(b) What is the probability the second number is even?(c) What is the probability the sum
Bean seeds from supplier A have an 85% germination rate and those from supplier B have a 75% germination rate. A seed company purchases 40% of their bean seeds from supplier A and the remaining 60% from supplier B and mixes these together. If a seed germinates, what is the probability it came from
If A, B, and C are independent events, showthat the events A and B ∪ C are independent.
A quality control inspector draws parts one at a time and without replacement from a set containing 5 defective and 10 good parts. What is the probability the third defective is found on the eighth drawing?
Suppose that E and T are independent events with P(E) = P(T) and P(E ∪ T) = 1∕2.What is P(E)?
A manufacturer of calculators buys integrated circuits from suppliers A, B, and C. Fifty percent of the circuits come from A, 30% from B, and 20% from C. One percent of the circuits supplied by A have been defective in the past, 3% of B’s have been defective, and 4% of C’s have been defective.
An elevator starts with 10 people on the first floor of an eight-story building and stops at each floor.(a) In how many ways can all the people get off the elevator?(b) How many ways are there for everyone to get off if no one gets off on some two specific floors?(c) In how many ways are there for
Suppose that A and B are events for which P(A) =a, P(B) = b and P(A ∩ B) = c.Express each of the following in terms ofa, b, and c.(a) P(A ∪ B)(b) P(A ∩ B)(c) P(A ∪ B)(d) P(A ∩ B)(e) P(exactly one of A or B occurs).
A day’s production of 100 fuses is inspected by a quality control inspector who tests 10 fuses at random, sampling without replacement. If he finds 2 or fewer defective fuses, he accepts the entire lot of 100 fuses. What is the probability the lot is accepted if it actually contains 20 defective
How many bridge hands are there containing 3 hearts, 4 clubs, and 6 spades?
An instructor has decided to grade each of his students A, B, or C. He wants the probability a student receives a grade of B or better to be 0.7 and the probability a student receives at most a grade of B to be 0.8. Is this possible? If so, what proportions of each letter grade must be assigned?
A fair coin is tossed four times. Let A be the event “2nd toss is heads,” B be the event“Exactly 3 heads,” and C be the event “4th toss is tails if the 2nd toss is heads.” Are A, B, and C independent?
In a sample space, events A and B are such that P(A) = P(B), P(A ∩ B) = P(A ∩ B) =1∕6. Find(a) P(A).(b) P(A ∪ B).(c) P(Exactly one of the events A or B).
If the integers 1, 2, 3, and 4 are randomly permuted, what is the probability that 4 is to the left of 2?
A number, X, is chosen at random from the set {10, 11, 12, ..., 99}.(a) Find the probability that the 10’s digit in X is less than the units digit.(b) Find the probability that X is at least 50.(c) Find the probability that the 10’s digit in X is the square of the units digit.
Acollege senior finds he needs one more course for graduation and finds only courses in Mathematics, Chemistry, and Computer Science available. On the basis of interest, he assigns probabilities of 0.1, 0.6 and 0.3, respectively, to the events of choosing each of these. After considering his past
Acommittee of 5 is chosen from a group of 8 men and 4women. What is the probability the group contains a majority of women?
A and B are special dice. The faces on die A are 2, 2, 5, 5, 5, 5 and the faces on die B are 3, 3, 3, 6, 6, 6. The two dice are rolled. What is the probability that the number showing on die B is greater than the number showing on die A?
How many people must be in a group so that the probability that at least two were born on the same day of the week is at least 1/2?
How many distinguishable arrangements of the letters in PROBABILITY are there?
Events A, B, and C in a sample space have P(A) = 0.2, P(B) = 0.4, and P(A ∪ B ∪ C) =0.9. Find P(C) if A and B are mutually exclusive, A and C are independent, and B and C are independent.
Events A and B are such that P(A ∪ B) = 0.8 and P(A) = 0.2. For what value of P(B) are(a) A and B independent?(b) A and B mutually exclusive?
Suppose that events A, B, and C are independent with P(A) = 1∕3, P(B) = 1∕4, and P(A ∪ B ∪ C) = 3∕4. Find P(C).
Show that (n − k)( n n−k)= (k + 1)( n k+1).
A hat contains slips of paper on which each of the integers 1, 2, … , 20 is written. A sample of size 6 is drawn (without replacement) and the sample values, xi, put in order so that x1 < x2 < · · · < x6. Find the probability that x3 = 12.
[34] Show that every quantum Turing machine can be simulated to every degree of precision by a quantum Turing machine that has a single primitive rotation θ with cos θ = 3 5 and sin θ = 4 5 .Comments. Hence, we can restrict ourselves to such quantum Turing machines in the definition of KQ. Then,
[37] Define the notion of a quantum Turing machine, and show that there is a universal quantum Turing machine that can simulate t steps of every other quantum Turing machine on input x up to precision (in the fidelity sense) in time polynomial in t, l(x), and 1/.Comments. Source: [E. Bernstein
[34] Show that all but an exponentially vanishing fraction of states |x have KQ(|x |n) ≥ 2n − 2 log n − O(1).Comments. This shows that most pure quantum states are maximally incompressible, in line with the classical case. Hint: Since the quantum Kolmogorov complexity of an n-qubit state is
[37] Recall the definition of the NWD for multisets in Equation 8.24 on page 706. Let X, Y, Z be search terms (sets of at least two words) and N>d(X).(a) Show that 0 ≤ NWD(X) ≤ (logd(X)(N/d(X)))/(d(X) − 1).(b) Use (f(y1)f(X))/(f(x1)f(Y )) ≥ (f(x0)/f(y0))(d(X)−1)NWD(X) with x0 = arg
• [35] This exercise and the next one are about web similarity.Let X be a search term (web query) with d(X) ≥ 3.(a) Show that the common similarity (common semantics) NWD(X)can not be derived in general from the pairwise NWD’s of pairs of members of X.(b) Show that classification using NWD(X)
[34] Show that in some cases the classification of x using eZ in Equation 8.22 does not work in the sense that all of A, B, . . . , Y give the same difference as eZ(A {x}) − eZ(A). Show that this scenario is impossible using eZ,1 in Equation 8.23.Comments. Hint: For example, use Remark VI.5 in
[32] Let X ∈ X and IDZ(X) be as in Equation 8.21. Show that IDZ(X) is an admissible distance and a metric.
[35] Let X ∈ X. Show that the function e(X) is a metric up to an additive O((log K)/K) term in the respective metric (in)equalities, where K is the largest Kolmogorov complexity involved the (in)equality.Comments. This proves Theorem 8.5.3.
[16] Let X be the set of finite multisets, X, Y ∈ X, and d : X →R+ be a distance that satisfies the triangle inequality of a metric. Show that if Y ⊆ X then d(Y ) ≤ d(X).Comments. Source (also for the following three exercises): [A.R. Cohen, P.M.B. Vit´anyi, IEEE Trans. Pattern Analysis
• [36] Let the information distance for multisets ID(X) be defined as in Definition 8.5.1 on page 698 either with the plain Kolmogorov complexity or with the prefix Kolmogorov complexity. Show that the maximal overlap, metricity, universality, and minimal overlap properties holding for the
• [17] Let k be a positive integer, X a multiset of strings with d(X) ≥ 2, and maxx∈X{K(X|x)} = k. Information distance in a multiset of strings using plain Kolmogorov complexity is defined in Definition 8.5.1 on page 698. Originally it was defined as ID(X) = min{l(p) :U(p,x, d(X) ) = X for
• [41] Let k be a positive integer, X a multiset with d(X) =n ≥ 2, and maxx∈X{C(X|x, d(X) )} = k. Theorem 8.5.1 on page 699(respectively its corollary) give an upper bound on ID(X) defined in Definition 8.5.1 on page 698 using plain Kolmogorov complexity. Here we are interested in a lower
By Item (a) the distance E5 equals the maximal overlap in Corollary 8.3.1 on page 666, up to an additive logarithmic term. Source for Items (a),(b), (c), (e), and (f): [M. Li, Int. J. Found. Comput. Sci., 18:4(2007), 669–681].
[28] Let U be the reference universal prefix machine. The cost of two-way conversion between x and y in the sense of a new distance E5 is defined by E5(x, y) = min{l(p) : U(x, p, r) = y, U(y, p, q) = x}, the minimum taken over all p, q, r such that l(p) + l(q) + l(r) ≤ E(x, y).This definition
[31] Show that the distance eG of Equation 8.14 on page 691 is computable, takes values primarily in [0, 1] but also outside in pathological cases, and is not a metric since it violates eG(x, y) = 0 for x = y, and eG(x, y) + eG(y, z) can be less than eG(x, z).Comments. Source: [R.L. Cilibrasi and
[O45] The NID is not computable. The distance eZ is a heuristic approximation that can deviate from the NID, notwithstanding the fact that it is successfully applied. Can you formulate another, better, practical theory of a normalized compression distance using a real-world compressor than in
• [38] Let Z(x) denote the binary length of the compressed version of x using compressor Z. A compressor Z is normal if it is a real-world compressor and satisfies the axioms (identity) Z(xx) = Z(x)and Z(λ) = 0 where λ is the empty string, (monotonicity) Z(xy) ≥Z(x), (symmetry) Z(xy) = Z(yx),
[25] The sum distance E4 = K(x|y) + K(y|x) is a metric by Theorem 8.3.6.Prove that its normalization defined by e4 = (K(x|y) +K(y|x))/K(x, y) takes values in [0, 1] and is also a metric.Source: [M. Li, J.H. Badger, X. Chen, S. Kwong, P. Kearney, and H.Zhang, Bioinformatics 17:2(2001), 149–154].
[24] For a computable probability distribution the expected value of Kolmogorov complexity equals the Shannon entropy up to the prefix Kolmogorov complexity of the probability distribution plus a constant(Theorem 8.1.1 on page 626). Show a similar relationship between entropy and information
[38] (a) Prove that the NID of Definition 8.4.1 on page 684 is not a semicomputable function, that is, it is neither lower semicomputable nor upper semicomputable.(b) Prove that there is no semicomputable function within computable distance of the NID function.(c) Call a function f(x, y) computable
[22] Show that we can reduce the error term in Theorem 8.4.1 to O(1/K).Comments. Use Lemma 3.8.1 on page 250. Source: [M. Li, X. Chen, X.Li, B. Ma, and P.M.B. Vit´anyi, Ibid.].
[22] Show that the NID of Definition 8.4.1 on page 684 satisfies d({y : e(x, y) ≤ δ ≤ 1}) < 2δK(x)+1.Comments. The density requirement is implied by a normalized version of the Kraft inequality, y:x =y 2−e(x,y)K(x) ≤ 1 for every x. Source: [M.Li, X. Chen, X. Li, B. Ma, and P.M.B.
[33] (a) Let x, y ∈ Rn (R denotes the real numbers) and denote by x−y the Euclidean metric—the L2 norm. Show that the normalized Euclidean distance x − y/(x + y), has values in [0, 1] only and is also a metric.(b) Let A, B be finite sets and AΔB = A B − (A B) the symmetric
• [42] Show that there exists an infinite sequence of pairs of strings (x, y) such that E0(x, y) > max{K(x|y), K(y|x)}+log log l(xy)−O(log log log l(xy)). Show that this implies the same result for sets X of n > 2 strings.Comments Source: [B. Bauwens and A.K. Shen, Information Distance
[38] Show that there are stringsa, b, and p of lengths n, 2n, and k ≥ 2n, respectively, having the following properties: (i) C(b|a, p) =0; (ii) C(p|a) ≥ k; (iii) there is no string q such that C(q) ≤ k − n, C(q|p) ≤ n, and C(b|a, q) ≤ n, all (in)equalities holding to within an additive
[29] (a) Prove that for every natural number n there exist infinitely many strings x (which may be very long compared to n) such that C(x) > 2n and for every string y with C(y|x) < n we have either C(y) < n + O(1) or C(x|y) < n + O(1).(b) Show that for the x’s of Item (a) there is no y such that
[35] It is easy to see that for every string x and every integer n, there is a y such that the information distance max{C(x|y), C(y|x)}between x and y is n + O(1). Prove that for every n and for every string x such that C(x) ≥ 2n + O(1) there exists a string y such that both C(x|y) and C(y|x) are
[36] Use the techniques in Muchnik’s theorem, Theorem 8.3.7, to prove the following.(a) For all strings x, y, and z of length less than n and C(x|y) = C(x|z) =m, there exists a string p of length m such that C(p|x) = C(x|p, y) =C(x|p, z) = O(log n). That is, p is a program for x when y or z is
[39] (a) Show that for strings x and y that are random with respect to one another in the sense that K(x|y) ≥ l(x) and K(y|x) ≥ l(y),there are p and q such that K(p) = K(y|x), K(q) = K(x|y), I(p; q) = 0, U(p, x) = y, and U(q, y) = x, where the first three equalities hold up to an additive
• [46] Muchnik’s theorem leads to an analogue of the full Slepian–Wolf theorem.(a) Show that there exists a probabilistic algorithm E (the encoding procedure) and a deterministic algorithm D (the decoding procedure)that behave as follows:(i) On input ∈ (0, 1), nx, x, the algorithm E
[O40] Develop a theory of resource-bounded (polynomial-time or logarithmic-space) information distance.
[23] Define a uniform variant Eu of E3 based on the uniform Kolmogorov complexity variant of Exercise 2.3.2 on page 130. Show that the energy dissipation can be reduced arbitrarily far by a computation that uses enough (that is, an incomputable amount of) time. That is, there is an infinite
[28] Show that there is a computably enumerable infinite sequence χ and some (incomputably) large time bound T such that for every total computable time bound t, for each initial segment x of χ, Et 3(x, ) > ct2ET 3 (x,)/2, where ct > 0 is a constant depending only on t and χ.
[37] Use the notions of Exercise 8.3.2.Prove a time–energy tradeoff hierarchy: For every large enough n there is a string x of length n and a sequence of m = 1 2√n time functions t1(n) < t2(n) < ··· < tm(n)such that Et1 3 (x, ) > Et2 3 (x, ) > ··· > Etm 3 (x, ).Improve this result by
[25] We determine the irreversibility cost of effective erasure. Let x be a string and t(n) ≥ n (n = l(x)) be a time bound that is provided at the start of the computation. Show that erasing the n-bit record x by an otherwise reversible computation can be done in time (number of steps) O(2nt(n))
[32] Prove the upper bound on E3 of Theorem 8.3.5 on page 673 by a direct construction supplying logarithmically small initial programs and ending with logarithmically small garbage.Comments. Source: [M. Li and P.M.B. Vit´anyi, Proc. Royal Soc. London, Ser. A, 452(1996), 769–789]. This is also
[21] Fix a reference universal reversible Turing machine, say UR0. Define Et 3(x, y) = min{l(p) + l(q) : UR0(p, x ) = q, y in t(n)steps of computation, where n = l(x)}. Show that for every computable function t there is an x such that Et 3(x, ) > E3(x, ).
[31] Let x be a binary string of length n, and B1(x,d) be the set of strings y with E1(x, y) ≤d. Let the number of elements in B1(x,d) be denoted by b1(x, d). The set B1(d, x, n) is defined as B1(x, d){0, 1}n and b1(d, x, n) is the number of elements in B1(d, x, n).(a) Show that up to an
[34] Let an irreversible computation use t steps and s space.(a) Show how to simulate it reversibly using t = Θ(t1+/s) steps and s = Θ(c()s(1 + log t/s)) space with c() = 21/ for any > 0 using always the same simulation method with different parameters. Typically, = log 3.(b) Show that
[36] Prove the existence of a universal reversible Turing machine.Comments. Source: [C.H. Bennett, IBM J. Res. Develop., 17(1973), 525–532]. If the original computation takes t steps and uses s space then Bennett’s simulation requires t = Θ(t) steps and s = Θ(st) space.
[20] Construct reversible OR, NOT, and XOR gates using Fredkin gates.
[27] Let x = x1 ...xn be obtained by random i.i.d. sampling a sequence X1,...,Xn of n random variables which are all copies of a random variable X. Let X have a finite range X and let Y be a finite set of destination words. Given a distortion function d(a,b) with a ∈ X and b ∈ Y extend it to
[41] Prove Theorem 8.1.7.Comments. Hint: use Theorem 8.1.8.Source: [N.K. Vereshchagin and P.M.B. Vit´anyi, Ibid.].
[41] Use Exercise 8.1.13 to prove Theorem 8.1.8.Comments. Source: [N.K. Vereshchagin and P.M.B. Vit´anyi, Ibid.].
[42] Let B be a family of nonempty subsets of {0, 1}n. Let m, k be natural numbers. If a string x of length n is an element of at least 2m sets of complexity at most k in B, then x is an element of a set in B of complexity at most k − m + O(K(B) + log n + log k + log m).Comments. For l = 0 this
[25] Consider the rate-distortion family En of Euclidean distortion.(a) Show that the rate-distortion function of x is related to the structure function gx by rx(δ) = gx(n + log δ) + O(1).(b) Show that for every n-bit rational number 0 ≤ x ≤ 1, we have rx( 1 2 ) = O(1), and 0 ≤ rx(δ) −
[35] Let r(δ) be the function shown in Figure 8.1 on page 638.(a) Show that K(r) = O(log n), and that r satisfies the conditions of Exercise 8.1.10.(b) Show that the rate-distortion graph rx(δ) of the string x existing by Exercise 8.1.10 is in the strip of size O(√n log n) of the graph of
[32] The distortion family Hn satisfies properties 1 through 4 in Definition 8.1.5, where property 4 follows from Exercise 8.1.9.(a) Show that rx(δ) = gx(nH(δ)) + O(log n) for every 0 ≤ δ ≤ 1 2 .(b) For every x of length n, we have rx( 1 2 ) = O(log n), and rx(δ) −rx(δ) ≤ n(H(δ)
[36] Let Hn be the Hamming distortion family of strings of length n. Show that Hn satisfies property 4 in Definition 8.1.5.For everyδ ≤ δ ≤ 1 2 , every Hamming ball of radius δ can be covered by at mostαnbn(δ)/bn(δ) Hamming balls of radius δ, where the covering coefficientαn is
[30] (a) Show that for every x and y there exists a z such that 2K(z)+K(y|z, x)+K(x|z,y) ≤ 2 max{K(x|y), K(y|x)}+O(log n), where n = l(x) + l(y).(b) Show that for every n there are random variables X, Y with 2n + 1 outcomes each such that for every random variable Z we have 2H(Z) +H(X|Y,Z) + H(Y
[39] Prove Theorem 8.1.3.Comments. Source: [D. Hammer, A.E. Romashchenko, A.K. Shen, and N.K. Vereshchagin, J. Comput. Syst. Sci., 60(2000), 442–464].
Item (b) follows by appropriate modification of the reference machine. Source: The basic Equation 8.3 appears in[P. G´acs, Lecture Notes on Descriptional Complexity and Randomness, Manuscript, Boston University, 1987; T.M. Cover, P. G´acs, and R.M.Gray, Ann. Probab., 17:3(1989), 840–865; W.H.
[32] Let P be a (possibly incomputable) probability mass function.(a) Show that 0 ≤ x P(x)K(x|P)−H(P) = O(1), where the O(1) term is independent of P and depends only on the reference prefix machine.(b) Show that 0 ≤ x P(x)K(x|P)−H(P) < 1 for all P for some appropriate reference prefix
[21] Let P be a computable probability mass function of m identically distributed random variables. Show that the analogue of Theorem 8.1.1 holds. In this case, the entropy is proportional to m, but cP is O(log m).Comments. Hint: use K(P) = O(log m) and a similar proof to Theorem 8.1.1.Source:
[19] Let P be a probability mass function and let A ⊆ N be computably enumerable. Define PA(x) = P(x|x ∈ A) and PA(x)=0for x ∈ A, and let PA be computable and H(PA) finite. Show that x PA(x)C(x|A, PA) ≤ H(PA) +O(1), where the O(1) term is independent of P and A.Comments. Hint: Let x1,
[25] Let P be a (possibly incomputable) probability mass function, and let Pn(x) = P(x|l(x) = n) and Pn(x) = 0 for l(x) = n. Show that H(Pn)−x Pn(x)C(x) ≤ log n+ 2 log log n+O(1), where the O(1)term is independent of P and n.Comments. Hint: By K(x) ≤ C(x) + K(C(x)) + O(1) and the left side

Showing 300 - 400 of 3340

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Last

An Introduction To Kolmogorov Complexity And Its Applications 4th Edition Ming Li, Paul Vitányi - Solutions

Step by Step Answers