163 163 155 8 2 Why divide and conquer works How does divide and conquer reasoning Chapter 1 produce such accurate estimates Alas this problem is hard to analyze directly because we do not know the accuracy in advance But we can analyze a related problem how divide and conquer reasoning increases our confidence in an estimate or more precisely decreases our uncertainty The telegraphic answer is that it works by subdividing a quantity about which we know little into several quantities about which we know more Even if we need many subdivisions before we reach reliable information the increased certainty outweighs the small penalty for combining many quantities To explain that telegraphic answer let s analyze in slow motion a short estimation problem using divide and conquer done 8 2 1 Area of a sheet of paper The slow motion problem is to estimate area of a sheet of A4 paper A4 is the standard sheet size in Europe On first thought even looking at a sheet I have little idea about its area On second thought I know something For example the area is more than 1 cm2 and less than 105 cm2 That wide range makes it hard to be wrong but is also too wide to be useful To narrow the range I ll drew a small square with an area of roughly 1 cm2 and guess how many squares fit on the sheet probably at least a few hundred and at most a few thousand Turning few into 3 I offer 300 cm2 to 3000 cm2 as a plausible range for the area Now let s use divide and conquer and get a more studied range Subdivide the area into the width and height about two quantities my knowledge is more precise than it is about area itself The extra precision has a general reason and a reason specific to this problem The general reason is that we have more experience with lengths than areas Which is the more familiar quantity your height or your cross sectional area Therefore our length estimates are usually more accurate than our area estimates The reason specific to this problem is that A4 paper is the European equivalent of standard American paper American paper is known to computers and laser printers as letter paper and known commonly in the United States as eight and a half by eleven inches In metric units those dimensions are 21 59 cm 27 94 cm If A4 paper were identical to letter paper I could now compute its exact area However A4 paper is I 163 2010 05 13 00 43 32 rev b667c9e4c1f1 163 164 164 156 remember from living in England slightly thinner and longer than letter paper I forget the exact differences between the dimensions of A4 and letter paper hence the remaining uncertainty I ll guess that the width lies in the range 19 21 cm and the length lies in the range 28 32 cm The next problem is to combine the plausible ranges for the height and width into the plausible range for the area A first guess because the area is the product of the width and height is to multiply the endpoints of the width and height ranges Amin 19 cm 28 cm 532 cm2 Amax 21 cm 32 cm 672 cm2 This method turns out to overestimate the range a mistake that I correct later but even the too large range spans only a factor of 1 26 whereas the starting range of 300 3000 cm2 spans a factor of 10 Divide and conquer has significantly narrowed the range by replacing quantities about which we have little knowledge such as the area with quantities about which we have more knowledge The second bonus which I now quantify correctly is that subdividing into many quantities carries only a small penalty smaller than suggested by naively multiplying endpoints The naive method overestimates the range because it assumes the worst To see how imagine an extreme case estimating a quantity that is the product of ten factors each that you know to within a factor of 2 in other words each plausible range is a factor of 4 Is your plausible range for the final quantity a factor of 410 106 That conclusion is terribly pessimistic A more likely result is that a few of the ten estimates will be too large and a few too small allow several errors to cancel To quantify and fix this pessimism I will explain plausible ranges using probabilities Probabilities are the tool for this purpose As discussed in Section 8 1 probabilities reflect incomplete knowledge they are not frequencies in a random experiment Jaynes s Probability Theory The Logic of Science 11 is a excellent book length discussion and application of this fundamental point To make a probabilistic description start with the proposition or hypothesis H The area of A4 lies in the range 300 3000 cm2 164 2010 05 13 00 43 32 rev b667c9e4c1f1 164 165 165 157 and information or evidence I What I know about the area before using divide and conquer Now I want to find the conditional probability P H I namely the probability of H given my knowledge before trying divide and conquer There is no known algorithm for computing a probability in such a complicated problem situation How for example does one represent my state of knowledge In these cases the best we can do is to introspect or in plain English to talk to our gut My gut is the organ with the most access to my intuitive knowledge and its incompleteness and it tells me that I would feel mild surprise but not shock if I learned that the true area lay outside the range 300 3000 cm2 The surprise suggests that P H I is larger than 1 2 The mildness of the surprise suggests that P H I is not much larger than 1 2 I ll quantify it as P H I 2 3 I would give 2 to 1 odds that the true area is within the plausible range Furthermore I ll use this probability or odds to define a plausible range It is the range for which I think 2 to 1 odds is fair I could have used a 1 to 1 odds range instead but the 2 to 1 odds range will later help give plausible ranges an intuitive interpretation as a region on a log normal distribution That interpretation will then help quantify how to combine plausible ranges For the moment I need only the idea that the plausible range contains roughly 2 3 of the probability With a further assumption of symmetry the plausible range 300 3000 cm2 represents the following probabilities P A 300 cm2 1 6 P 300 cm A 3000 cm2 2 3 P A 3000 cm2 1 6 Here is the corresponding picture with width proportional to probability p 1 6 A 300 cm2 p 2 3 p 1 6 300 3000 cm2 3000 cm2 For the height h and width w after doing divide and conquer and using the similarity between A4 and letter paper the …