204512/บรรยาย 4

ขออภัย Lecture Note ที่ท่านเรียก ยังไม่เปิดให้ใช้บริการค่ะ

Balls & Bins

• มีถัง $n$ ถัง
• มีบอล $n$ ลูก

${\rm {Pr[first\ bin\ is\ empty]=}}\left({{\rm {1-}}{\frac {\rm {1}}{\rm {n}}}}\right)^{\rm {n}}$

Random Variable

นิยาม

สำหรับตัวแปรสุ่ม $X$

$\sum \limits _{i=-\infty }^{\infty }{i\cdot \Pr[X=i]}$

---

มีลูกเต๋า 2 ลูก โยนทีละลูก

ให้ตัวแปรสุ่ม

$Y_{1}=$แต้มบนลูกเต๋าลูกที่ 1

$Y_{2}=$แต้มบนลูกเต๋าลูกที่ 2

$Y=$แต้มรวม

$E[Y_{1}]=(1+2+3+...+6)\cdot {\frac {1}{6}}$

$E[Y_{1}]=3.5$

$E[Y_{2}]=3.5$

$E[Y]=2\cdot {\frac {1}{6}}\cdot {\frac {1}{6}}+3\cdot 2\cdot {\frac {1}{36}}+4\cdot 3\cdot {\frac {1}{36}}+5\cdot .....$

$E[Y]=7$

$E[Y]=E[Y_{1}+Y_{2}]=E[Y_{1}]+E[Y_{2}]$

Linearity of Expectation

สำหรับตัวแปรสุ่ม $X,Y$

$E[X+Y]=E[X]+E[Y]$

ให้ตัวแปรสุ่ม $X$ แทนจำนวนถังว่าง

$E[X]=?$

ให้ตัวแปรสุ่ม

$X_{i}=1$ ถ้าถังที่ i ว่าง

$X_{i}=0$ กรณีอื่นๆ

สังเกตว่า

$X=\sum \limits _{i=1}^{n}{X_{i}}$

ดังนั้น

$E[X]=E[\sum \limits _{i=1}^{n}{X_{i}}]$

$E[X]=\sum \limits _{i=1}^{n}{E[X_{i}]}$ โดย Linearity of Expectation

---

$E[X_{i}]=0\cdot Pr[X_{i}=0]+1\cdot Pr[X_{i}=1]$

$E[X_{i}]=Pr[X_{i}=1]$

$E[X_{i}]=(1-{\frac {1}{n}})^{n}$

$E[X]=\sum \limits _{i=1}^{n}{E[X_{i}]}$

$E[X]=\sum \limits _{i=1}^{n}{(1-{\frac {1}{n}})^{n}}$

$E[X]=n(1-{\frac {1}{n}})^{n}$

$E[X]\approx$