=is۸M6GP3Nb'N;dD$1/n$lOj֕H$4BhP?<}q!D_r{ WA\o`-D \y/snڣA,n8^_;uF5a`屈k@CF1( -v{S^@#2Ə>˵80W Y(hBxgݐkjs|>'̺%2, ш3p3mѡDb3^-㍦]>=]]z1~1% D};mX{ S,YJpcܮ`|FՖcC!qݿo;IړX5:>??}I?|svq2.}*5@f8t>oGmzq~s޾h}^˱? V#RU(Y,vή?8\jj8|y͈7.|ŗI布O>w/|@'߻zeM(p}3Zwe$LlxypqiؕbN#eEaC ml7' pg Rg %pOM9̹rw 0>j2̇g6G'շ_w/OW ֍OGh Vc ]p_M+\9j^}$Se88|5=n.AGCUIL+ 8i^DJ̩D,jԒ.⊒ݳ_g=WSw|3B>+uuuu+MꫛR>0'+.JK:UDmtx-YjkĒQF ܫ74T?Amv*z~c; c矏wV7&_Y4CȘ63Wi,}E=O DzIqsZ4@|l6;i;y.}+S9ﻌ@gG=ǝ콂֡x *J fv\}kR7jzI(C6 | 3ۀnui(dTe 6CE` D^. akjQt?f5 /Fv&EP _ !S_F]g@0C`ALրY]>40othddb M!\`)ىavHwIvdd<ɣˀ682s@D]xWT5'fpP.^f"~ZuYqTɪ \Iد}Q$Ty!Δk"b ?0NJRۋE8# a G}P2 -KP0 $i 8~q*~]vYreh@j?5~]T\ρcU`D`i$Q8r ,cKT&S*f<>#u(~hyPUۄ*M*ԋiv,Dd@`"(4P 91RspJ=5Ug9NLS2 8J;0*KRCfgí ԝk^ %sB6b3;g"Lڕ~A7qkP5nbb58j%qѸ@{8EʢZd `EQkqNSZB}.\ZK/pR0 7 zk,+%纴dRL,1I+h"g.dZFX|*r&]CgSh .kuSz>j.aW̶BBMa3ezyDb6|DC*ta`[%XmfUHfVHOHIr9(c;E0 Ѯy0eE 9;8(:|Ȗ5^jM7\EIuTӓ D$ۂܛ҂uwr+8$+ћ_k PnQOk VB#y|sI怫)S`˼ wM֙I0?OD&ow!i '$\` #jW9:ej2 B 1,шҨNxL޸_LЊ3?ĹQWnC8{ AWJ6VV0T7 9G2.f5 E4˰$!,jۘ?!C6fT'hq m/fK}݅N//W?1'?wr;3X-Kn+M AN$%OE͗$JhKGC0489)څSa$*5DL\@业AimG.l;2omG[`UyE:-FN]NVA_TIS"4輙D&URj)ZEE]N6:@ CCyGYcϖ'^sUMr:]Ss5oPN9cib c<\{*ElI: l=%֕n>fx^;M-JײQu7'rjC3E!ΰ; ο^g&K[PR?YPn6ϑ)$wţA^AäT;Aq2*!ldZZӋK,HT9IFJS6 UB6x.~`Qa&T} UxxAʓ߈h*a!ca$72L1P'f1!K(Y&pJ]Z{p5qsءWKf 鳃2*is|ձ']Pόm,eMIPi|3V=Ȋ5W \0wm_zJbfgnY'g;_&R*MQ0NJ79['/8cJ({\0ɷG%<Ĭ-CC,XrCKQ񺬋s@\D>$=_53X$-RkPQ!d ~w쭴SN~/0[d KJkNެC&KQwxrk͒4sO.\=ѩ&!Q{UJ4\ՒG=ʅ4Qr=8 h\TLlRt9W8!uûG30n9W@Pk=|C200$p tќWt޺_~Y?t?}:|ߦ_ֽc~r~pu8goNzbҏPz

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(ɶ&v6yM"!6I0G{:s]|IEn&דH$,.yy#2<`mR!>7E780ȉ/"[{6p|1/pi楾fߙ0iH86xͭf7A ;eԆ/EXC 7ol7<FQ`ϱ3oL9=a7~|h}fXO=ѐ|gBDS TP[?#/و<`!T<;r8a|#.bF=XH$/7i(Љ`.A95qH4IS>?t>2bBı DTRIu9cCҥ dGO%g=:cPRM㴞@@pṖX1d @>eyHH@'[ T2ڐu<.})t઄e DBgG䉇<&5[aNZ+T<(HD¿.wlm ʘonFqQv`FRVDn 6Z +'}x' ΃>pȝRZhg+}^73"VG$qX2.hts&YH} -X*[4y8x>#xdJ2GJ+ElR疨<,-592}[w~۝a<<Όcv?pm(PD\@營/:iӗ[Ύ^-a_\o_x~=~td~u@ƟO:x|:5ܓ/·ípM4~'QǫeZm5r]U1ZkzmM_7^ٯF[6{{v$>N,=~v&V)X9f?8Nxix"u&PN];* qW` C3&K"~|x}{)z_>ҋ{i]fK@[;m>˴dZ|_C`e'$,>&O<.><xU鯧 F@0 yw9(5VLQK$+Jvq~>ڟLRWR g:խs7nH, (.T}Hbda:6+6F=[7+6,rPRT[UD(_=]zdvF|eC#c p_vixAC B"<% :fV}&MkbcҐ-qT,都,*O=|28Br>w [PtHb(2BguE;4v^#74Ȉ1hWp=nO=@8x/>7pcGC!*CiD  7@/t7N "p d3F^{T[k-4#?b&mgR$Κd xHp>e$IZ{3Ac1< vm u,PA`AŐIF&:)V4,vatd>OF#< m3*H1gZ  LѣwA%[sb*e'PP'W*:;HE˕zAtGL&"f+ sH.ŸX!3Ёf` X_y%вD áM0܌79|we)ZV4C0AHIj:6PF&F؁s,r8Be=bv}.(Q9:ʫZ/" v%W UMh"Ah*T^Hd!"Y<@AVў:a/vdVQLLTEyI8PY2;nL5mxXp(UHyXg|UZy\._g*aaMY4s{!̷tˊ@fXBsLYknҜs7ʚTFLEETe'!N++CnwHŜ\,1$sAJ2ָB )Q 9aҞk{[SeoFjH~gPl;yQ=r0kAA! 3]N,HV&4%"e p#QϳRrKkK&̈́B`ӈ^Κ*rRKƃhBZ+Ę8w[ @Rh5^Т!2{SO_f' RXCR! AETCǾx8 …" 6&xY j2kriO ^=^qoE+@]V堹Jhmn%hdD`-W32YS90' ]]+ ]ӋlY:vdA;l,m}EZXH5=@D-Hj-)-XXXw-S~Hى˾=JAf/e6%`(47̏0a2F̻p`;dy4Ό!sh JdN*`qBb. s!S{{glƷyDy<gOv+!hH0J}"]ݵmd>~ä7,ђ^< 4]ak<Z71TjL2 ـMLz 7Lk '4GL&Oԡ4OdȐ(S:DcbK!j%Jߓ&N5쐆=j mեY`iЉˏ̞%1eOظt%Pf`X\#W[vOܒ| -j)ٝd> &|=U43_!L# [}Xt.S"8L"ODh {㡁-Z9q<LH AE'JVɨ>Rm\lvh=ԒYrG젺LAZŶ,_ugsv/3#{vY~jm=䌅U1͕4@1>/X(`K)K7n{nAD 7e7+P1:xV~r[=_A<¡lTkFtA%JOZj|m%#sԦn]0,!"-^QLbТ;mփNkX8%xZ_m3Gj{t7Sa|^Vmlz[?£n7irpǦP| £jPAS/@mR:p!ҩ0:!!-C[}{{+RyK#yWCY4.GȔZ|RE1r~\>BjV/v8չ r2CzAQH g1Sf5aUjhOLTwC 5U='&)LcɫLV|I= B`XpE҉@nNJrb*ziʎf9{ }{T7Y%xYKAܓ=pyj^'meSGNg^ef=s@e݃9J'KUy茥7g঎fGeuH|Pb}j13T\CJ'ҥSdKSձ;PBr1wLSErէ2q_rKp E10ok` /jˆ(OU ͼ1)Jɤ],'$IhFkȹLY{{{{ SX!:ocZJk㉿<`/J)ނb+<0h{}܂R dw֗΀gٶ6t$-E Z jaG}uW,6#wes}C1yΟ[_ͧօ~~fw # -lx893 5.\UiuڐqZWɡ=y ĹSD?roĀ9N=-!fm*MbJWcژ Xbe]_'6) i9P_jZ q&S?3t7Z 2O9^{`lŗ)+n+z9]zZwT/IFɝ5KHN;;r|_,N5 =tRҥC'~ԭ*xy桲m's>SO@?62>\9!3!:C,şٮl_K2swhu6:[vv 1yu?g HCnx :$y@.U//!UȨ|"GP'.q%ܲ:^A=H# Vt㪮!$d&EiОc{{p K]޾~H.=s+OsLs\x2cѓ]A!5[~p#}7mq;^GcqӳOj7RT 2P%Rz=is80y9jCQs;qbǞIȬ "!6I0cgj%/(ۓu% w^^|~H\*^Ƶh9ED}`}'Fla^Ka1(j,c7'[7k+Xvʨ _(4,kQj3y0`_cg15,4r.na{\;zs?ΐ‰&{ Ɖ[?g%ؐ<`!TF<;t(a9_1B#y^|i˛DNTU}D0 B8$)n1!A"I*DV1!JjRUϣ 2dMr )I~qZO 8 a C,YU S<$N$-`C]G*mH:p:pU²B f3CFCOFYy|gt)R3-rO^08IBPn{Zz[괭 ힽnuڛ@˘,&hmZ>92&.fn,! &f{sccn766:%M1sA/.B}n`ʚ-ՁB'%FP$"_;6նe̷ASDcWUf(qh;0 )cs+r"7Ylk5bsԓa< A8N)Z-P4KM`G |CNq8,BD49,Q &ym- ~f? Wqf4: {zhu[`3:z wж{8jZo_>y/٩X/7hC*m,]E^Opr~=l~^3⍫>|bI#帇O}:'/|@'/߻~mM(p};Zwe$Llw|upyiؕcNceEaCml7 p Rg %pOM̹rw0>j*7̇g/?_L^|_t֝OϿ|6c×wG/6V- p[6tweb~1XDKr!wyUXVfhp_pbz܎]䇪j# VpҼ仉+{S XԨ%]%gku9Qzs/lf+}gх3}V?t VĹW7 |`NW\Vtډ>Z 0 %썮˭%WohB)- U*v?hso`=2;#Miޡ1mfB;Yd < ڡ!z1[+>zI#1iȁLw8*mwTvE\HVʧsw !9pz;{ CT5<<0xd}4#mwI9 G7 2n 74>\ۓdPl@N1^Ag PȨЃAlQC{ Ћ>&pō-b\:}̇.բޣZKw@B_`ߧvM$ Y $VICЧ1Ia&4π`1x;8n|*h`1<$X' FCR%1Ȗy$GWmpPe)Tb!6T 1dkN]%vE@ D1JEgȓUpб_/8HB)D~eaI[å8qF:0:L X+dZ(=`8TIqf"TPN0X7SWʁ&~ )|7B5H8~Q8r ,c+T&S*f<>#u(~hWyPUۄ*āBE4;A"2 0(\9j횪hh'@I`pyJ%QT؝UpԊ %p)L!VT N5WRZǡw`jpPe]'YR[AU:ȓ5(-tOZ?j!}bAaj]אa)ͮq^ L;"d$ T{ DdCDZ}X(Ha Ke0@:u@>RiV0 J*I5Me01(`$X&qtb £Зkg7b}B7Vǔ|qCm?BsQ4eOP5?: sNA~#2E %aܘ9e0 @F2`2łA0kyq#'xw+!0Fk0jCDgEܫ\f$IrL~DqۡKXA.axc"<ʔS$^VƞW`{-#UZ[PPp @bYFe[Os6e:I YX7Ji8磶r*zul+T,6SG.)|ήL! ` G>riO ^=^roy+@]V堹Jhmf%hdD`-WS2֙S:0{ ]]+ ӋˇlY:vdN;h/l}EZXH5=@D-Hj̽)-[Xw-S~Hى˾]JAf/e6%`(47̏0a2F̻p:v0iv.7; T>=`Ĝ lu!0Yy[-~~?$Gg߿J àSFZAH!e91\  Zqbs&G8;"j-z'zo>sRzJ&*F8gH[̼Faf?dE t'~؆ 8Ξ-rZ/'V_Ncz%}m$iVD\ mɀhx'3'@0`*,t>DH@ZI W2bW=(mǗ6BhKw*oH=h[Zߩ*r*~JD7Ȥ"ZJ-%"PȱkPFț'i2{vf7dr95zT*ףߞ^K}\8Ǎ+򤉊x.5/rePTBҐ`4{D;+ T=@^IoXۣ-xAhG*$yT3~kbTT٫m2Ldp>|!1^Lk4G_L&Oԡ4{dȀ(S:Dcb !j%Jߓ&N5l=j mեY`a? XR'"bnC<* A=c!# ǀkyD GfO'l\E(S0b.J`K-;էNnI J^NHw2E_W*h/iS~8!& 5r'EK1]:'%İ18Cxh`KmEp1yO X79؉C'rJq!⺐f&b)k> CCyGYcϖ'%^sUMr:]Ss5oQN9cib c<\{&ElI: l=%֕n>fx^;M-JײQu7'rjC3E!ΰ; ο^&K[PR?YPn6ϑ)$WţA^AäT9Aq2*!ldZZӋ+,HT9IFE` *z 5/hL@ [mE|eI NJ;RU/[(=iA򵱗 Q:Fv624E1AZ;Ur0di}NȋV;C*(/:Pmm?W7Wmml$̓S@xtM[-B^:h-z\@.$PT:U?$e{oU߻7$4w5E^LEW!+[4 , ̕#ԙʉ6.Nm`QbicP )y)3 ypp$0rKx3e^3\v`TdOu7/9XЎ,^uCNOOM}bB T;Vʤ ۏcLYǢs,NTppW lSHPvD4ͩ[[12 }̢X˻mU7u>;j-רSG_D CXQq^2'W:T.' \r4܁r5 CxgJ4*B/K>( $-\)y[ y| #_6D|"w`m-IAUJ&b1A HBlGM7Z`[[ -i1i6HC|_}Q]NqH^B ń րF@x/D$h  t<˶ x&#iy/PhP -=%fQ V}>,˽PDu\Jo>A/.ôES @OY uh᡿O5w=&5L_ u].~ኔNz[)-Mȹ'̈tdB Xی@oWlédokl|aD1 `vyPkKe6ܮ_:?`+3WYV L -k|+D ~sUWI1ji]&srL)8He|7}+]xhc`)5^uy|~ȇ+f뜤\RbBU~-2Y>j7ęL~0v}fKL}^v[q{כWsȤzI5*_дOYFry%q~4:$$ ӽJI&S?ZUg]:FrWR0_V'WZXki,X`Ŭ\r-̺v_Qg~_\юʺ4!J

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