=is۸M6GP3Nb'ı'vɬ "!6I0cM_xIEٞT֕H$4эFwA/gdy.~˥B5|n\qk0ac_DԷsw|1/pi慾f3iNH86{}qX5= 2j×"J q3L (05FL {˰?b>r,Χ`Gh\3dp =uC*-뒗l\*D#^:l0A9v4سб!ow"ʮ$d..3"[H "?`}s 8b4cߵ<ф&csdfql@ %i膄 nkFkѺs$ԛ#ov) Hm77)zs1s4[ i#5lo1wSpo Jw!b hv&Qc ~ک,Yrpcܮ,x!N8$pWIu)h8l#ݦVOh[d7ᣤӜy @v&0q {gh(37fڂc.&nG ^sXDsϪ=.V0 L]`?viHFǀޖ[#5 !II,X(I>:^1B#"&ycyVn D(^DC4-#=&D;B$I(*X\0&GZ}YNtMr )I~qZO@@pPC_1fTxOʪ8N uSd!h]&02 Jl:C>d$O<1!`) LJY?P=}&H"<" MRo fw[ӵVmmXnuvX^ d6ion7H^'FkՂ?蓃.s]4q06-vV!i04 677ۛs1-*hՌ" z@u3{Pl:ADDh-P5&  ޱK(c "RŠġ"4ͭȉ$ Zk g(+('=|'0 ΃>pʝPZ hgM`G vMաo8InNb> iTP/8)Ii]e˂&cPЧ=@ sZH`(5i̢#SQ/LJF)|3z|מq:g5% 3=yo:U)ӗ7gg'oч_/wekܺ^8Z]F=|: EQh۽`\/ZrOrt!tET6d+.?_1h>g<ŇS'?}>x3(渃O>>||Z3M>;wʚP`קfTJI&~{7ӔؕcN#EaS ml7' 0gRg %pOU92w 0>j2̇g(>||;+?4 VĹW7 $`MW\Vtډ>Z a:6K6F][K6,^jb (KˈQzᅢTJ.ZF6h3+ڙ"ۧMX)`0hR3)nz_;>toͣfyC5mgQQTml>}rQq'{u?^07b<;)"W߸:z|D22 IF. )ىavHsIvdf<ɣˀ6(2s@ !6T #1d둘AL2j8;OYD]J\~=$~#~)dP$m ^,Q3Ypa/=ꃐkY"PP]fw'I[X`m͋>PA;mt@ZV4fЯ wj86PJF2o9 g;X &!l>qϢD(/j8_&ڥJmB@S u"N 0Ld=$'5 FzFԣ]Su_4?u9).#XX)'BZq.=dv6 j1x\p(HY{XW|URyZ._G"*ɇ9Mi 9}rk-HecYl([gY)9ץ9f„`! ӈ^ƚ{>*rRKpLZ#W>qjZECe qLO,dܥ2C:\TY}#Zqb" 7&xޚ 2<έ:%pȃj.Q==ύ즾 ChZ~HH0MdPu6ΎGH S&]AB./oG8V3\,^tZ ^Ż1G؍&07rÑz6 6~VMLL L!Cy}\.ӾlB':fVAzب1 Ex =|#Ƥ\/ Ԕrcw^ 0*} LIˀz-X1Ug#2`Kl:$0;gҠa]wnUw˩0Yat2P)LQv |y&.!RNnKK a AsEnLh'jzX.9wP?J=r5cE7Qp&l4JHC<p)&6e#S<ī0;W2MhP54_ oߛ*UwW5Uyqt\Df=[HL׃GJULf6 /}&u(712C<3ҫ~9> FpErԛ/1`{p X)f8 L#E <ȵ<\{tC'b =Mb:rCW2aQdwB\pPn51D"fIด⡂[f.@sG|0HD`(yt:FgHC lITV䰺(Q&'@1t$_6>R:.ƅ`"@/泑j14>-z>my\05LmJMn엗t͑yjuQH%]GG]VC'S,gKNf`_,.w K6ÃiR@9 W) ~Mڑmp~O(w{)>qX,&BnA pVAxGFFG{A *|wH0c2*OMpTa52--%n$r`B$E +z <`A 1<xA `;t_Cy6{1I1q ߈h*ai汰|kEISY } %샊,z_}.J=i9P{쫐YrԃGLNZŶt`u>hsz/3#{ۓ vY~jm>I0Uo`dſ{TR'\$='XQR|nv>5n4 -7( {UP>GYku&~n5#:.ͥ{wnM,I meQ!a:ISUHJnUB0:²J=s uro˼]ZEcT,ȁ~J^ B6 F!L W!>+ ><8c+˟WPӓSQX sϓwv{@{VI= cXpE҉nNKrl*Zi9 ʎdf9{}sTY&xY AܑwyjҞg'w-SCNg^ej=3@dݽ5޽J'KU蔦3g`?fgeb:5E+}zLLh1o^t*a:,0a:rgDKP4Т!U?iIPS8LRoD0܍р ZŤ )n"Y1gވX%wNt\(Ԑv[d5}*q#SY:/pZH[㱿nDF "<P!Vkk}ȒEUNF?ozJOaRɟts[źuOm.=us.XׁIB~4X 7J:Rgp^c;:EnAۦ<v7!0#nɢ^J.uJwn-S."BB|zi .G<1ծo8>;UO}SU3uNo.^15)ՋjMq&>3lAeo+v(}gؒSh_ݔ,:b1oM ɭ%KEH.;ϝ>`>nJDeWҴ{sEKV*+Z'HJUf>a/RJ +`rM2"mO C1˗4?+Guԭe/UQюʺ4 J <]|\H~ot[=|C201$R/ xNg7B:?~]?t?}<|צ׽c~r~pu8g?=\OFb5!EX܅y

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar


QuestionofDay

Question of the Day


Key Concepts

Key Concepts

  1. Markov’s Inequality: Let X be a random variable taking only non-negative values. Then for each a > 0
    P[X > a] < E[X]/a;
  2. Chebyshev’s Inequality: Let X be a random variable. Then for a > 0
    P[|X - E[X] | > a] < Var[X]- a2
  3. Weak Law of Large Numbers For e > 0
     [ ||S || ] Pn ||-n-- p|| > e --> 0 as n --> oo n

    and the convergence is uniform in p .

  4. Let f be a real function that is defined and continuous on the interval [0, 1] . Then
     || sum n ( ) ( ) || sup ||f(x) - f k- n xk(1- x)n-k||--> 0 0<x <1| n k | k=0

    as n --> oo .


Vocabulary

Vocabulary

  1. The family of polynomials
     ( ) n k n-k Bn,k(t) = x (1 - x) k

    are called the Bernstein polynomials.


Mathematical Ideas

Mathematical Ideas

This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 5

Proof of the Weak Law Using Chebyshev’s Inequality

Proposition 1 (Markov’s Inequality) Let X be a random variable taking only non-negative values. Then for each a > 0

P[X > a] < E[X]/a;

Proof 1

P[X > a] = E[IX >a] integral = dP integral X >a x- < a dP 1 < --E[X] a
Q.E.D.

Proposition 2 (Chebyshev’s Inequality) Let X be a random variable. Then for a > 0

 Var[X] P[|X - E[X] | > a] < ----2-- a

Proof 2

This immediately follows from Markov’s inequality applied to the non-negative random variable (XE[X])2 . Q.E.D.

Theorem 1 (Weak Law of Large Numbers) For e > 0
 [ | | ] P ||Sn-- p|| > e --> 0 as n --> oo n |n |

and the convergence is uniform in p .

Proof 3

The variance of the random variable Sn is np(1 - p) . Rewrite the probability as the equivalent event:

 [|| ||] [|| ||] Pn |Sn- - p| = Pn |Sn-- p| . | n | | n |

By Chebyshev’s inequality

Pn [| Sn - np |> ne] < Var[Sn]-= p(1---p) 1- (ne)2 e2 n

Since p(1- p) < 1/4 , the proof is complete. Q.E.D.

Note that the proof demonstrates that

 [||S || ] Pn ||--n- p||> e = O(1/n) n

uniformly in p .

Bernstein’s Proof of the Weierstrass Approximation Theorem

Theorem 2 Let f be a real function that is defined and continuous on the interval [0,1] . Then

 | | | sum n ( ) ( ) | sup ||f(x) - f k- n xk(1- x)n-k||--> 0 0<x <1| k=0 n k |

as n --> oo .

Proof 4

  1. Fix e > 0 . Since f continuous on the compact interval [0, 1] it is uniformly continuous on [0,1] . Therefore there is an j > 0 such that |f (x)- f(y)|< epsilon if |x- y|< j .
  2. The expectation E[f (Sn/n)] can be expressed as a polynomial in p :
     [ ( )] sum ( ) sum ( ) ( ) En f Sn- = nf k- Pn[Sn = k] = nf k- n pk(1 - p)n-k. n k=0 n k=0 n k
  3. By the Weak Law of Large Numbers, for the given e > 0 , there is an n0 such that
     [| | ] P ||Sn-- p|| > j < e. n |n |
  4. | [ ( ) ]| | ( ( ) ) | | Sn | || sum n k || ||En f --- - f(p) ||= || f -- - f(p) Pn[Sn = k]|| n k=0 n
  5. Apply the triangle inequality to the right hand side and express in terms of two summations:
     sum ( ( ) ) sum ( ( ) ) < f k- - f (p) P [S = k]+ |f k- |+ |f (p)| P [S = k] k n n n k n n n |n-p|<j |n-p|>j

    Not the second application of the triangle inequality on the second summation.

  6. Now estimate the terms:
     sum sum < ePn[Sn = k] + 2 sup |f (x) |Pn[Sn = k] |k-p|<j |k-p|>j 0<x<1 n n
  7. Finally, do the addition over the individual values of the probabilities over single values to re-write them as probabilities over events:
     ||S || ||S || = ePn[||-n-- p|| < j] + 2 sup |f (x)| Pn[||--n - p||> j] n 0<x<1 n
  8. Now apply the Weak Law to the second term to see that:
    || [ ( ) ]|| |En f Sn- - f (p) |< e + 2e sup |f(x)|. | n | 0<x <1

    This shows that ||E [f (Sn-)- f(p)]|| n n can be made arbitrarily small, uniformly with respect to p , by picking n sufficiently large.

Remark 1 The family of polynomials

 ( ) B (t) = n xk(1 - x)n-k n,k k

are called the Bernstein polynomials. The Bernstein polynomials have several useful properties:

  1. Bi,n(t) = Bn -i,n(1 - t)
  2. Bi,n(t) > 0
  3.  sum ni=0Bi,n(t) = 1 for 0 < t < 1 .

Corollary 1 The polynomial uniformly approximating the continuous function f(x) on the interval [a,b] is

 sum n ( ) ( ) ( )k ( )n- k f a + (b - a)k n x---a- b---x- k=0 n k b - a b - a


Problems to Work for Understanding


Reading Suggestion:

  1. Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Sections 1.2 and Chapter 4.
  2. An Introduction to Probability Theory and Its Applications, Volume 1, William Feller, John Wiley and Sons, 1968, ISBN-13: 978-0471257080, pages 228-247.
  3. Probability, by Leo Breiman, SIAM: Society for Industrial and Applied Mathematics; Reprint edition (May 1, 1992), Philadelphia, 1992, ISBN-13: 978-0898712964.


Outside Readings and Links:

  1. Virtual Laboratories in Probability and Statistics ¿ Binomial
  2. Weisstein, Eric W. ”Weak Law of Large Numbers.” From MathWorld-A Wolfram Web Resource. Weak Law of Large Numbers.
  3. Wikipedia, Weak Law of Large numbers


=ks۶P79(gۭ8vc6$$_rw%Qe^O" ./ ܃="Koܸ R`~` o$b^҈7+})̞3fvE bqǑplٛS[o+Xvʨ _(4,oQj3y0`_bg15,4r.na\;zsΐ‰&[ ǷKؐ<`!TF<;t(aJ:͙w@ X`gnzvhy2kygv-X;b zN|$X5Ǟ[E4`0b`c$aXN { yM.!9Z2DĂRښn|-̸860404+۴;pDNU}D0 B8$)n1!A"IEV19Bҥ dGzt7phlBKH 6M3zj@P`>0K { PVĉt"l눘@% )_G2YݗLQQbB!#y' ,OY<>z 3A)ItHߝ;$f)`vڌmVW{[aݳ׭N{az3EڤY V{V O%߭(?8Ān< ~H nX퍍i Pq0Df\ 5¥P_,؇fgSu ""Bk 0ѕ!H7E N_Cm8m(%mV!ylnEN&y}Z#@YA9?a(pSA<+h gB2CL+eElR,,-=>6G 㵏ƗG7>p)PD\@/.;IړMwϏ_Ma_^wG/.6&_'?Z?YїΗus;wpJkp38y Gmzq~}޾j}^3˱^nhC*m,7]}|Yxy/7[W.Ν <4:WOX z?pO8/q8};yք>oףzWJ4A}뫣ë_MSF`Wn~Y8iB POh E߇N @l67d\K1=cT}8g@5 2]Ԉ틣~dSޜN]iCqLgӊEĽ:Va}6oH8t3#M۱wБP|@i bF|7q^Te"5jIdqE9ܳߪg=gSw|3B>+?4 VĹW7 $`MW\Vtډ>Z a:6K6F][K6,^j b (k;Q?|oTJ.ZF6h3+ڙ"ۧMX)`0hR3)nz_;>toͣfyC5mgQQTOml>}rQq'߃s"H dv\}k֛R7mjzI(B6}3nui(We 6]E` X~.taCkj~Q48f@\_`ߦL$ Yt$VI莃ӧ1Ia{&4?Ȁ1;8Yn|9*`c|9#IN424paH N ;DCKk'3[L]Զ@QSjLѥwA%[  u2ߞVs@@(ơVA$&W:6y_' 3uA3eLDLW'"ikb?ΈBfGɂ+`}Q ]'2;I:k3l^ i]2r `<-~]`TPcm*P"4Y83hb(L0Dy`}%"GTGyQQd5ѮUBUmx Uiv,Dda"4 9q`0Rs0j홪h'@IpyJ9Q؝pXԊ %p),!VT8 uG@-/Jz85 8 2.|̓u*I_d'- cbPXZc5bXbJJnW.s&xB)>#r2( ;O>SjEZHDF=ɃǢ} QTpnAlеwy"r:!do[ 6$V2DS4ae0qKTm~ļF?(YO !UOKNEm5P훔\ZˢثFdlݱa<`ɠwM{mN2\d+YsF<^K.-Bb 3tZGhn["SkE?'gaaMi4Ys!N4ˊ@X4gWEsNLt+kR-j1mBiHZퟨ/- ź#essռD8KZc@0 0NPDaΩv]sM̚.|#6T`;r )[wy| ׂ[ApBYT < QyMiJKyp\ki@*{ DdCDZJɥ.͙7& aPF0֤o4pV Z$cLs$VeZ4d~^yBF k]*3=1̕Juwb \(&{s7XǹU'ӕ#^1 ۛ9_A E?B_qpyw=Am>ԫ;]2"kIxP{Q0 e0 F] c2łkོ#oNLQ+v t0čp$F6> qtpGIQb;h(ѭ WMGuo)*DL~h+ pl ttdy.kPvZ탅-EIn'?HI7s nB=F]Qw9W0ddl2J64s Qh$oG:a2WfLp~g;dy]Όsh %2~ nOOX8!1[]LVV _~Lޞ_oR0QV`R[FPJucxZ؜ 펈\CDoB XoB*< FpEr(j%pl&|{ 'ˤWb˶Rkfn;*d>d.`mV-<'Xx:Z Hd¢]֤ZO/9aYԉ@6&I V0E߅`{UFFA`Qf:aGq'iY$I>wdRU#^95ZeG "Qz$;Wkc/6uva =mdi~D1Nb*9pBX\''j{llom_Ƨ â kT[նBDžG[kI96`쐭VЦׄu:\eBNO~` Щп:("!̈́羻T%,*"LtV'iJ5B )?XݢJFgVXVic|qTNmrw+VxH} 9O+!P}ӆ ($[³)3 *sw4r%{yvleCtzvzf:*|KayΓ:nb/hߟ]j1gACpLH:1_P- _t)]MEk22Aّ =<2l6zﮕG Ev9hOaV_/xI> ~ǝH`UQAQ`*Ċrm;Yrj=RI{W ;L*Srn.p|6Xqڢ:0\]o5&[5TG ~t].~alG'J-pǔ'&fm:YkP:.[.mt*%Z$3[HhOo -!-difCcF9%JUo3|mfj;ݲNN w?`M$' :PuUA6`nr9'G@19KQ%6 %<'Ce XzCSJQ񆪫ӋK@\D%=Z53Y;SQfyog2|?SZknTZ[f&mw->0z ]Q͢(V __ƍд[[+vQJtIHQ&{.MK~4WabϺru/T%/ac|"*8԰&>*$#Җ0|O#>"MTG_R=eYKc /sO͕g_VNŃI'`/?x%+2u;sIBZ6b?kfgnӎ7Un qD97S| ȥes"3$*u9O$Nߥ:OT1tH/ՋșQC:JAɐMk7 g>-߿{ /smC3Ls\x2ɳ]A! z,T:sޟt>m~ZNÑq{r;+!&}Տ6X)y=is۸M6GP3N$N;dD$1/n$lOj֕H$4BhP?<}q!D_r{ WA\o`-D \y/snڣA,n8\cn]3{ѣ` b)6|y,PhG=cA }^cl԰ #C+1r|v4,Tcϭ"0{V X!w¼.' 0tAإ! h9H:F>?.%$G@kBfXQJ[|r >|#.bF=XH$/i(Љ`.A95qH4IS>?p>2bBı DTRIu1cCҥ dGO$g=:ePRM㴞@@pṖX1d @>eyHH@'[ T2ڐu4.})t઄e DBgՇ䉇<&92_QqpEc3ryl7aI`ss17``&\ҹZK]>YeΦ@XDDU#ab(Jjۿ2۠)*Q\8Q@屹9,61 I0 Cr'(%Yߦb vMաo8I "ݜ }|Ҩ`@_qCh<ҶʖM+O z45A"'洒 Qj,JEGԹ6 u _sg|/=3xmэ/,\mykJ=f;"+y3=yo:U)ӗ˷gg'ΫY?Yѷηuu= zzhu{`3z>Fmzq~{޾h}^˱? V#RU(Y,r=Գo[ON <0:O`X z?tƏٷ_f|Z 0 %썮˭%WohB)-U2v?hso`=2;#Miޡ1mfB;Yd < ڡ!z1[+>zI#1iȁLw8*mwTvE\PVʧsw !9pz;{ CT<<0xd}8#mwI G7 2n 74>\ۓdPl@N1^Ag PȨЃAlQC{ Ћ>&pŵ-b\:}̇.բѣZKw@B_`ߧvM$ Y $VICЧ1Ia&4π`1x;8|*h`1<>$X' FCR%1Ȗy$GmpPe)Tb!6T 1dkN]&vE@ D1REgȓUpб_/8HB)D~eaI[å8qF:0:L XKdZ(=`8TIqf"TPN0X7SWʁ&~k )|7B5H8~Q8r ,cKT&S*f<>#u(~hyPUۄ*āBE4;A"2 0(\9j횪hh'@I`pyJ%QT؝UpԊ %p)L!VT gN5WRZš{`jpPe]'YR[AU:ȓ5(-tOZ?j!}bAaj]אa)ͮq^ L;"d$ T{ DdCDZ}X(Ha Ke0@:u@>RiF0 J*I5Me0qnt列.Aj /ճQ/?n+Ѐ uY-Ag(Lp`j(1H=jn4^k0jCgEˤ`$qrL~DذKXC.axc"<ʔDcH*UJ;F/^*-} LIˀz-x 1Ug#2AXpߧ9@Sf`p,]44]v9L wV2:X)L]B@ f(HR (tK̼󖊰,AsEa̒H* 4[."j3K f!u`0Fl_)XP;gEWG u\mɜx_%(ɱ=jz#d[{SZ0V\nrd%zWׇڃ+s_rem2J64s Qh$ot:Ip5=`Ĝ lu!0Yy[-~v? N?ABr4b47. LqnwD%N&},ǕݢUݾSqUW&UR< :&I%EtZJDVcQנ7Ol.d@mo_=!ؗ*c\{GlzQĊ FpFr"{=4uXV0@;@'$U PI>pŷ<A(/I 諳@2ozOvT؃P.OJ5A@eQ=X9pE%ڣC:{Lp$n ˠX|dRtN/E-%ҝༀLчĕ'3f8Di$TbSCB\I!R GP|pHD`yt:FgHC lIԺau.8Q&'@1t$R^96>.!u\\D^,0g#$chr[( }>`k.j3)5u"_^VkrjNZ թ2@bl"t]w]a xOe(-;'޺', v9HI[!J[w^mhӧ(6sGwBK}d0qr J@G0 Mզs<27$nx4(2 b09ho4(3._>S%7DCULKwzqX`<"(@wLHAyGOI>Rm\ʹvh=ՒYrԃGLAZŶt`u>hsz/3#{ۓ vY~jm>I0U1_͕4@1&IY(`K) 7nӍVCn4 -VoWtct(V";2K$ GrC'%e*-uVQJ KGnMjg`XBrOEŠEwPk*9pBX\'gj{llom_Ƨ kT[ն 66 wlů@xtM[-B^:h-z\.$PT:UE$e;oU;sobI*oh$ok(eIRB Wrch:Yl5+_\3{[m\ʟբ6.Ǡ:`ASBf@0wG Ev9ŵў¬"z %&|Xu⽴,c522+~˹5|dݢHm'Uwo=_'r0O -|b]i:৶B:9su!' j/VMk4<\õp"mmSL;ěsOdQA%X@o%Wlédhl!o> `vPGٛ KeC: 7WAo;B՛MC6stx8935,LU uڀqZW28y ĹD߫r/YN-!?*sLJ#ژjWb7T]'!)֪:'7y_Ջj q&>3lAeo+v(}gؒSh_T,:b1^3pWq#4-[k|v;}r|.W)N5 tRҥi檖%"8.s.H.hZ{K\>j7sHS)(Iэ";^?&'|Ǐg6`ݘ=|ys|zxd0``H rJT*99oϿs~趏~zl}~YϯÑ8|tr=!&}ׄO6: y

Last modified: [an error occurred while processing this directive]