กลับไปหน้าบทความ

อ่าน 6 นาที

บทพิสูจน์ของโฮฟฟ์ดิง

ความไม่เท่าเทียมกันของความน่าจะเป็น/ต้นขั้วความน่าจะเป็น

ในทฤษฎีความน่าจะเป็นบทพิสูจน์ของ Hoeffdingเป็นอสมการที่จำกัดฟังก์ชันสร้างโมเมนต์ของตัวแปรสุ่มที่มีขอบเขตซึ่งหมายความว่าตัวแปรดังกล่าวเป็นแบบซับเกาส์เซียนตั้งชื่อตามWassily...

บทพิสูจน์ของโฮฟฟ์ดิง

ในทฤษฎีความน่าจะเป็นบทพิสูจน์ของ Hoeffdingเป็นอสมการที่จำกัดฟังก์ชันสร้างโมเมนต์ของตัวแปรสุ่มที่มีขอบเขต[ 1 ]ซึ่งหมายความว่าตัวแปรดังกล่าวเป็นแบบซับเกาส์เซียนตั้งชื่อตามWassily Hoeffdingนักสถิติคณิตศาสตร์ชาวฟินแลนด์- อเมริกัน

การพิสูจน์เลมมาของ Hoeffding ใช้ทฤษฎีบทของ Taylorเลมมาของ Hoeffding เองก็ถูกนำไปใช้ในการพิสูจน์อสมการของ Hoeffdingรวมถึงการวางนัยทั่วไปของอสมการของ McDiarmidด้วย

คำแถลง

ให้Xเป็นตัวแปรสุ่มค่าจริงใดๆ โดยที่เอX{\displaystyle a\leq X\leq b}เกือบแน่นอนกล่าวคือ ด้วยความน่าจะเป็นหนึ่ง จากนั้น สำหรับทุก ๆλอาร์{\displaystyle \lambda \in \mathbb {R} },

อี[อีλX]เอ็กซ์(λอี[X]+λ2(เอ)28),{\displaystyle \mathbb {E} \left[e^{\lambda X}\right]\leq \exp {\Big (}\lambda \mathbb {E} [X]+{\frac {\lambda ^{2}(ba)^{2}}{8}}{\Big )},}

หรือเทียบเท่า

อี[อีλ(Xอี[X])]เอ็กซ์(λ2(เอ)28).{\displaystyle \mathbb {E} \left[e^{\lambda (X-\mathbb {E} [X])}\right]\leq \exp {\Big (}{\frac {\lambda ^{2}(ba)^{2}}{8}}{\Big )}.}

การพิสูจน์

การพิสูจน์ต่อไปนี้เป็นการพิสูจน์โดยตรง แต่ค่อนข้างเฉพาะเจาะจง

การพิสูจน์

อนุญาตμ=อี[X]{\displaystyle \mu =\mathbb {E} [X]}เนื่องจากข้อสรุปเกี่ยวข้องกับเอ{\displaystyle ba}โดยไม่เสียความเป็นทั่วไป เราอาจแทนที่ได้X{\displaystyle X}โดยXμ{\displaystyle X-\mu },เอ{\displaystyle a}โดยเอμ{\displaystyle a-\mu }, และ{\displaystyle b}โดยμ{\displaystyle b-\mu }ซึ่งทำให้เกิดความแตกต่างเอ{\displaystyle ba}ไม่เปลี่ยนแปลง และสมมติว่าอี[X]=0{\displaystyle \mathbb {E} [X]=0}ดังนั้นเอ0{\displaystyle a\leq 0\leq b}.

เนื่องจากอีλx{\displaystyle e^{\lambda x}}เป็นฟังก์ชันนูนของx{\displaystyle x}เรามีสิ่งนั้นสำหรับทุกคนx[เอ,]{\displaystyle x\in [a,b]},

อีλxxเออีλเอ+xเอเออีλ{\displaystyle e^{\lambda x}\leq {\frac {b-x}{b-a}}e^{\lambda a}+{\frac {x-a}{b-a}}e^{\lambda b}}

ดังนั้น,

อี[อีλX]อี[X]เออีλเอ+อี[X]เอเออีλ=เออีλเอ+เอเออีλ=อีแอล(λ(เอ)),{\displaystyle {\begin{aligned}\mathbb {E} \left[e^{\lambda X}\right]&\leq {\frac {b-\mathbb {E} [X]}{b-a}}e^{\lambda a}+{\frac {\mathbb {E} [X]-a}{b-a}}e^{\lambda b}\\&={\frac {b}{b-a}}e^{\lambda a}+{\frac {-a}{b-a}}e^{\lambda b}\\&=e^{L(\lambda (b-a))},\end{aligned}}}

ที่ไหนแอล(ชม.)=ชม.เอเอ+ln(1+เออีชม.เอเอ){\displaystyle L(h)={\frac {ha}{b-a}}+\ln(1+{\frac {a-e^{h}a}{b-a}})}โดยการคำนวณอนุพันธ์ เราพบว่า

แอล(0)=แอล(0)=0{\displaystyle L(0)=L'(0)=0}และแอล"(ชม.)=เออีชม.(เออีชม.)2{\displaystyle L''(h)=-{\frac {abe^{h}}{(b-ae^{h})^{2}}}}.

จาก อสมการ AMGMเราจึงเห็นว่าแอล"(ชม.)14{\displaystyle L''(h)\leq {\frac {1}{4}}}สำหรับทุกคนชม.{\displaystyle h}และด้วยเหตุนี้ จากทฤษฎีบทของเทย์เลอร์จึงมีบางสิ่ง0θ1{\displaystyle 0\leq \theta \leq 1}โดยที่

แอล(ชม.)=แอล(0)+ชม.แอล(0)+12ชม.2แอล"(ชม.θ)18ชม.2.{\displaystyle L(h)=L(0)+hL'(0)+{\frac {1}{2}}h^{2}L''(h\theta )\leq {\frac {1}{8}}h^{2}.}

ดังนั้น,อี[อีλX]อี18λ2(เอ)2{\displaystyle \mathbb {E} \left[e^{\lambda X}\right]\leq e^{{\frac {1}{8}}\lambda ^{2}(b-a)^{2}}}.

คำแถลง

ข้อความและบทพิสูจน์นี้ใช้ภาษาของ ตัวแปร ซับเกาส์เซียนและการเอียงแบบเอกซ์โปเนนเชียลและมีความเฉพาะเจาะจงน้อยกว่า[ 2 ] :เลมมา 2.2

อนุญาตX{\displaystyle X}เป็นตัวแปรสุ่มค่าจริงใดๆ โดยที่เอX{\displaystyle a\leq X\leq b}เกือบแน่นอน กล่าวคือ ด้วยความน่าจะเป็นหนึ่ง จากนั้นจะเป็นแบบซับเกาส์เซียนที่มีค่าความแปรปรวนตามบรรทัดฐานตัวแทนXวีพีเอ2{\displaystyle \|X\|_{vp}\leq {\frac {b-a}{2}}}.

การพิสูจน์

ตามนิยามของตัวแทนความแปรปรวน ก็เพียงพอที่จะแสดงให้เห็นว่าฟังก์ชันก่อกำเนิดคูมูลันต์ของมันเค(ที):=บันทึกอี[อีที(Xอี[X])]{\displaystyle K(t):=\log E[e^{t(X-E[X])}]}พอใจเค"(ที)(เอ)2/4{\displaystyle K''(t)\leq (b-a)^{2}/4}การคำนวณอย่างชัดเจนแสดงให้เห็นว่าเค"(ที)=อี[(Xอี[X])2อีที(Xอี[X])]อี[อีที(Xอี[X])](อี[(Xอี[X])อีที(Xอี[X])]อี[อีที(Xอี[X])])2{\displaystyle K''(t)={\frac {E[(X-E[X])^{2}e^{t(X-E[X])}]}{E[e^{t(X-E[X])}]}}-\left({\frac {E[(X-E[X])e^{t(X-E[X])}]}{E[e^{t(X-E[X])}]}}\right)^{2}}โปรดสังเกตว่าปริมาณอี[(Xอี[X])อีที(Xอี[X])]อี[อีที(Xอี[X])]=อี[(Xอี[X])อีที(Xอี[X])อี[อีที(Xอี[X])]]{\displaystyle {\frac {E[(X-E[X])e^{t(X-E[X])}]}{E[e^{t(X-E[X])}]}}=E\left[(X-E[X]){\frac {e^{t(X-E[X])}}{E[e^{t(X-E[X])}]}}\right]}คือค่าคาดหวังของตัวแปรสุ่มที่ได้จากการเอียงแบบเอกซ์โปเนนเชียลอย่างแม่นยำXอี[X]{\displaystyle X-E[X]}ให้ตัวแปรนี้เป็นวายที{\displaystyle Y_{t}}เหลือเพียงการกำหนดขอบเขตวีเอ[วายที](เอ)2/4{\displaystyle Var[Y_{t}]\leq (b-a)^{2}/4}.

โปรดสังเกตว่าวายที{\displaystyle Y_{t}}ยังคงมีระยะทำการ[เออี[X],อี[X]]{\displaystyle [a-E[X],b-E[X]]}ดังนั้นจงแปลมันเป็นที:=วายทีเอ+อี[X]2{\displaystyle Z_{t}:=Y_{t}-{\frac {a+b-E[X]}{2}}}เพื่อให้ช่วงของมันมีจุดกึ่งกลางเป็นศูนย์ เหลือเพียงการหาขอบเขตเท่านั้นวีเอ[ที](เอ)2/4{\displaystyle Var[Z_{t}]\leq (b-a)^{2}/4}อย่างไรก็ตาม ตอนนี้ขอบเขตนั้นเป็นเรื่องเล็กน้อย เนื่องจาก|ที|เอ2{\displaystyle |Z_{t}|\leq {\frac {b-a}{2}}}.

จากกรณีทั่วไปนี้ สูตรจะเป็นดังนี้อี[อีλ(Xอี[X])]อีλ2(เอ)28{\displaystyle \mathbb {E} \left[e^{\lambda (X-\mathbb {E} [X])}\right]\leq e^{\frac {\lambda ^{2}(b-a)^{2}}{8}}}เป็นเพียงผลสืบเนื่องมาจากคุณสมบัติทั่วไปของตัวแทนความแปรปรวนเท่านั้น

ดูเพิ่มเติม

หมายเหตุ

  1. ปาสกาล มาสซาร์ต (26 เมษายน พ.ศ. 2550). ความไม่เท่าเทียมกันของความเข้มข้นและการเลือกแบบจำลอง: Ecole d'Eté de Probabilités de Saint-Flour XXXIII - 2003 สปริงเกอร์. พี 21. ไอเอสบีเอ็น 978-3-540-48503-2.
  2. Boucheron, Stéphane; Lugosi, Gábor; Massart, Pascal (2013). ความไม่เท่าเทียมกันของความเข้มข้น: ทฤษฎีความเป็นอิสระที่ไม่ใช่เชิงอะซิมโทติกสำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Hoeffding%27s_lemma&oldid=1360736293 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ บทพิสูจน์ของโฮฟฟ์ดิง

ในทฤษฎีความน่าจะเป็นบทพิสูจน์ของ Hoeffdingเป็นอสมการที่จำกัดฟังก์ชันสร้างโมเมนต์ของตัวแปรสุ่มที่มีขอบเขตซึ่งหมายความว่าตัวแปรดังกล่าวเป็นแบบซับเกาส์เซียนตั้งชื่อตามWassily...

คำแถลง

ให้ X เป็นตัวแปรสุ่มค่าจริงใดๆ โดยที่ เอ ≤ X ≤ ข {\displaystyle a\leq X\leq b} เกือบแน่นอน กล่าวคือ ด้วยความน่าจะเป็นหนึ่ง จากนั้น สำหรับทุก ๆ λ ∈ อาร์ {\displaystyle \lambda \in \mathbb {R} } ,

การพิสูจน์

การพิสูจน์ต่อไปนี้เป็นการพิสูจน์โดยตรง แต่ค่อนข้างเฉพาะเจาะจง

ดูเพิ่มเติม

ความไม่เท่าเทียมกันของ Hoeffding ความไม่เท่าเทียมกันของเบนเน็ตต์