Chapter 9Stirling’s ApproximationBinomial BoundsSlide 6The Gamma FunctionSlide 8N – Dimensional Euclidean SpaceSlide 10Interesting Facts about N-dimensional Euclidean SpaceSlide 12Chebyshev’s InequalityVarianceThe Law of Large NumbersSlide 16Chapter 9Mathematical PreliminariesStirling’s Approximation1log)log(logLet . log!log111nnnxxxxdxIknnnnkFig.9.2-1by trapezoid rulennI log21)1log(2log1log21 !!log1log21log nenennnnnnnntakeantilogsnennn2~!Fig.9.2-2by midpoint formulannI log21)1log(3log2log81 !!loglog21811log87nenennnnnnnntakeantilogs7.24.2 where!87eCeCnennnn9.2. . . .Binomial BoundsShow the volume of a sphere of radius λn in the n-dimensional unit hypercube is:)(22211)(nHnnnnnV  Assuming 0  λ  ½ (since the terms are reflected about n/2) the terms grow monotonically, and bounding the last by Stirling gives:' somefor 2)1()1(1)1()1(1)()()!()!(!)(2111)()1(12CnCnCnnnCeeennnCnnennCnenCnennnnnnnnHnnnnnnnnnnnnnnnnnnn    9.3).()1log()1(log)1(log1H)()(0)(002222 as 1211212,211111-1 So rms).between te ratios actual (the 112232111 ratioswith series geometric aby termwise111 boundnHnHkknHnkkknnCnCknnnnnnnnnnnnnnn   nknnHnnkknkn012022 2~2129.3N.b.The Gamma FunctionIdea: extend the factorial to non-integral arguments..)(Let 01 dxxennxby conventionFor n > 1, integrate by parts: dg = e−xdx f = xn−10201)1(1)( dxxenexnnxxn1)1()1()1()(00xxedxennn)!1()(!3)4(!2)3(1)2(  nn9.4  dxdyedyedxedtedtetdttedxxeyxyxttttxx222222222121integral)error the(called2212100021020 02222rredrdre21dxdyarea = dxdy9.4rdr rdθarea = rdrdθN – Dimensional Euclidean SpaceUse Pythagorean distance to define spheres:rxxn221Consequently, their volume depends proportionally on rn342)(321 CCCrCrVnnnniixntnndxedtei122221converting to polar coordinates9.5  010122221)(drnreCdrdrrdVedxdxenrnnrnxxn 122220121022121nCnnCdttenCdrdttteCnnntntnnn22212nnnCnnCjust verifyby substitutionr2  t9.5nCn1 22.00000 2 π3.14159 3 4π/34.18879 4 π2/34.93420 5 8π2/155.26379 6 π3/65.16771 7 16π3/1054.72477 8 π4/244.05871   2k πk/k! → 0From table on page 177 of book.Interesting Facts aboutN-dimensional Euclidean SpaceCn → 0 as n → ∞ Vn(r) → 0 as n → ∞ for a fixed rVolume approaches 0 as the dimension increases! nrrCrCrCrVrVnnnnnnnnn as111)()()(Almost all the volume is near the surface (as n → ∞)end of 9.5What about the angle between random vectors, x and y, of the form (±1, ±1, …, ±1)? 0)1()1)(1( vectorsrandomddistributeuniformlyfor 1products randomuniform 1  nnnnknkHence, for large n, there are almost 2n random diagonal lines which are almost perpendicular to each other!end of 9.8yxyxcosBy definition:n1cos length of projection along axislength of entire vectorFor large n, the diagonal line is almost perpendicular to each axis!Angle between the vector (1, 1, …, 1) and each coordinate axis:As n → ∞: cos θ → 0,  θ → π/2.Chebyshev’s InequalityLet X be a discrete or continuous random variable with p(xi) = the probability that X = xi. The mean square is  ||)()()()(222222XPdxxpdxxpxdxxpxxpxXExxiii  22||XEXP  x2 × p(x) ≥ 0Chebyshev’s inequality9.7VarianceThe variance of X is the mean square about the mean value of X, adxxpxXE )(So variance, (via linearity) is:          .2)(22222222XEXEaXEaaXEaXEaXEXV9.7Note: V{1} = 0 → V {c} = 0 & V{c X } = c²V{X}The Law of Large NumbersSuppose X and Y are independent random variables, with E{X} = a, E{Y} = b, V{X} = σ2, V{Y} = τ2.Then E{(X − a) ∙ (Y − b)} = E{X − a} ∙ E{Y − b} = 0 ∙ 0 = 0And V{X + Y} = E{(X − a + Y − b)2} = E{(X − a)2} + 2E{(X − a)(Y − b)} + E{(Y − b)2} = V{X} + V{Y} = σ2 + τ2because of independence9.8Consider n independent trials for X; called X1, …, Xn.The expectation of their average is (as expected!):    aXEnXEXEnXXEnn 11So, what is the probability that their average A is not close to the mean E{X} = a? Use Chebyshev’s inequality:    22222nAVaAEaAPLet n → ∞Weak Law of Large Numbers: The average of a large enough number of