CS 530: Geometric and Probabilistic Methods inComputer ScienceHomework 3 (Fall ’06)1. Download the complete amino acid sequence for the chromosome of thebacterium, Buchnera, from the class webpage. Amino acids are representedby single characters from the set:{A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y, $}Using MATLAB, compute the distribution of the amino acids. Plot thedistribution and compute the entropy of the Buchnera chromosome.2. Using the Huffman coding algorithm (executed by hand if you wish), de-vise a variable-length prefix code based on the code alphabet, {A, G, C, T }.Compute the efficiency of the code you devise and compare it to the effi-ciency of the fixed-length “genetic code” used by all living cells. Is yourcode more or less efficient?3. Assuming that the amino acid sequence of the Buchnera chromosome canbe modeled as a first order Markov process, compute the conditional entropyper amino acid. [Hint: Use the amino acid sequence to build a 21 × 21transition matrix, Pt | t−1and compute the conditional entropy, Ht | t−1, asdescribed in the class notes.]4. Using MATLAB, compute the eigenvectors and eigenvalues of the transi-tion matrix you constructed in the last problem. Is the Markov processirreducible and aperiodic? If so, plot the limiting distribution and compareit to the distribution of amino acids you plotted in the first problem.5. You are going to successively flip a coin until the pattern HHT appears; thatis, until you observe two successive heads followed by a tail. In order tocalculate some properties of this game, you set up a Markov chain with thefollowing states: S, H, HH, and HHT, where S represents the starting point,H represents a single observed head, HH represents two successive heads,and HHT is the sequence you are looking for. Observe that if you have justtossed a tails, followed by a heads, a next toss of a tails effectively startsyou over again in your quest for the HHT sequence. Set up the transitionprobability matrix.6. Let x(n)idenote the quality of the n-th item produced by a production systemwith x(n)0being “good” and x(n)1being “defective.” Suppose that x evolvesas a Markov chain whose transition probability matrix is:.99 .12.01 .88What is the probability that the fourth item is defective, given that the firstitem is defective?7. Consider the Markov process whose transition probability matrix, P, isgiven by:.4 .0 .0 .1.0 .7 .3 .2.3 .2 .3 .4.3 .1 .4 .3Suppose that the initial distribution is x(0)= [.1 .1 .5 .3]T.(a) Compute x(1), x(2), x(3)and x(4)(b) Compute P2, P3and P4.(c) Compute x where x = Px.8. Hazel and Naomi each have a brown paper grocery bag containing threeexotic fruits. Initially, Hazel’s bag contains three persimmons and Naomi’sbag contains three kumquats. Once every day, Hazel and Naomi swap onefruit chosen at random from their bags.(a) Derive an expression for the probability that Hazel will have k + 1kumquats today given that she had k kumquats yesterday.(b) Derive an expression for the probability that Hazel will have k kumquatstoday given that she had k kumquats yesterday.(c) Derive an expression for the probability that Hazel will have k − 1kumquats today given that she had k kumquats yesterday.(d) Give the transition matrix for the Markov process.(e) Is the Markov process irreducible? aperiodic? Prove your answers.Hint: Observe that the number of kumquats which Hazel has in her bagalways equals the number of persimmons which Naomi has in her bag andvice versa.9. In this exercise you will simulate the Ising model, a standard model of theemergence of spatial organization in ferromagnetic materials. The inputto your program, written in MATLAB, is a matrix representing a 64 × 64toroidal lattice of randomly oriented spins, i.e., the spin at each locationequals +1 with probability12and −1 with probability12. It will return thematrix of spins after n iterations of the Gibb’s sampling procedure, usingthe conditional p.m.f. computed as described in class. This matrix can bedisplayed as a grey scale image using gdisplay. Hand in your MATLABcode and hardcopy of the results of your simulation for n = 103, 104, 105,and