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)$

---

Hashing

ในส่วนนี้ จะให้ ${\mathbb {K} }=\{1,\ldots ,M\}$ แทนเซตของคีย์ และ ${\mathbb {I} }=\{1,\ldots ,N\}$ แืทนเซตของดัชนีในตาราง

hash function $h:{\mathbb {K} }\rightarrow {\mathbb {I} }$ จะส่งคีย์ไปยังตำแหน่งในตาราง

นิยาม: Family of hash function ${\mathcal {H}}$ เป็น 2-universal ถ้า สำหรับทุก ๆ สมาชิก $x,\ y\in \ {\mathbb {K} }$ ที่ $x\neq y$,

$\Pr _{h\in H}[h(x)\neq h(y)]\leq {\frac {1}{N}}$

เลือกจำนวนเฉพาะ p > M
ให้ $h_{ab}$ สำหรับ $a\in {1,...,p-1}$ และ $b\in {0,...,p-1}$

$h_{ab}(x)=((ax+b){\bmod {p}}){\bmod {N}}$

$|H|=(p-1)p$

Lemma

สำหรับ x, y ที่ $x\neq y$

จำนวน $h_{ab}\in H$ ที่

$h_{ab}(x)=h_{ab}(y)$

ไม่เกิน ${\frac {(p-1)p}{N}}$ ตัว

Proof

ให้

$ax+b\equiv r{\pmod {p}}$

$ay+b\equiv s{\pmod {p}}$

(1) ถ้า $x\neq y,r\not \equiv s{\pmod {p}}$

พิสูจน์ด้วยข้อขัดแย้ง

assume

$ax\equiv ay{\pmod {p}}$

x = y

(2) ถ้า $h_{ab}(x)=h_{ab}(y)$ แล้ว $r\equiv s{\pmod {N}}$

จำนวนคู่ r, s ที่สอดคล้อง $\leq p[{\frac {p}{N}}-1]\leq {\frac {p(p-1)}{N}}$

(3) พิจารณา คู่ r, s คู่หนึ่ง ที่ $r\equiv s{\pmod {N}}$

จะหาค่า a, b ที่

$ax+b\equiv r{\pmod {p}}$

$ay+b\equiv s{\pmod {p}}$

$ax-ay\equiv r-s{\pmod {p}}$

$a(x-y)\equiv r-s{\pmod {p}}$

$a\equiv (r-s)\cdot (x-y)^{-1}{\pmod {p}}$

แต่ละคู่ r, s จะมี a, b คู่เดียว

จาก (1), (2), (3), มี a, b ไม่เกิน ${\frac {(p-1)p}{N}}$ คู่