Class Note for MATH 527A at UA
Popular in Course
Popular in Department
This 45 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 12 views.
Reviews for Class Note for MATH 527A at UA
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
SOME GEOMETRY IN HIGHDIMENSIONAL SPACES MATH 527A 1 INTRODUCTION Our geometric intuition is derived from three dimensional space Three coordinates suf ce Many objects of interest in analysis7 however7 require far more coordinates for a complete description For example7 a function f with domain 71 1 is de ned by in nitely many coordi nates77 ft7 one for each t 6 711 Or7 we could consider f as being determined by its Taylor series 220 ant when such a representation exists In that case7 the numbers 10 11702 could be thought of as coordinates Perhaps the association of Fourier coef cients there are countably many of them to a periodic function is familiar those are again coordinates of a sort Strange Things can happen in in nite dimensions One usually meets these7 gradually reluctantly7 in a course on Real Analysis or Func tional Analysis But in nite dimensional spaces need not always be completely mysterious sometimes one lucks out and can watch a coun terintuitive77 phenomenon developing in R for large n This might be of use in one of several ways perhaps the behavior for large but nite n is already useful7 or one can deduce an interesting statement about limH00 of something7 or a peculiarity of in nite dimensional spaces is illuminated I will describe some curious features of cubes and balls in R as n a 00 These illustrate a phenomenon called concentration of measure It will turn out that the important law of large numbers from probability theory is just one manifestation of high dimensional geometry Along the way7 we will meet some standard analysis techniques These may be familiar to varying degrees I think it could be useful for you to see how multidimensional integrals7 linear algebra7 estimates7 and asymptotics appear in the analysis of a concrete problem A num ber of these matters are relegated to appendices In the main part of the exposition7 I try to focus as much as possible on geometric phenomena it would be reasonable to read about those rst7 and only refer to an appendix for quick clari cation as needed Ultimately7 you should also understand the appendices 1 2 MAT H 52 7A 2 THE CUBE 21 Volume of the cube C s is the cube centered at the origin in R with sidelength 2s le7 C s 17n1 7s 3 dj 3 s for all j lts n dimensional volume is by de nition VolC s 2s gtlt 2s gtlt gtlt 2s 25 ntimes We have an obvious consequence Proposition 21 As 71 7 00 the volume of C slt tooolfsgt ahdltls always1fors A 5 tends to zero if NlH From now on7 One 2 will be my reference cube7 and I will simply write 0 So VolC 1 for all n Notice7 however7 that the point 7 is a vertex of the cube7 and it has distance 2 from the origin So Proposition 22 The cube 0 has diameter but volume 1 The mathematics is completely elementary7 but I hope you agree that visualizing such behavior is rather more tricky It gets worse 22 Concentration of volume I want to compare the volume of C to the volume of a subcube7 CW 7 5 where E E 01 is given We already know from Proposition 21 that the latter volume tends to zero as n 7 00 Hence the shell77 between the two cubes contains most of the volume Proposition 23 For every 6 E 01 e Volume of shell VolC 7 One 7 2 tends to 1 as n 7 00 In other words7 as n 7 007 there is no such thing as a thin shell of small volume All the volume of C escapes towards its surface7 out of any prescribed subcube In order to understand7 in some measure7 how the volume concen trates at the surface of C look again at 1 21 VolO 7 OWE 73 71717 6 Of course7 1 76 7 0 because 0 lt 176 lt1 Now invoke Lemma A1 lim 1 7 e 1 L700 n SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 3 This suggests that we should let the E in 21 vary with n Instead of taking a subcube C 7 whose sides are in xed ratio to the side length 1 of C we expand the subcube and shrink the shell as n increases In this way the volume trapped in the shrinking shell does have a nonzero limit Proposition 24 For every t gt 0 t t lim VolO i O 7 lim 17 1 i i 17 equot n 1 naoo 2 2n naoo It is understood that n must be large enough to ensure lt How to think about this Say you want to know what shell contains half the volume of C for large n of course Since 1 7 equot 5 for t 69315 you know that the cube of sidelength 17 has volume about i with the remaining volume contained in the very thin shell of width between the subcube and our reference cube 0 Later on we will look at the cube a bit differently and see that its volume also concentrates along the diagonal plane x1zn0 This will be related to probability theory First however we will study the ball it is more symmetrical than the cube and easier to deal with 23 Surface area of the cube ln dimensions 1 and 2 cubes are not cubes in the everyday sense of the word The cube 015 is a line segment of length 25 The cube 025 is a square sidelength 25 It has four 1 dimensional sides each of which is a copy of Cl The surface area of 025 is the total 1 dimensional volume in this case just ordinary length of the four sides to wit 4 gtlt 25 035 is the usual cube lts six 2 dimensional sides are copies of 025 and the surface area of 035 is the sum of the 2 dimensional volumes or the usual areas of its sides 6 gtlt 2s The cube 045 in four dimensions has a number of 3 dimensional sides Let7s call them 3 faees The surface area of 045 is really the sum of the 3 dimensional volumes of the 3 faces 8 gtlt 2s3 To see why this formula is correct we need to describe the 3 faces A 3 face is determined by setting one of the coordinates equal to its extreme value is and allowing the other coordinates to vary in 75 s For example 8796279637964 l ml S 8 for j 2374 is a 3 face It is a copy of the cube 035 95179527953 l l jl S 5f0rj17273 4 MAT H 52 7A except the indices have changed which is irrelevant This object has the 3 dimensional volume 253 There are eight 3 faces since any one of the four coordinates could be xed at 5 or 7s with the other three coordinates allowed to vary in 75 s The surface area of C s is the sum of the n 7 1 dimensional volumes of its 71 7 1 faces Area is not really a good term 1 but we will use it to distinguish between the n dimensional volume of the solid n dimensional object and the n 7 1 dimensional volume of the boundary of the object Later on the same convention will apply to the ball Emrcz39se 21 How many 71 7 1 faces does C 5 have How many 71 7 k dimensional faces for 0 S k S n A 0 face is a vertex and the n face by convention is the whole solid cube D Emrcz39se 22 For each s E 0 oo compare the behavior of the volume of C s to the behavior of its surface area as n 7 00 The case 5 should strike you as being counterintuitive D Emrcz39se 23 Fix 6 E 0 5 Let SE be the slice SE C s zl an12 l lt 6 ie a sort of equatorial slice of the cube How does the ratio VolSE VolC s behave as n 7 007 D 3 VOLUME OF THE BALL The material about concentration of volume comes at times verba tim from P Levy Probl mes concrete d analyse functionalle Gauthier Villars 1951 p209 ff See also pp 261 262 of the Math 527 notes for the computation of the volume of a ball in R 31 Volume of the ball part 1 We write B R for the solid ball radius R centered at the origin in R The term ball means surface plus interior The surface itself is called the sphere denoted by S 1R The superscript n 7 1 signi es that the sphere in R has dimension n 7 1 Thus B R 1n ER 1 3R S 1R 1n ER 1 R 1something like n 7 1dimensional Lebesgue measure might be preferred by cognoscenti SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 5 gt4 n d sm e cos 9 sin 9 1 e n71 IR FIGURE 1 Volume of ball by slices Example 31 To be clear about dimensions consider B41 1x23z4 l x 3 3 xi 3 1 C R4 This is 4 dimensional in the sense that as long as x x x lt 1 all four coordinates can be varied independently However 531 961796279637964 ix x3 xi 952 1 c R4 This is 3 dimensional in the sense that once three of the Q are xed the remaining one is largely determined up to i sign in this example There are better de nitions but this should convey the idea It is rather tricky to picture SS since we cant go into four dimensions but there are ways In any case this section deals with the ball only D Now let Kn be the volume of the unit ball B 1 in R Then the volume of B R is KnR Let us calculate Kn refer to Figure 1 The circle represents the ball of radius 1 The horizontal axis is Rn l the set of n 7 1 tuples 1 xn1 The vertical axis is the last direction x If we were computing the volume of the ball in R3 ie n 3 we would add up the volumes of circular slices of radius cos0 and thickness dsin 0 K32 7Tcos26dsin0 I 2 6 MAT H 52 7A Now this integrand 7TCOS2 6 is the two dimensional volume of the two dimensional ball disk of radius cos 6 Note that it has the form volume of two dimensional UNIT ball gtlt radius2 7T gtlt cos2 6 Using symmetry in 6 we may thus write 3 K3 2 Kgcos36d6 0 The pattern continues for n gt 3 I claim that xn sin 6 represented by a horizontal line segment in the gure intersects B 1 in an 7171 dimensional ball of radius cos 6 Indeed the intersection is de ned by iilsin26 1 31 gt x xiil 17sin26 cos62 and this is Bn 1cos 6 So instead of a very thin slice with a two dimensional disk as cross section we now have a very thin dsin 6 slice whose cross section is the ball of radius cos 6 in dimension n 71 Its volume is Kn1 cosn 16 gtlt dsin 6 Thus 32 K 22 Kn1 cosn6d6 21194 0 where 33 1 d f 2 cosn6d6 0 To make further progress towards a useful formula for Kn we need to understand the integral In 32 The integral In Here we collect information about In We re turn to the volume Kn in the next subsection Integration by parts in 33 gives for n gt 1 7r In sin6cosn71 6 n 712 cos 26sin2 6d6 0 n 7 1 2 cos 2 6 7 cos 6 d6 0 n 71In2 7 1 Hence 34 1 TIM SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 7 Since I0 g and I1 17 we can solve 34 recursively Starting with I07 we nd I27I47 7 and from I1 we get I37I57 The pattern is easy to ascertain 7T1 5 2p71 35 I 7 lt gt 217 2 2 4 6mm 24 62p 36 I 2P1 Remark 31 Standard notation 13 5 7 210 1 2p 1 D We will need to know how In behaves as n 7 00 Since the integrand cos 6 decreases with n for every 6 31 07 one expects that In 7 0 This is true7 but we want to know how fast the decrease is The next lemma provides the answer We use the notation an on to signify that limnH00 57 1 this would be a good time to glance at Appendix B Lemma 31 In N 1 l Zn39 Proof From 35 and 367 one sees that for all positive 717 7r Another proof nIn n 7 1In2 implies nInIn1 71 1In21n1 then writing 38 for with n replaced by n 7 171 7 27 7 we get the string of equalities nInIn71 71 1In711n72 71 2In721n73 39 39 39 1110 ma Here is the idea of the rest of the proof First we note that by 347 In N In2 Next we show that In1 is trapped between In and In2 lt will follow that In1 In7 so that 37 gives I Taking the square root will establish the Lemma Lets do it more carefully Because 0 S cos6 S 17 we have cos 6 lt cos 1 6 lt cosniz 6 for 6 E 07 g and thus In lt In1 lt In Divide by In and use 37 8 MAT H 52 7A Since the right side has limit 1 it follows that In lim 1 MK 1 1 Now multiply 37 by If and rearrange The right side has limit 1 hence so does the left side Now take the square root D Remark 32 Lemma 31 has a remarkable consequence Applied to n 2p 1 it says that 7139 lim 2p 1 12 1 7 pace 2 or in longhand 2242 2p2 1 7139 39 1 1733032522p7122p1 2 There is a dot dot dot77 notation that is used for in nite products analogous to the usual notation for in nite series here stands for a certain limit of partial products analogous to the familiar partial sums one would write 7T 224466 2 733557739 This is called Wallis product B Let us now look at fog cos 6d6 more closely The integrand is de creasing in 6 and for each 6 31 0 where its value is 1 it decreases to zero with 71 So the main contribution to the integral should come from a neighborhood of 6 0 Indeed if 04 gt 0 and 6 E 04 then cos6 lt cos Oz and so 2 7T cos 6d6 lt cos oz d6 7 7 04 cos a Dd DZ 2 Now cos oz approaches zero geometrically but we saw in Lemma 31 that In approaches zero only like n We are in the situation of the 2J1 Wallis Arithmetica in nitorum Oxford 1656 The product can be recast as Tlquot 4n24n2 7 By the way Wallis was a codebreaker for Oliver Cromwell and later chaplain to Charles 11 after the restoration SOME GEOMETRY 1N HIGHDIMENSIONAL SPACES 9 example in Appendix B geometric decrease beats power growth which gives 71005 a 0 1 ED cos 0dt970 We obtain Proposition 31 For every 04 E 0 g Inw cosn d 0 If however the limit of integration 04 is allowed to decrease as 71 increases one can trap a proper fraction of the the total value of In in the shrinking interval of integration Consider 3 W 1 9 t cosn d 7 cos 7 dt 0 W o W Frorn A 6 in Appendix A t d t2 d cos 7 t7 6 7 t 0 W 0 and we just saw that 7r In N 7 271 Thus 3 1 W 2 2 310 lirn 7 cosn d 6J7 dt n7ooIn 0 7T 0 Remark 33 By the time we get to 310 we no longer need 6 E 07r2 That restriction was used in the earlier observation that the integral over any nite subinterval 004 C 07r2 was asymptotically equivalent to In Once we go to the shrinking upper limit 04 then this upper limit will fall into 07r2 when n is large enough no matter the choice of B D 33 Volume of the ball part 2 We had obtained the relation 32 K 22 Kn1 cos t9dt9 21194 0 Replace n by n 7 1 to get le 2 1Kn4 and thus Kn 4InIn1Kn2 10 MATH 527A Now recalling 37 from the preceding subsection we obtain a recur sion relation from which Kn can be determined 2 311 K 5192 Knowing that K2 7139 and K3 go we nd K4 K6 and K5 K7 and recognize the pattern 7147 H 2 2 This formula has an amazing consequence 312 K2 313 K2p1 Proposition 32 For every R gt 0 the volume of the ball of radius R m R tends to zero as n a 00 Proof If n 2p is even for example the volume will be r132 K2 p Thus 2 2 R K217 R2p2 7T K217 R2177 p 2p 1 showing that the volume decreases rapidly once p becomes suf ciently large If you notice that the KZPRZP happen to be the coef cients in the Taylor series representation of em when x WRZ this argument should ring a bell The proof for odd dimensions is similar D As was seen in Proposition 21 the dependence of the volume of the cube C 5 on s and n is quite different There is another curious relation between cubes and balls that should be noticed The distance between the origin and the vertex 5 5 of C 5 is 5 Therefore the radius 5 n of the smallest ball containing C s tends to 00 with 71 Furthermore if s gt i then VolB s a 00 since the volume of the inscribed cube tends to in nity On the other hand the largest ball contained in C 5 will have radius 5 which is independent of 71 Even if VolC s a 00 the volume of this inscribed ball B 5 tends to zero It is tempting to extrapolate to in nite dimensions In R whatever that might mean a cube is not contained in any ball of nite radius The cube with sides of length 1 and volume 1 contains the unit ball which has volume 0 Well this last statement is mostly nonsense but somewhere in it there is a little truth SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 11 34 Asymptotic behavior of the volume The formula for Kn in volves factorials7 which are approximated by Stirling7s formula 0 27 k N 27rk kke k Proposition 33 M 27m M Proof Apply Stirling7s formula7 rst in even dimensions From 3127 VozBnRm N R 7T1 N 4273013176177 if we set p 712 and do some rearranging exercise7 we get 276 314 Kn N lt WWWW Multiplying this by radius VERY we get the desired formula The case of odd dimensions is something of a mess7 and there is a subtle point Begin by multiplying top and bottom of the expression 313 for K2171L by K21 2462p 2171017 and also multiply from the beginning by the factor that will come from VERY to get recall that n 2p 1 227Tp 2 20 2p 1 Next7 substitute for the two factorials from Stirling7s formula The terms are ordered so that certain combinations are easier to see 2 17 227rP 21 m 6 Lap 12p21 1 27T2p 1 6 21 21 12quot1 First some obvious algebraic simpli cations in the last expression 2p1 2 2p 1 up 10 0 22 P2PP1L 2 1 w e 2p12p1pp Moreover7 P 1 i 1 1 2101 2 12 2P1p and inserting this leads to My 1 315 K 2 2w Pepflii 2p17 2p1 2p11pp 12 MATH 527A Now we do asymptotic simpli cations as p a 00 The subtle point arises here Let RHS stand for the right side of 315 So far we know that 1 K2 1 316 l 717 1 pin RHS If we replace any part of RHS by an asymptotically equivalent expres sion7 obtaining a modi ed expression RHS77 say7 we will still have 1 K2 1 1 p 1 pin RHS7 For example7 lim 211 1 174100 W We can then modify 316 xE 11 K2p1 W 7 1m RHS 1 i 1 P m 7 xi This gives a new denominator7 and we get K lim 1 1H 22WPep1 m2p 1 2 which we would write more brie y as 1 1 317 2711 227Tp6p1772p 1 xE1p A comparison of 315 and 317 suggests that we have allowed p to tend to 00 in some places7 but not in others lsn7t this unethical No it is not7 as long as we are replacing one expression whose ratio with K2171L tends to 1 by another expression with the same property This same reasoning further allows us to substitute i for 5 1 2177 By now7 315 has been simpli ed to lt2 rgtpep 2p 1 39 and it is an easy manipulation to turn this into the desired formula in terms ofn2p1 D 318 SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 13 Corollary 31 0 39Rlt 1 lim VolltBnltR gtgt ifpf n 00 007 zf gtW Proof Write the asymptotic expression for the volume as V QWERZ M and recall that when 27TeR2 gt 17 the numerator grows much faster than the denominator The case S 1 is trivial D This is a little more like the behavior of the volume of the cube7 especially if you think not about the side length 25 of Cquots7 which remains xed7 but about the length 25 of its diagonal Cube diameter constant gtlt x Ball radius constant gtlt The behavior of the volume is determined by the value of the propor tionality constant Still7 there is no way to get a nonzero7 non in nite limiting volume for the ball 35 Volume concentration near the surface Consider the two concentric balls B 1 and B 1 7 6 The ratio of volumes is VolB 1 7 6 Kn1 7 6 V01B 1 T 1 E For every 6 this ratio tends to zero as n 7 007 which means that ev ery spherical shell7 no matter how thin7 will contain essentially the whole volume of B 1 Of course7 it should be remembered that lim VolB 1 07 so the shell also has a small volume7 it is just a signi cant fraction of the whole To see how the volume accumulates at the surface7 we again let 6 depend on 717 as we did for the cube Choosing E we nd that V01B 1 KnU t VolB 1T KL 1 tn 7 E 76 The interpretation is exactly as for the cube subsection 21 14 MATH 527A 36 Volume concentration near the equator for B R Recall that VolB R a 0 for every R We ask what fraction of this vanishing as n a 00 volume accumulates near the equator of the ball Let 91 lt 0 lt 02 and consider R f cos ads 1 0 92 319 1 1 7 cosnddd cosnddd Rn f2 91 0 1 2 The numerator is the volume of the slice bounded by the hyperplaness an Rsin 01 an Rsindg see Figure 1 Since the factor B has cancelled7 we will temporarily set R 1 and work with the unit ball later7 R will be re inserted by hand According to Proposition 317 the two integrals on the right side of 319 are each asymptotically equivalent to In Hence Proposition 34 For every 91 E 70 and 02 E 07 the fraction of the volume of B R contained in the equatorial slice between the hyperplanes an sint9L and an sindg tends to 1 as n a 00 If however 91 gt 0 61 lt 02 then the fraction of volume in the slice tends to zero As before7 to trap a proper fraction of the volume7 we must allow the limits of integration to approach 0 as n a 00 The results of Subsection 32 suggest that we take 91 and 02 61 lt g The signs of the 67s will not matter now7 only the fact that a 0 at a cleverly chosen rate Incidentally7 since sinu N u for u a 07 the bounding hyperplanes an sin are essentially an as n gets large From equation 3107 we now obtain Proposition 35 Let 61 lt g The fraction of the volume of B 1 contained in the slice bounded by the hyperplanes an sin7j 17 27 tends to l m t2 d 320 7 6 7 t x 27139 1 3a hypemlane in R is an n7 ldimensional set de ned by a single linear equation in 111 Inc If this set does not contain the origin7 it is sometimes called an a ne hyperplane7 but I won t make that distinction Hyper means one dimension down 7 in this context The set de ned by a single7 generally nonlinear7 equation fzl In 0 is a hypersurfacer The sphere S 1R is a hypersurface in Rut SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 15 Remark 34 Proposition 35 remains true if one asks about the volume between the hyperplanes an j 12 That volume differs from the volume in the proposition by and another similar integral7 but the limits of integration approach each other as n a 00 and the integral tends to zero The details are omitted D Remark 35 If you know some probability theory7 you will have noticed that 320 represents an area under the standard normal curve It is an often used fact that the value of 320 for 61 7196 52 196 is approximately 95 In other words7 for large n all but about 5 of the volume of B R will be found in the very thin slice between M iiooa E w Remark 36 By rotational symmetry7 Proposition 35 will hold for ev ery equator7 not just the one perpendicular to the xn direction THINK ABOUT THAT FOR A MINUTE Next incorporate this in your thoughts THE VOLUME ALSO CONCENTRATES NEAR THE SURFACE OF THE BALL D 37 Volume concentration near the equator for B Rn The results of the last subsection can be viewed from a slightly different angle7 which is important enough to be emphasized in its own little subsection Instead of xing R7 and looking at the fraction of volume contained in the slice between4 an and an one can let the radius of the ball become in nite at the rate RW and look at the slice between z 61 and an g Keep in mind that VolBRm a 0 or 007 so we may be talking about a fraction of a tiny volume or of a huge volume Proposition 36 Let 61 lt g The fraction ofthe volume ofB Rn contained in the slice bounded by the hyperplanes an 67j 127 tends to 1 m t2 d 321 7 677 t N27T 1 Ederez39se 31 Prove this proposition D 4it is simpler to use instead of sin 7L the two are asymptotically equivalent 16 MATH 527A 4 SURFACE AREA OF THE BALL 41 A formula for surface area Recall that the surface of a ball is a sphere We speak of the area of a sphere simply to distinguish that quantity from the volume of the whole ball But keep in mind Example 31 that the sphere 53R is itself 3 dimensional sitting in the 4 dimensional R4 What we refer to as its area is actually its 3 dimensi0nal volume Likewise7 the area of Sn 1R C R is understood to mean its 71 7 1 dimensional volume The surface area of B R is easily expressed in terms of VolB R Consider the n dimensional volume of the spherical shell between the balls of radii R SR and R VolB R 61 7 VolB R mm 6R 7 Rn KnnR 16R with denoting terms in 6R2 and higher Think of this volume as being approximately 41 volume of shell area of Sn 1R gtlt thickness 6B of shell7 ie volume of shell nKnR 1 gtlt 6R 41 becomes more accurate as SE a 0 Hence the area of S 1 is 42 V01B R nKan l This type of argument would indeed recover a formula which you know from calculus7 for the area of a region D on a surface in R3 given by z fzy D 1W dx dy But we will need to get at the area of the sphere by a different7 seem ingly more rigorous approach anyway Let Ln1 denote the surface area of the unit ball B 1 in R We know from general principles that the ball B R will have surface area Lwl gtlt Rn lg this will be used shortly Now refer to Figure 27 which again represents the unit ball B 1 in R If you are at all uneasy with the use of n in what follows7 work through the steps using 71 3 Recall from 31 that the line segment xn sin0 represents the ball Bn 1cos 0 as just remarked7 it will have surface area Ln2gtlt cos 97 2 This is n 7 2 dimensional volume The outside arc of the shaded area is the surface of a cylinder put together as follows the base is SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 17 FIGURE 2 Surface area by slices Bn 1cos t9 and the edge surface ofthe base is Sn 2cos t9 the height is d0 For small d67 the side of the cylinder is nearly perpendicular to the base7 and then the outside arc of the shaded region represents a contribution circurnference gtlt height Ln2cos 97 2 gtlt d0 to the total surface area Therefore 43 Ln1 2 Ln2cos 26d6 NHLH To obtain a formula for Lnil7 we can proceed in three ways First7 in the formula Lwl 71K 7 which is 42 at R 17 use the known expressions for Kn Second7 in 437 start with n 3 and L34 L1 27f7 and use the known expressions for In Third7 in 437 replace LWZ by 2 3Ln4 which is 43 after the replacement n 7 1 a n 7 27 to get 2 Lnil 4In721n73In73 7T Ln last ste b 37 n 7 2 3 p y Then use L1 27139 and L2 47139 to get started on a recursive deter mination of Ln1 li resurnably7 all these methods lead to the same answer 18 MATH 527A FIGURE 3 Volume vs surface area Proposition 41 2 p 1 L21 47139 7T 2p 7 1ll 7147 12171 27139 Remark It is worth understanding exactly why cos 6 becomes cosn z and not cos 1 0 which would be analogous to the change in the expo nent of R For the volume7 we had volume of base of slice x radius 1 which was then multiplied by thickness of slice dsin t9 cos 0d6 For the surface area7 it was surface area of base of slice olt radius 2 here the power does just drop by 17 but this was only multiplied by the arclength77 d0 So the difference is the bit of rectangle that sticks out beyond the circular arc in Figure 3 D Esercz39se 41 Compare the n a 00 behavior of the volume and surface area of B Rm for all R gt 0 One value of B should be peculiar D 42 Surface area concentration near the equator The surface area of B R concentrates near the or any equator The calculation has already been done Look at 319 If R is replaced by Rn l and cos 6 is replaced by cosn z 319 represents the fraction of surface area of B R contained between the hyperplanes xn sin 07 j 17 2 Everything we know about the n a 00 limits remains true7 word for word I will not restate the results7 you do it Esercz39se 42 State precisely the proposition about surface area con centration near the equator D SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 19 5 THE WEAK LAW OF LARGE NUMBERS In this section7 concentration of volume for the cube about its equa tor is shown to be an expression of one of the basic theorems of prob ability theory I will use several technical probability de nitions in an intuitive way otherwise7 there would be too many digressions 51 The probability setting Let 01 01 again be the interval 1 1 1 5 75 5 and consider the experiment of choosing a number at random from this interval All results are to be considered equally likely More precisely7 the probability that a randomly chosen number 1 falls into a subinterval db g 7 is de ned to be its length7 b 7 a We write Pz1 6 ab b 7 1 So P1 E 1 In a setup like this7 where the possible choices form a continuum7 the probability that a random 1 will be exactly equal to a given number is zero For example7 P1 0 0 A justi cation might be that you would never know 1 to all its decimal places More mathematically7 this is the only possible logical consequence of our starting de nition of the probability Pz1 E 07 0 0 7 0 0 Now we go to 0 unit side length7 remember7 and de ne the prob ability that a randomly chosen point lies in a region D g C to be the volume7 VolD Again7 the whole cube has probability 1 One can imagine picking x 17 7x as a whole 7 e g by throwing a dart into the n dimensional cube Or7and this is what I will do7one can build up the random x one coordinate at a time First choose 1 6 01 at random Then7 inde pendently of this rst choice7 pick 2 6 01 Continue The probability that an x built in such a way lies in D is again VolD This is not easy to prove with full mathematical rigor7 one essentially needs the theory of Lebesgue measure I will illustrate for the case n 2 and D a rectangle The key technical notion7 which cannot be avoided7 is independence SUMMARY An experiment with a number maybe in nite of possible outcomes is performed An event A is a subset of the set of possible out comes A probability measure assigns numbers between 0 and 1 to events The interpretation of PA p is that if the experimen is repeated a large number N times7 then about pN of the results will t the criteria de ning A Every single statement I just made requires clari cation and much more mathematical precision Example 51 Suppose a 6 sided die is tossed 607 000 times Let A 27 4 or 6 shows 7 and B 1 37 4 or 6 shows 20 MATH 527A Assuming that each of the six outcomes 1 23 456 is equally likely we have PA and PB This means intuitively that A should happen on about half or 30 000 of the tosses Of these 30 000 about one third each will result in in 246 so B happens on 23 or 20000 tosses Tosses resulting in 1 or 3 are no longer possible since we are restricting attention to outcomes where A has occurred In other words the probability of B was at the outset and it was still g after the results were restricted to the outcomes 2 4 6 in A One says 51 the probability of B given A the probability of B We cannot make a better prediction about the occurrence of B amongst the outcomes satisfying A than we could about the occurrence of B amongst all possible outcomes D Example 52 Suppose now B is 13 or 5 shows Then none of the 30 000 tosses tting the description of A will t the description of B Thus the probability of B given A 0 If we know that A has occurred we know with certainty that B has not occurred D We consider the A and B in Example 51 to be independent Exam ple 52 illustrates an extreme case of non independence Another extreme case would be B 1 2 4 or 6 shows If we know that A has happened it is certain that B has also happened or the probability of B given A 1 The technical meaning of independence is a rephrasing of 51 52 PA and B both happen PAPB To understand this rewrite it as if PA 344 0 PA and B both happen PM The left side is the fraction of the outcomes satisfying A for which B also happens In the setting of Example 51 it would be 20 000 7 x 60000 7 2 7 77PB 30000 60000 3 H 53 PB Example 53 We will pick a point x 6 02 at random by choosing its two coordinates independently Let A1 be the event 1 6 a1b1 and let A2 be the event 2 6 a2b2 We have PA1 b1 7 a1 PA2 b2ia2 The choices ofxl and p2 are to be made independently This means that we require that Plt1 E 01b1 and 2 6 02132 b2 7 12b1 7 11 SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 21 But this is the same as saying that Px 12 E rectangle with base a1b1 and height a2b2 Volrectangle The general statement Px 6 D VolD is deduced by approxi mating the region D by a union of small rectangles compare the de nition of a multiple integral as limit of Riemann sums D Laws of large numbers give precise meaning to statements that some thing should happen on average For example if we choose randomly and independently a large number N of points in 01 7 say 11 a2 aN any positive 17 should sooner or later be nearly balanced by a negative one and the average 01020N N should be close to zero The larger N is the better the law of averages should apply and this ratio should be closer to zero Now as just explained these independently chosen 17 can be thought of as the coordinates of a randomly picked point a a1 aN in the high dimensional cube ON One version of the law of averages says that the volume of the region in ON where 54 is not close to zero becomes negligible as N a 00 In other words we have concentration of volume again Volltaa1aN EON H 54 W is 3mm 1 I now turn to the geometric problem and revert to my usual notation 1 xn E C The interest is in concentration of volume about the plane H0 1 xn 0 Notice that this plane has normal 111 and that the line along the normal is in fact the main diagonal of the cube passing through the corner The distance to the corner is We want to look at slices bounded by planes Hi7 1 in possibly 77 will depend on niwe shall see The honest approach would be to nd a nice more or less explicit formula for the volume of such an equatorial slice as there was for a ball and then to apply the geometric fact of concentration of volume to obtain a probabilistic application However I confused myself trying to nd a volume formula there are too many corners when you slice the cube by a plane H7 and I gave up The less satisfying approach is to prove the probabilistic result as it is done in probability texts using a simple inequality see 527 Notes p 386 and to reinterpret it in geometric language This is what I have to do 22 MATH 527A 52 The weak law of large numbers For x 1 J E 0 set SAX z1zn this is a function whose domain is the cube I will sometimes omit the argument x Further7 given 6 gt 07 de ne the equatorial slice77 55 SEXEO H IltE Theorem 51 Weak law of large numers For every 6 gt 0 lim V0l85 1 Equivalently Sn X n 56 lim Volx E C I I gt 6 0 VLHOO Remark 51 The weak law77 is really a much more general theorem I have stated it in the context of our cube example But the Q might also be chosen at random from the two element set 7117 with 1371 P1 These two numbers could signify tails77 and heads77 in a toss of a fair coin We would then be working with a discrete cube7 711 Theorem 51 gives one precise meaning to the law of averages for coin tosses there are7 on average7 about as many heads as there are tails D Remark 52 If there is a weak law7 there should be a strong law7 and there is It is set in the limiting cube7 C where now x 1727 is an oo tuple It says that those x for which i 1 N 57 l 0 lt gt N13 N occupy total volume 1 in C Evidently7 some more theory is needed here7 to give meaning to the notion of volume in C and to clarify the nature of possible sets of zero volume where the limit 57 fails to hold D The proof of Theorem 51 is based on a useful inequality7 which is stated here for the cube 0 although any region of integration could be used For typing convenience7 I use a single integral sign to stand for an n fold multiple integral7 and I abbreviate dzl dxn dnx d1d3 W C n SOME GEOMETRY TN HIGHDIMENSIONAL SPACES 23 Lemma 51 Chebyshev7s inequality Let F O a R be a function for which 02 dEf fFx2d x is nite For 6 gt 0 let A5 x E O l gt 6 Then U2 58 VolA5 lt Proof of lemma Since A5 g C FX2 d x 3 Fx2d x oz A o For x 6 A5 we have 62 lt FX27 so 62 d x lt FX2d x A5 A5 The left side is just 62 d x 62VolA5 A5 Combine this string of inequalities to get 62 VolA5 lt oz7 as desired D Proof of Theorem We apply Chebyshev7s inequality to F Sn First7 we note that Sn2 i i 222 j1 i1 The integral over 0 of the double sum vanishes7 since in the iterated multiple integral7 1 E 1 2 A typical contribution from the simple sum is 1 1 1 2 2 2 2 2 1 d d dni i l i 2 2 2 Thus 7 24 MATH 527A Chebyshev7s inequality now gives Volxl lSnxl gt 5 lt Set 6 en in this relation7 and you get 59 Volxl ls xll gt 6 lt 1 127762 This tends to zero as n a 007 and the theorem is proved D 53 Connection with concentration of volume We have seen that the volume of the region g C where 57 lt 6 tends to 1 as n a 00 The geometric meaning of this fact still needs a little more clari cation To this end7 we switch to a coordinate system in which one direction is perpendicular to the planes H7 z1 xn 77 This new direction is analogous to the sn direction in our discussion of the ball Let e17 en be the standard basis7 ej00 1 00 739 place Thus7 x1einen Now let fn be the unit vector 1 17m71 el en in the direction normal to H0 The orthogonal complement to fn is of course the n 7 1 dimensional vector subspace H0XER lz1zn0 The process of Gram Schmidt orthogonaliztion in linear algebra guar antees that we can start with the unit vector fn7 and construct or thonormal vectors f17 fn1 which7 together with fn7 provide a new orthonormal basis of R These f are far from unique certainly one possible set can be written down7 but that would be more confusing than helpful The point is that a given x in the cube now has two coordinate expressions 161 l nen ylfl i i ynilfnil i SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 25 Take inner products of both sides with f7 and remember that the f are orthonormal You nd 1 1 510 yn WW1 39 n 7 ES Now go back to 59 Inserting 5107 we convert it into 1 V 1 n gt lt 7 o M 1y 1 em 1W Finally7 notice that the corner of the cube7 where all aj corre sponds to yn We may therefore phrase the weak law of large numbers in more geometric language7 as follows Proposition 51 The diagonal of C has length The fraction of the unit volume of 0 contained in the slice SEW see 55 ap proaches 1 as n a 00 D In other words7 a slice SEW whose width is an arbitrarily small frac tion of the length of the diagonal of C will eventually enclose almost all the volume of 0 Remark 53 Recall that the volume of C also concentrates near the surface D Eaereise 51 Verify that one possible choice for the new basis vectors f isforj1n71 1 1 i j f xjj1 0quotquot 039 739 terms A APPENDIX COMPOUND INTEREST In the main part of these notes7 we need two facts First7 equation A 2 below7 which often arises in a discussion of compound interest in beginning calculus It is fairly easy to prove Second7 the rather more subtle formula A1 1 ntd r td d 0 cos tiO nLIEQCOS tiO e 2 t7 which is a consequence of A 2 and some other stuff The rst subsec tion explains the ideas7 and everything afterwards lls in the technical mathematical details There are lots of them7 because they will reap pear during the Math 527 year7 and you might as well get a brief 26 MATH 527A introduction The details could well detract from the important issues on rst reading Go through them later7 but do go through them A1 The ideas The rst result should be familiar Lemma A1 For every 1 E R A 2 lim 1 7 e a mace n I will actually require a consequence of a re nement of Lemma A1 This generalization of Lemma A1 says7 in a mathematically precise way7 that if bn a 07 then we still have abn A 3 lim 1 naoo r and that the approach to the limit is equally fast for all a in any xed nite interval 7AA Technical term the convergence is uniform The relevant application is this unexpected corollary Corollary A1 t i n 7 7 A 4 nlLIEOCOS e 2 Convergence is uniform on nite intervals in this sense given 6 gt 0 and E gt 0 there is an integer N gt 0 depending on B and E but not on t such that n gt N implies t 2 A 5 lcos 7 e t lt E for all t E 766 Although all this will be repeated7 let me reveal why A 4 should be true and why I want this uniform77 convergence From the Taylor series for cosu we have 1 17 2 cosu 2u 77 terms are just not there Then t n t2 cos 7 1 7 7 n lt W lt 2 which has limit e t22l But the are there7 in the guise of the correction term in Taylor7s formula So one encounters the more com plicated limit A 3 I will then want to conclude that L4 Suppose all the A gt 1 lttgtd d 6 im cos 7 t e 7 t a 0 W 0 SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 27 This seems plausible given A 4 but to argue rigorously one needs A 5 This says more than just that t t2 i n 7 7 cos e 2 for each individual t it says that the graph of cosn is arbitrarily 2 close to the graph of 6J7 over the whole interval 766 if only n is large enough But if the graphs are close on an interval then the integrals over that interval should also be close Which is what I want A2 Sequences of numbers First a review of some simple and likely familiar de nitions and facts about limits of sequences of num bers A continuous function F has this property often taken as de nition of continuity A 7 on 7 c gt Fcn 7 We will prove later that A 8 nln1 3 7 a n Taking F to be the exponential function exp 0 nln1 i and c a we then obtain from A 7 and A 8 that A 9 1 g expnln1 7 e which is one of our goals Recall the epsilon delta de nitions of continuity and the epsilon N77 de nition for limit of a sequence De nition A1 A function F R 7 R is continuous at c E R if for every 6 gt 0 there is a 66 ie depending in general on 6 such that lx 7 cl lt 66 irnplies 7 lt 6 D De nition A2 A sequence onf 1 converges to c as n 7 00 if for every 6 gt 0 there is an integer Ne gt 0 ie depending in general on 6 such that n gt Ne irnplies lcn 7 cl lt 6 28 MATH 527A Example A1 Claim If F is continuous at c and 0 7 c then Fc 7 We need to show that given 6 gt 0 there is an NE gt 0 such that n gt Ne implies 7 lt 6 So let 6 gt 0 be given According to De nition A1 we are guaranteed a 66 so that lx 7 cl lt 66 implies 7 lt 6 Now use De nition A2 of convergence but substitute our 6 for the E in the de nition There is an N6 gt 0 such that n gt N6 implies 10 7 cl lt 6 this N depends on 6 and through 6 also on 6 The implications n gt N66 gt lcn7cl lt 6gt 7Fcl lt E establish the claim D A3 Sequences of functions So much for sequences of numbers and how they behave when plugged into a continuous function how ever we will need to work with sequences of functions The best way to see why we will worry about seemingly obvious details is to meet an example where things go wrong Incidentally I started to use the somewhat unusual symbol a77 for the argument of my functions because at certain points it seemed that z would interfere with my notation 1 xn for points in R I hope no offense is taken Example A2 Consider the sequence of functions fna nza 1 7 a de ned for 0 S a S 1 Clearly fn0 fn1 0 for all n and when 6 01 fna 7 0 by the geometric decay beats power growth77 principle see the beginning of Appendix B if you are not sure what I mean The maximum of fn is assumed at a n n17 n 7 2 n n 1 7 1 n f n1 n n1 n1 n 71nn139 and the value there is Using n 1 we see that the maximum value tends to in nity In fact 1 n1 in gt ltngt 7e maxfn 71 ne which is abbreviated max fn g in Appendix B SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 29 The most striking Bad Behavior is seen when the fn are integrated between 0 and 1 We have 7 7 7 a 1 n 1 n 2 A mn w mna nnmm Even though fna a 0 for every 1 the integrals of the fn do not approach zero We express this by saying that the identity 1 1 n2 1 1 A 10 lirn fna da lirn fna da 0 naoo 0 naoo does not hold But if you look back at A 4 and A 1 you see that this is emaetly what we wanted to claim ha mmhaf One can begin to see what goes wrong in this example by graphing fna nza 1 7 a for a few values of n It is evident from Figure 4 that although fna a 0 for any given x the graphs of fn are never close to the graph of the limit function fa E 0 over the whole interval 01 A signi cant amount of area rnigrates towards a 1 which is possible because the fn graphs become very tall D The epsilon N77 de nition of A 11 the graphs of fn are close to the graph of lirn fn over the whole interval77 goes as follows De nition A3 A sequence of functions fnf 1 converges uniformly to the function f on the interval 7AA if for each 6 gt 0 there is an NE generally depending on E and A but independent of a 6 7A A such that n gt Ne irnplies lfna 7 fal lt 6 for all a E 7AA A 00 could occur or the interval might be replaced by one of the more general form 046 D Eat ample A3 The functions fn frorn Example A2 do not approach the identically zero function fa E 0 uniformly on 01 It is pretty easy to see that the verbal description A 11 is violated but perhaps less clear how to deal with the 67s and N7s If we want to show that the criterion of the de nition is not satis ed we must show that its negation holds 30 MAT H 52 7A ynquot2a n1a for n1020304050 20 09 FIGURE 4 f a 0 but ff 9 0 there exists 6 gt 0 such that for all N gt 0 there exist 71 gt N and 1 6 01 such that fn a 7 fa gt 6 ASIDE The situation is relatively simple here While negating more in volved statements could later in the course be more tricky So a brief elaboration might be warranted The de nition has the logical structure VG Namely for all e gt 0 blah where blah there exists N such that bleh where bleh for all n gt N and a 6 01 bleugh where bleugh fna 7 fa lt e To negate the statement in layers so to say 0 The negation of for all e gt 0 blah77 is there exists 6 gt 0 such that not blah o The negation of blah is there is no N such that bleh77 or for all N not bleh o The negation of bleh is there are n gt N and a 6 01 such that not bleugh o The negation of bleugh is fna 7 fa gt e SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 31 Putting it together there exists 6 gt 0 such that for all N gt 0 there exist 71 gt N and a 6 01 such that fna 7 fa gt e as stated above Take 6 I First choose N0 so that n L L 7 gt 2 h gt N maxf fn1 wenn 0 we know this is possible since maxf 71 716 Now given any N gt 0 choose any n gt maxN N0 and take a Then L n139 lfna fa l lfna 0l gt 2 gt1 6 Observe that I needed just one 6 for which something bad hap pened there exists an E gt 0 In such a situation you will generally pick a numerical value here I took 6 I but could as well have chosen 6 106 or 10 6 To verify that the criterion in the de nition does hold you need to establish something for every 6 and you can never do so by choosing your favorite small explicit number D Example AA Now x a number A 6 01 The functions fn from Ex ample A2 in fact d0 converge uniformly to the identically zero function on 0 A Again this should be clear from the graphs What kept them from converging uniformly on all of 01 was the growing maximum that migrated towards a I But now this maximum will eventually be outside 0A somewhere in the interval A 1 near a I and the graphs over 0A will be close to zero Of cially let 6 gt 0 be given We have for 0 S a S A fna S nza l a S nZA 1 A lt 2712A the triangle inequality 1 7 a S 1 a was used as well as A lt I At this point I assume rather than prove that 2712A 7 0 for A 6 01 geometric decay beats power growth Thus there is an NE A depending on E and A such that n gt NEA implies 2n2A lt 6 QED The reason this does not lead to uniform convergence over all of 0 I is that NEA keeps growing as A gets closer to I In other words you have to let 71 get bigger and bigger before 2n2A lt E kicks in D Emrcz39se Al De ne fna na l 7 a on 01 and as above let fa E 0 Does fn 7 f uniformly on 01 Does 01fnada 7 01fada 0 32 MAT H 52 7A Discuss D This next proposition is one of our goals5 Proposition A1 Suppose fn a f uniformly on the nite interval 046 Then fna da a fa da Proof Let E gt 0 be given We have 19 19 Ma dai fa da fnafa da lfnafal da By uniform convergence7 there is an N gt 0 such that WW fal lt a 16 046 9 6 alfnafaldalt iadae as desired D So Emercz39se A2 The proof used the inequality S f Why is this true Emercz39se A3 The integration interval has to be nite for this particular proof to make sense7 since you need 6 7 oz to be a nite number In fact7 the proposition is no longer true on an in nite integration interval Let 1 7 forn a 2n7 lm n 0 otherwise 7 Then fn a 0 uniformly on all of R while fnada1foralln123 D There is one nal uniform convergence issue Earlier7 we had on a c and concluded that F continuous Fcn a Now7 if fn a f uniformly7 does F o fn a F o f uniformly F o f is the composition7 Ffa7 51f you know that the integral may not be de ned for some wild functionsil am not worrying about this Our functions are nice SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 33 It is really tedious to write down the full statement so let me just indicate the idea Suppose the Mean Value Theorem applies to F and that lF cl lt some K on a big interval Thus My FW FCy967 0r lFi FWN S Klyi l for some c E It follows that lFfna Ffal S KlMa fal and if n is large enough the right side will be as small as you please Of course one should worry about ranges and domains the argument that goes into F is the value that comes out of fn or f The details are left as exercise Proposition A2 Suppose the functions fn are continuous on 7A A or 046 more generally and that they converge uniformly to the con tinuous function f on that interval6 Suppose the range of the fn and f lies in some open subinterval of 700 Let F 700 a R be continuously di erentiable and suppose there is a number K such that lF cl lt K for c 6 700 Then Fo fn a Fo f uniformly on 7AA A4 Compound interest proofs Lemma A2 Fip A gt 0 Let bk be a sequence offunctions converg ing uniformly to zero on 7AA Then for every 6 gt 0 there is an integer N gt 0 depending on Abke such that n gt N implies 6a71abna 71 l lt 6 for all a E 7AA Instead of proving this Lemma all at once I will start with the simplest case and repeat the argument with small modi cations This is a bit tedious but conceivably the strategy can be helpful to you if you haven7t spent a lot of time with proofs Proof Let us rst prove Lemma A1 Assertion A 2 will follow from the relation obtained by taking logarithms A 12 lim nln1 2 a naoo n Recall the Taylor series for ln1 z valid for lt 1 x2 p3 1 1 i i n x x 2 3 6it turns out that such a limiting function f is automatically continuous 34 MAT H 52 7A We use this in the left side of A 3 a a a nln1ni pn 121 a a2 A 13 if 7 7 17121L3711L47121L We need to show that the error term pn can be made arbitrarily small by taking 71 large enough Caution the n77 is not the summation index You have a different series for each Estimate 1 a a2 5 t 27 t 4712 t lt1 E E triangle inequality 7 2 371 4712 A 14 1 g Z g3 decrease denominator This last series is the familiar geometric series7 Zrk with r in our case It converges when 0 lt r lt 17 and this will happen as soon as M lt1 Then the sum is 11 7 r n Now let 6 gt 0 be given Choose No it will depend on a and 6 so that n gt No implies M lt Then the geometric series converges7 and n moreover 1 7 lt 2 1 7 M V L The error term is then estimated by lt la 2 1 W p n 1 M n 39 V L Next7 choose N 2 N0 so that n gt N implies W2 2 lt 6 n For n gt N7 therefore7 lpnl lt 6 or llne 71n1 3m lt e n This is the translation of A 15 lim ln1 g 1115 1 naoo into of cial mathematics The desired A 2 now follows by taking exponentials7 see Example A1 SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 35 Next case So far7 a has been a single xed number lf7 however7 it is allowed to range over an interval 7AA we are asking about the convergence of fna nln1 to fa a The convergence is uniform To see this7 we replace the upper bounds in the proof just concluded by their largest possible value Take No it will depend on E and now on A so large that for n gt N07 1 17 A lt 2 the same as g lt Then 1 1 737Altz for lal SA 1 M 1 g Finally7 given 6 gt 07 choose N 2 N0 so that for n gt N A2 2 lt 6 n Then the error term from A 137 which is now written pna since a is no longer xed7 satis es 1 01 lt E71 A271 A2 p n 1 7 M Thus we have for all a E 7AAla7nln1 lt ewhen n gt N7 which is uniform convergence Applying Proposition A2 we conclude that 1 3 a e uniformly on A7Al Last case the general statement Instead of A 137 we have PM abna 121 an 12 A46 11 bn 4747 lt gtnnlt n gt M ltagtnlt23n4n2 gt where an is used as abbreviation for a bna in the sum Choose 0 lt E lt 1 If we can make something less than any such 6 we can obviously make it less than big 67s Because bn a 0 uniformly7 there is an No such that n gt No implies lbnal lt 5 lt 1 for all a 6 7A A the reason for 62 becomes clear shortly For such 717 we have lanl labnal S 101 lbnal lt 101 1 S A1 36 MAT H 52 7A Next take N 2 N0 so that simultaneously 1 71 7 E lt 2 and 2 2A 1 lt E n 2 when n gt N Just as before 6 lpnal lt 5 One arrives at a bna n1nlt1 T a Ma ma where e lpnal lt E for all a E 7AA and n gt N Therefore a bna E 6 la in1nlt1 TM lt lpnal lbnal lt 5 5 6 Another application of Proposition A2 proves Lemma A2 in full glory D AS The corollary It is now time to prove Corollary A1 Recall Taylor7s formula with remainder also called Lagrange7s formula or Lagrange7s remainder form A47 u W f 0u you gmw rWM c is some number known to lie between 0 and u Applied to cos this gives 1 1 cosu 17 E112 cosc U4 Set u i t t2 1 t4 A 18 cos 17 g cos Here 0 will lie between 0 and and will depend on t and 71 Writing the right side of A 18 in the form 7192 124cos ct4n 1 71 SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 37 we see that we can identify 7t22 with a and 124 cos c t4n with bna in Lemma A2 Since ltl S B and lcoscl S 1 it is also true that 134 1124cosct4nl m from which it is clear that bn a 0 uniformly on 76 6 Thus Lemma A2 applies and we have proved the corollary Primarily we wanted the limiting relation A 6 for the integrals This immediately follows from Proposition A1 B APPENDIX ASYMPTOTIC EQUIVALENCE Here is an example Let r 6 01 and p gt 0 be xed We know that as n a 00 both 7quot and 71 tend to zero Do they approach zero at the same rate One way to see that the answer is no77 is to look at the ratio Tn 7 npr nil This has limit zero7 On the other hand nip and V712 n 5 tend to zero at the same rate since 71 xn2n5pi 1 1 5 V712 n 5 P T which has limit 1 This leads to a de nition 7 mp 71 Jrn7127 De nition B1 If an bn are two sequences for which 13 1 lim 7 1 we say that the sequences are asymptotically equivalent and write B 2 an N bn as n a 00 usually left unsaid D In the examples above the two sequences both had limit zero They might just as well both tend to in nity in which case the statement B 2 would mean that they grow at the same rate The same notation 7The logarithm of the right side is plnn nln Ti Recall that n increases much faster than ln n so the n lnT dominates and it tends to fool So the log of the right side tends to 700 and the right side tends to zero Calculus students learn that geometric decay beats power growthlli 38 MAT H 52 7A is applied to functions if fxgx a 0 or fx gx a 00 as x a A A could be nite or ioo and 13 3 lim 1 weA 996 we write f N g as x a A Here we usually insert as x a A since z might be asked to ap proach any one of many possible values A In the case of sequences the subscript n has to go to 00 unless n a foo so it is hardly ever necessary to mention the fate of 71 Remark B1 If an and bn both have the same nite nonzero limit L as n a 00 relation B l is automatic and contains no information What might be useful is a comparison of the rate of approach to the limit ie consideration of the ratio aniL bniL D Remark B2 The concept of asymptotic equivalence as de ned above is only the most restrictive of a number of related and important notions One might wonder when the ratios in B 2 or B 3 remain boundediin that case the sequences or functions are comparable in a weaker sense This is written f 09 read f is big Oh of 9 Or one might want the ratio to approach zero signifying that the numerator decays more rapidly than the denominator Written f 09 f is little oh of 9 For example the assertion em1z0 aszaO means that the error term in the approximation of em by 1 z tends to zero faster than a for small x We will not need these variants but they are constantly used in applied analysis D C APPENDIX STIRLING7S FORMULA 01 The formula It is dif cult to get a handle on the growth of n as 71 increases For example 90 148 gtlt 10138 100 932 gtlt 10157 my computer calculated Zfo ln k and then exponentiated ls there a pattern In probability theory one asks about the binomial coef cient C 1 2n w n 717 SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 39 which counts the number of outcomes of the experiment of tossing a coin 271 times in which exactly 71 heads and7 of course7 also exactly 71 tails occurs How big is 0 1 One must replace the factorials by something manageable7 and Stirling7s formula provides the tool proof below Proposition C1 0 2 71 27m 71 It is important to understand what 0 2 does claim7 and what it does not claim According to our de nition of 77 7 n l1m 1 H00 27m nne It is not true that the dz erence 17117 27m nneinl is at all small What is small is the relative error7 since 1711 7 x27Tn n e l 27T71 71 lim V limll7 lll7ll0 naoo 71 Waco 71 A table will illustrate this n 5 10 25 711 120 3628800 1551 X 1025 Stirling 11802 3598695 1546 X 1025 Ratio 10168 10084 10033 Rel Error 0168 0084 0033 Difference 198 30104 5162 gtlt 1022 Remark 01 Stirling7s formula 0 2 can be improved It is possible to show that 1 1 2 1 7 7 0 3 n 7m 6 12m 288712 n 1 using the big Oh77 notation from Remark B2 Thus 071 3 stands for numbers Tn satisfying Tn mm lt an 7 oo for some xed but perhaps unknown number 0 The Tn7s are there fore smallish7 but notice that they are multiplied by the huge prefactor outside the Big Oh can be further replaced by 071 47 etc ad nauseum Math 583 deals with techniques for obtaining as ymptotic expansions77 like this D 8 2 2 2 is also the coef cient of I in the Taylor series of 1x1 7 z 40 MAT H 52 7A Example 01 To illustrate Stirling7s formula let us nd the asymptotic form of the binomial coef cient 0 1 G 3 2n 27T2n 2712 e 2 i 22 DZ V 27m une 2 7m This applies in probability theory as follows There are altogether 22 outcomes ofthe experiment of tossing a coin 271 times ie 22 different sequences of H77 and T77 heads or tails If the coin is fair each sequence has probability 122 Therefore the probability of getting exactly 71 heads is 1 2n 1 WW Eg the probability of getting exactly 500 heads in 1000 tosses is about 110007T N 000318 Not likely So the question arises what is the law of averages precisely One version of it illustrating high dimensional geometry is presented in Section 5 see Remark 51 D Emereise 01 Use Lemma 31 to derive the asymptotic approximation in 0 3 thereby circumventing Stirling7s formula D 02 Proof of Stirlingls formula This subsection is tacked on only because a proof of this useful formula is rarely encountered except perhaps in a more advanced course that includes asymptotic methods One standard approach is via the P fu CthTlg PzdEf twile tdt 0 One shows using integration by parts that Pn 1 n1 for n 0 12 On the other hand there are techniques for approximating integrals like this one for large values of x and those yield Stirling7s formula as well as the improvements in Remark 01 There is how ever an elementary proof as well elementary 31 easy which relies on something called the Euler summation formula and Wallis7 product 39 I follow K Knopp Theory arid Application of In nite Series 64 We want to prove that lim 71 1 H00 27m nne 7 or the equivalent statement for the logarithms TLHOO 0 4 limZlnk7ln27T7nlnnn0 k1 9527 Notes pp 262263 SOME GEOMETRY 1N HIGHDIMENSIONAL SPACES 41 The sum 2 ln k k1 is roughly comparable to n lndxxlnz7x nlnn7n1 1 1 We begin to see where Stirling might come from but evidently the approximation of sum by integral is too crude That is where Euler7s more re ned method comes in We need the greatest integer function de ned by n greatest integer S x Proposition C2 Euler summation formula Let f be continuously dz erentz39able on 1oo Abbreviate fk fk Then for n 12 05 1 flaw7ffltzgtdz ltf1fngtfltz7unproven Notice that the rst two terms on the right already give for f ln 1 1 nlnn7n1 0lnn n lnn7n1 Proof For k 12 n 71 we have by integration by parts 06 ml k1 A x 7 k 7 f dab 7 95 7 k 7 fz 1 7 A fx dab 1 k1 fk fk1 k 95 Since k S x S k 1 in the left side of 0 6 we may replace the k in the integrand by the fact that 31 k at the upper limit where z k 1 n does not affect the value of the integral Thus 1 1 k1 k1 fkfk1k fzdzk 7z7 f xdzk1n71 Summing these equations over k we get on the left side 1 1 1 1 1 f1f2 f2f339 fn71fn 7 f1f2f3 fn71 fm and on the right side 1n fzdz 7 7 f zdz 42 MAT H 52 7A x7x712 05 7 05 1 1 1 1 1 1 1 0 2 4 6 8 10 FIGURE 5 The function P1 in Euler7s formula Add f1 f to both sides to get Euler7s formula D Notice that P1z dEf z 7 7 is a periodic function period 1 with jump discontinuities at the integers Figure 5 We are about to integrate by part in the integral fPl f in Euler7s formula in preparation observe that P1 is the derivative of the periodic bounded function Figure 6 def 1 1 PM 7 5e 7 W 7 gm 7 z1 E P2 has corners at the integers as expected since P1 has jumps there Note also that 132k 112 for k 012 Lemma C1 If f mists then 1 P1zf zdz 7 awm P2ltzgtf ltzgtdz Let us now set f lnx We already have gotten to n 1 C77 Zlnknlnnin yn k1 where by the lemma 13295 z Yn n n P 2W dx 1 1 2 SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 43 warmmr 5 xrx112 o 1 i o anWWWV 01 l l l l l l 70 05 FIGURE 6 Antiderivative of P1 The integral converges as n a 007 by comparison with The term before the integral is 1 1 1 1 0398 5 1271 12 T 712 We conclude that yn has a limit 7 as n a 00 The last step is to show that y ln The method strikes me as being exceedingly tricky You have to know what you are looking for7 or be very clever Go back to 397 22422p2 1 7T lim 7 pam3252m2p7122p1 2 or 2462 1 09 lim mi 3 pace35lt2pi1x72p1 2 We are about to work 7 into this 44 MATH 527A By 07 2 ln2 4 210 2 ln2p101 210ln2 2 ln101 2101n2 210 1 ln10 210 2 z from C77 210 1 ln210 210 ln2 27p Also7 3 ln210 1l 210 ln210 1 210 1 Y2p1 Subtract On the left side7 you get a difference of logs7 which is the log of the quotient 22422102 i 246210 1 12342101 T1352101210139 The expression on the right is rearranged a bit check it7 resulting in 1HM 1 2101ln1 1 13521012101 2101 1 Eln210 1 1 ln2 2 yp ygp1 Mov 1n210 1 to the left side where it produces a inside the log Now everything in sight has a limit The left side tends to ln V by 0 97 the term 1 2 1 l 1 ltp gtn 2p11 tends to 1 by the cornpund interest forrnula A 87 and 2 7mm 2777 v Here it is important to know that the sequence 7 has a lirnitthat was the reason for bringing in P2z Thus 7r ln11ln2 y7 y lH27T from which SOME GEOMETRY IN HIGHDIMENSIONAL SPACES 45 Remark 02 There is an improved77 Euler formula Namely7 one can continue with the integration by parts fl P12 W1 7 f m 1 1 1 n 7 ng PSfN 1 1 11 mw Psf l Psf 12 1 here 1 3 1 2 1 PM gm M 7 1m M Em M is the bounded periodic antiderivative of P2 In this way7 one gets the i term7 and subsequent terms7 in the improved Stirling formula 1 i 1 i i mentioned in Remark 01 You can see the m appearing in 0 8 B
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'