Slide 1Slide 2Binomial BoundsSlide 6Slide 7Slide 8N – Dimensional Euclidean SpaceSlide 10Interesting Facts about N-dimensional Euclidean SpaceSlide 12Slide 13VarianceThe Law of Large NumbersSlide 16Chapter 9Mathematical PreliminariesStirling’s ApproximationFig.9.2-1by trapezoid ruletakeantilogsFig.9.2-2by midpoint formulatakeantilogs9.2. . . .1log)log(logLet . log!log111nnnxxxxdxIknnnnknnI log21)1log(2log1log21 !!log1log21log nenennnnnnnnnennn2~!nnI log21)1log(3log2log81 !!loglog21811log87nenennnnnnnn7.24.2 where!87eCeCnennnnBinomial BoundsShow the volume of a sphere of radius λn in the n-dimensional unit hypercube is:Assuming 0 λ ½ (since the terms are reflected about n/2) the terms grow monotonically, and bounding the last by Stirling gives:9.3)(22211)(nHnnnnnV ' somefor 2)1()1(1)1()1(1)()()!()!(!)(2111)()1(12CnCnCnnnCeeennnCnnennCnenCnennnnnnnnHnnnnnnnnnnnnnnnnnnn ).()1log()1(log)1(log1H9.3N.b.)()(0)(002222 as 1211212,211111-1 So rms).between te ratios actual (the 112232111 ratioswith series geometric aby termwise111 boundnHnHkknHnkkknnCnCknnnnnnnnnnnnnnn nknnHnnkknkn012022 2~212The Gamma FunctionIdea: extend the factorial to non-integral arguments.by conventionFor n > 1, integrate by parts: dg = e−xdx f = xn−19.4.)(Let 01 dxxennx0201)1(1)( dxxenexnnxxn1)1()1()1()(00xxedxennn)!1()(!3)4(!2)3(1)2( nndxdyarea = dxdy9.4rdr rdθarea = rdrdθ dxdyedyedxedtedtetdttedxxeyxyxttttxx222222222121integral)error the(called2212100021020 02222rredrdre21N – Dimensional Euclidean SpaceUse Pythagorean distance to define spheres:Consequently, their volume depends proportionally on rnconverting to polar coordinates9.5rxxn221342)(321 CCCrCrVnnnniixntnndxedtei122221 010122221)(drnreCdrdrrdVedxdxenrnnrnxxnjust verifyby substitutionr2 t9.5nCn1 2 2.000002 π 3.141593 4π/3 4.188794 π2/2 4.934205 8π2/15 5.263796 π3/6 5.167717 16π3/105 4.724778 π4/24 4.05871… … …2k πk/k! → 0From table on page 177 of book. 122220121022121nCnnCdttenCdrdttteCnnntntnnn22212nnnCnnCInteresting Facts aboutN-dimensional Euclidean SpaceCn → 0 as n → ∞ Vn(r) → 0 as n → ∞ for a fixed rVolume approaches 0 as the dimension increases! Almost all the volume is near the surface (as n → ∞)end of 9.5nrrCrCrCrVrVnnnnnnnnn as111)()()(What about the angle between random vectors, x and y, of the form (±1, ±1, …, ±1)? Hence, for large n, there are almost 2n random diagonal lines which are almost perpendicular to each other!end of 9.8By definition: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.0)1()1)(1( vectorsrandomddistributeuniformlyfor 1products randomuniform 1 nnnnknkyxyxcosn1cos Chebyshev’s InequalityLet X be a discrete or continuous random variable with p(xi) = the probability that X = xi. The mean square is x2 × p(x) ≥ 0Chebyshev’s inequality9.7 ||)()()()(222222XPdxxpdxxpxdxxpxxpxXExxiii 22||XEXP VarianceThe variance of X is the mean square about the mean value of X,So variance, (via linearity) is: 9.7Note: V{1} = 0 → V{c} = 0 & V{cX} = c²V{X}Also: V{X − b} = V{X} adxxpxXE )( .2)(22222222XEXEaXEaaXEaXEaXEXVThe Law of Large NumbersLet X and Y be 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 = 0∙And V{X + Y} = V{X − a + Y − b} = 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:Let n → ∞Weak Law of Large Numbers: The average of a large enough number of independent trials comes arbitrarily close to the mean with arbitrarily high probability.9.8The
or
We will never post anything without your permission.
Don't have an account? Sign up