Information Theory Inference – David J C MacKay (1)

Fitness as a function of time. The genome size is G = 1000. The dots show the fitness of six randomly selected individuals from the birth population at each generation. The initial population of N = 1000 had randomly generated genomes with f(0) = 0.5 (exactly). (a) Variation produced by sex alone. Line shows theoretical curve (19.14) for infinite homogeneous population. (b,c) Variation produced by mutation, with and without sex, when the mutation rate is mG = 0.25 (b) or 6 (c) bits per genome.

The dashed line shows the curve (19.12). mG 0.65 0.7 0.75 0.8 0.85 0.9 0.95 with sex without sex 0.65 0.7 0.75 0.8 0.85 0.9 0.95 with sex without sex f f Figure 19.4. Maximal tolerable mutation rate, shown as number of errors per genome (mG), versus normalized fitness f = F/G. Left panel: genome size G = 1000; right: G = 100 000. Independent of genome size, a parthenogenetic species (no sex) can tolerate only of order 1 error per genome per generation; a species that uses recombination (sex) can tolerate far greater mutation rates.

Exercise 19.1.[3, p.280] Dependence on population size. How do the results for a sexual population depend on the population size? We anticipate that there is a minimum population size above which the theory of sex is accurate. How is that minimum population size related to G? Exercise 19.2.[3] Dependence on crossover mechanism. In the simple model of sex, each bit is taken at random from one of the two parents, that is, we allow crossovers to occur with probability 50% between any two adjacent nucleotides.

How is the model affected (a) if the crossover probability is smaller? (b) if crossovers occur exclusively at hot-spots located every d bits along the genome? 19.3 The maximal tolerable mutation rate What if we combine the two models of variation? What is the maximum mutation rate that can be tolerated by a species that has sex? The rate of increase of fitness is given by df dt ≃−2m δf + η √ r m + f(1 −f)/2 , (19.15) 19 — Why have Sex?

Information Acquisition and Evolution which is positive if the mutation rate satisfies m < η r f(1 −f) . (19.16) Let us compare this rate with the result in the absence of sex, which, from equation (19.8), is that the maximum tolerable mutation rate is m < 1 (2 δf)2 . (19.17) The tolerable mutation rate with sex is of order √ G times greater than that without sex!

A parthenogenetic (non-sexual) species could try to wriggle out of this bound on its mutation rate by increasing its litter sizes.

c⃝1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 c⃝Cambridge University Press 2003 Version 7.2 (fourth printing) March 28, 2005 Please send feedback on this book via http://www.inference.phy.cam.ac.uk/mackay/itila/ Version 6.0 of this book was published by C.U.P. in September 2003. It will remain viewable on-screen on the above website, in postscript, djvu, and pdf formats.

In the second printing (version 6.6) minor typos were corrected, and the book design was slightly altered to modify the placement of section numbers. In the third printing (version 7.0) minor typos were corrected, and chapter 8 was renamed ‘Dependent random variables’ (instead of ‘Correlated’). In the fourth printing (version 7.2) minor typos were corrected. (C.U.P. replace this page with their own page ii.) Contents Preface . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . v 1 Introduction to Information Theory . . . . . . . . . . . . . 3 2 Probability, Entropy, and Inference . . . . . . . . . . . . . . 22 3 More about Inference .

. . . . . . . . . . . . . . . . . . . . 48 I Data Compression . . . . . . . . . . . . . . . . . . . . . . 65 4 The Source Coding Theorem . . . . . . . . . . . . . . . . . 67 5 Symbol Codes . . . . . . . . . . . . .

. . . . . . . . . . . . 91 6 Stream Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 110 7 Codes for Integers .

. . . . . . . . . . . . . . . . . . . . . . 132 II Noisy-Channel Coding . . . . . . . . . . . . . . . . . . . . 137 8 Dependent Random Variables .

. . . . . . . . . . . . .

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: 7e731f15577f27e3
• File Extension: .pdf
• File Size: 6,462,661 bytes (6.163 MB)
• Title: –
• Author: Unknown
• ISBN: 0123456789
• Pages: 643
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 1452.0 minutes
• Total Words: 290,400
• Total Characters: 1,594,563
• Average Words per Page: 451.63
• Average Characters per Page: 2479.88

Most Frequent Words

probability (1317), code (1070), one (949), codes (894), two (869), distribution (845), function (784), bits (672), exercise (664), number (659), channel (628), data (620), model (516), information (515), given (508), log (490), example (484), random (469), algorithm (464), figure (460), figure (455), binary (427), gaussian (412), error (405), set (403), using (358), state (355), method (353), source (343), rate (335), sampling (334), value (329), length (323), bit (312), matrix (309), entropy (304), mean (302), theory (300), first (293), use (289), problem (286), inference (285), shown (285), methods (280), decoding (280), likelihood (278), also (266), time (265), between (254), coding (251), make (244), energy (243), chapter (242), linear (239), monte (238), carlo (238), posterior (235), models (234), case (232), solution (231), three (231), prior (229), optimal (227), sum (225), see (224), vector (223), possible (223), density (222), large (221), parameters (221), now (217), probabilities (217), network (216), bayesian (214), noise (213), show (212), find (210), maximum (208), point (208), input (208), variables (207), codeword (207), capacity (206), points (206), second (205), symbol (205), weight (202), parity-check (201), values (199), used (197), equal (197), exp (197), string (194), shows (192), samples (191), thus (188), functions (188), small (187), distributions (183), single (183).

PDF Download