204512/บรรยาย 4

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย:

นายมนต์ชัย สารทอง

นายอุกฤษณ์ กุลดิลก 50653971

บทนี้จะกล่าวถึงทฤษฎีความน่าจะเป็นพื้นฐาน จากนั้นจะพิจารณาโครงสร้างข้อมูลแบบสุ่มสองแบบ คือ skip list และ universal hash

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]}

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

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

Y_{1}=

แต้มบนลูกเต๋าลูกที่ 1

Y_{2}=

แต้มบนลูกเต๋าลูกที่ 2

Y=

แต้มรวม

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

E[Y_{2}]=(1+2+3+...+6)\cdot {\frac {1}{6}}=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 .....=7

Linearity of Expectation

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

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

จาก Ex.1 ให้ตัวแปรสุ่ม 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 {\frac {n}{e}}

1+X\leq e^{X}

(1-{\frac {1}{n}})^{n}\leq (e^{-{\frac {1}{n}}})=e^{-1}

(1-{\frac {t}{n}})^{n}\leq (e^{-{\frac {t}{n}}})=e^{-t}

มีบอล m ลูก มีถัง n ถัง

ให้ $X=$ จำนวนถังว่าง

หา E[X]

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

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

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

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

ต้องโยนบอลกี่ลูก X จะเข้าใกล้ 0

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

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

E[X]\leq n(e^{-1})^{\frac {m}{n}}={\frac {n}{e^{\frac {m}{n}}}}

{\frac {n}{e^{\frac {m}{n}}}}=1

n=e^{\frac {m}{n}}

ln\ n={\frac {m}{n}}

m=n\ ln\ n

ให้ $m=cn\ ln\ n$

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

E[X]\leq {\frac {n}{n^{c}}}={\frac {1}{n^{c-1}}}

Thm: สำหรับตัวแปรสุ่ม X, Y; $E[X+Y]=E[X]+E[Y]$

Proof: $E[X+Y]=\sum \limits _{i=-\infty }^{\infty }{i\cdot Pr[X+Y=i]}$; $E[X+Y]=\sum \limits _{i=-\infty }^{\infty }{i\cdot [\sum \limits _{j=-\infty }^{\infty }{Pr[X=j,Y=i-j]}]}$; ให้ $i=a+b,j=b$; $E[X+Y]=\sum \limits _{a=-\infty }^{\infty }{\sum \limits _{b=-\infty }^{\infty }{(a+b)Pr[X=b,Y=a]}}$; $E[X+Y]=\sum \limits _{a=-\infty }^{\infty }{\sum \limits _{b=-\infty }^{\infty }{a\cdot Pr[X=b,Y=a]}}+\sum \limits _{a=-\infty }^{\infty }{\sum \limits _{b=-\infty }^{\infty }{b\cdot Pr[X=b,Y=a]}}$; $E[X+Y]=\sum \limits _{a=-\infty }^{\infty }{a[\sum \limits _{b=-\infty }^{\infty }{Pr[X=b,Y=a]}]}+\sum \limits _{b=-\infty }^{\infty }{b[\sum \limits _{a=-\infty }^{\infty }{Pr[X=b,Y=a]}]}$; $E[X+Y]=Pr[Y=a]+Pr[X=b]$; $E[X+Y]=E[X]+E[Y]$ ตามต้องการ

ตัวแปรสุ่มที่สำคัญ

1. ตัวแปรสุ่มแบบ indicator

มีตัวแปรสุ่มที่มีค่า 0 หรือ 1 สังเกตว่า

Proposition: ถ้า X เป็น Indicator R.V.

E[X]=\Pr[X=1]

Proof: จากนิยาม เราได้ว่า $E[X]=0\cdot \Pr[X=0]+1\cdot \Pr[X=1]=\Pr[X=1]$

2. ตัวแปรสุ่มแบบ binomial

มีการทดลองสำเร็จด้วยความน่าจะเป็น p

ทดลอง n ครั้ง แบบไม่ขึ้นต่อกัน

จำนวนครั้งของการทดลองที่สำเร็จ จะเป็นตัวแปรสุ่มแบบ

binomial => มี พารามิเตอร์ (n, p)

สำหรับตัวแปรสุ่ม X แบบ binomial ที่มี parameter (n, p)

ให้

X_{i}=1

ถ้าการทดลองครั้งที่ i สำเร็จ

X_{i}=0

กรณีอื่นๆ

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

ดังนั้น

E[X]=E[X_{1}+X_{2}+...+X_{n}]=\sum \limits _{i=1}^{n}{E[X_{i}]}=np

Pr[X=a]=C(n,a)\cdot p^{a}(1-p)^{n-a}

เมื่อ $C(n,a)$ แทนสัมประสิทธิ์ทวินาม ที่มีค่าเท่ากับ

{\frac {n!}{a!(n-a)!}}

ทั้งนี้เนื่องจาก ในการทดลอง n ครั้ง จะทดลองสำเร็จ a ครั้ง มีจำนวนรูปแบบที่เป็นไปได้ทั้งหมดเท่ากับ $C(n,a)$ แบบ และแต่ละแบบ มีความน่าจะเป็นที่จะเกิดขึ้นเท่ากับ $p^{a}(1-p)^{n-a}$

3. Geometric R.V.

มีเหรียญที่ออกหัวด้วยความน่าจะเป็น p

จำนวนครั้งที่โยนจนได้หัว เป็นตัวแปรสุ่มแบบ geometric [พารามิเตอร์ p]

ให้ r.v. X เป็นตัวแปรสุ่มแบบ geometric ที่มี parameter p

Pr[X=i]=p(1-p)^{i-1}

E[X]={\frac {1}{p}}

Skip List

#---------------->O---------->#
                  |
#---->O---------->O------->O->#
      |           |        |
#---->O------->O->O---->O->O->#
      |        |  |     |  |
#->O->O->O->O->O->O->O->O->O->#

ในการตัดสินใจว่าแต่ละโหนดจะมีความสูงขึ้นไปเท่าไหร่ จะใช้ความน่าจะเป็น เช่น การโยนเหรียญ เมื่อมีการเพิ่มข้อมูลใหม่ จะค้นหาจนกระทั่งพบช่องที่สามารถลงได้ จากนั้นก็ใช้ความน่าเป็น ในการดูว่าจะให้โหนดที่เพิ่มลงไปใหม่ควรจะมีความสูงเท่าไหร่

เมื่อกล่าวว่าเหตุการณ์ใดเกิดขึ้นด้วยความน่าจะเป็นสูง จะหมายความว่า เหตุการณ์ดังกล่าวขะไม่เกิดขึ้นด้วยความน่าจะเป็นไม่เกิน ${\frac {1}{n^{c}}}$ เมื่อ c>0 และ n คือ parameter ของระบบ

Lemma: skip list ที่มีข้อมูล n ตัวจะมีความสูง O(log n) ด้วยความน่าจะเป็นสูง

Proof: พิจารณาข้อมูล x ใดๆ ความน่าจะเป็นที่ระดับของ x>k

Pr[ระดับ x>k] = ${\frac {1}{2^{k}}}$

ให้เหตุการณ์ $A_{i}$ แทนเหตุการณ์ที่ข้อมูลตัวที่ i มีระดับมากกว่า k

Pr[ $A_{i}$ ] = ${\frac {1}{2^{k}}}$

ให้เหตุการณ์ A แทนเหตุการณ์ที่มีข้อมูลบางตัวมีระดับมากกว่า k

$A=\bigcup _{i=1}^{n}A_{i}$

ดังนั้น

$Pr[A]\leq \sum _{i=1}^{k}Pr[A_{i}]={\frac {n}{2^{k}}}$

ให้ K = c log n = O(log n) จะได้ว่า

Pr[ความสูงไม่เกิน k] = 1 - Pr[มีข้อมูลบางตัวมีระดับมากกว่า k] $\leq 1-{\frac {n}{2^{k}}}=1-{\frac {n}{2^{clogn}}}=1-{\frac {1}{n^{c-1}}}$

ถ้า c>2 , เหตุการณ์ดังกล่าวจะเกิดด้วยความน่าจะเป็นสูง

Pr[เดิน k node] =

k\cdot {\frac {1}{2^{k}}}

Theorem: Expected search time ของ skip list ที่มีข้อมูล n ตัว คือ O(log n)

Proof

ให้ H = ความสูง = O(log n)

ให้ $T_{i}$ เป็นเวลาที่ใช้ในชั้นที่ i

$T=\sum _{i=1}^{H}T_{i}$

$E[T]=E[\sum _{i=1}^{H}T_{i}]=\sum _{i=1}^{H}E[T_{i}]=O(\log n)$