Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer ScienceDepartment of Mechanical Engineering6.050J/2.110J Information and Entropy Spring 2005Issued: March 14, 2005 Problem Set 7 Due: March 18, 2005Problem 1: Confusius Gate...The pro c es s model covered this week can be used for both deterministic systems, whose output is determinedby the input, and by nondeterministic systems. Let’s use it to describe the action of a a peculiar gate. Thegate in Figure 7–1 will output the opposite of what the input was when both input bits are the same, andthe second input bit if the two bits in the input differ.---- --ZZZZZZZZ~HHHHHHHHj*>0001101101Figure 7–1: A confusius gatea. First, consider the channel without defects, as shown in Figure 7–1. Assume each of the fourpossible inputs is equally likely, for example if the input had been obtained by two indep e ndentcoin tosses. Calculate the two output probabilities p(B0) and p(B1), the input information I, theoutput information J, the noise N, loss L, and mutual information M.b. Lupus Berevus, the only manufacturer of these gates in the world, happens to be dyslexic (that’show he came up with the gate to start with), and is unable to remember the rules for 01 and 10which he keeps on crossing while he constructs the gates. In average, about a 40% of the timethe output of 10 is changed by that of 01 and vice versa. In addition to that the gates are notprop e rly shielded from external currents and this affects the output for input 00 that ends upbeing interpreted as any other input with equal probability.Draw a process model diagram which models the c onfusing confusius gate as a proce ss. Includethe transition probabilities in your diagram.c. If the output is 1. . .i. What is the probability that it was produced by the input (0 1)?ii. What is the probability that it was produced by the input (1 0)?iii. What is the probability that it was produced by the input (1 1)?iv. What is the probability that it was produced by the input (0 0)?d. What are the input information I and the output information J (in the correct units)?1Problem Set 7 2e. What are the noise N, the loss L, and the mutual information M? Is this process noisy, lossy,both, or neither?f. Extra Credit: How useful is the comparison between J for the correct channel and J for thechannel with defects? What about the comparison between M for the two channels? In answeringthis question, you might consider thinking about which gate may be more useful in circuit design.Problem 2: And then came the humans, ...According to the latest archeological findings, about two hundred thousand years ago, two species of hominidsHomo Sapiens, and Homo neanderthalis, coexisted with the currently dominant Homo sapiens sapiens for aslong as one hundred thousand years. It has been debated what is the exact relationship between the threespecies in terms of evolution. In this problem set we will frame this debate as an information flow problem.Let us first focus on a hypothetical interbreeding between H. sapiens (which we abbreviate as S), and H.neanderthalis (which we abbreviate as N). For the moment we will ignore mutations leading to H. sapienssapiens. We will address this problem taking the mothers of each species as input. Therefore, we will havetwo possible values as input; either the mother is “S” and we label the input MSor she is “N” and we labelthe input MN. Assume a female population of 1000 N and 10000 S.In order to characterize the evolution process, we need to know the number of females that have children,and the species of the children. We do not really have observations from that time, so we will have to guess;the following assumptions (guesses) will help us characterize the system. Assume that females mate onlyonce. Typically females from one species will mate males from the same species. When that is the case,the females will always have children (labeled CSor CNaccording to the species of the parents). However,some interspecies mating occurs. Suppose 20% of N-females will mate S-males, and 10% of S-females willmate N-males. Fertility of interspecies couples is reduced; only 50% of them have children. C oncerning thespecies of the children of intersp e cies couples, 10% will be classified as CN, and the remaining 90% will beseen as CS.a. What is the probability that a randomly chosen mother is H. neanderthalis (P (MN))? (HINT:Only females with offspring are mothers!. You should get P (MN) = .0865)b. As an observer H. sapiens sapiens that has forgotten his glasses, you see a kid playing around butyour miopy does not let you appreciate to which s pec ies he belongs. What is your uncertainty(measured in bits up to two decimal places) about the spec ies of the mother?c. Model evolution as a nondeterministic process. (We will later refer to this model as “expectedevolution”). The mothers of each species are the input of the system, and their offspring are theoutput of the system. (This is a probability model, like the ones you have see n in class). Drawthe diagram of the probability model and compute its transition probabilities. (HINT: Two ofthe transition probabilities you should get are CSN= 1/10 and CN S= 0.0053)d. Compute P (CN) and P (CS).e. If you are told that the kid playing around appears to be S, what is your uncertainty about thespecies of the mother?f. What if you were told that the kid is N?g. You can set up an inference machine (one that tells you what is the probability of the motherbeing S or N given the offspring’s species.) Present this machine in the form of a probabilitymodel diagram like the ones discussed in class.Problem Set 7 3Now, you will complete the model of evolution by introducing mutations, so that the model also includesH. sapiens sapiens (which we abbreviate as H). We will do so by introducing a second process that we willcall “Mutation”. The input of the mutation process is the output (CN, CS) of the “expected evolution”process that you defined in part c; the output of the mutation process is the actual result of evolution oncemutation is taken into account. Denote the outputs of the process of mutation as JN, JS, JH.10Assume that H. sapiens sapiens are mutants of H. sapiens, and that mutations occur 1% of the time.h. Characterize the probability model of the process of mutation the same way you did for the modelof “expected evolution”.i. You