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$

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 140025182
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:40:48 GMT


Sensitive client information

IP address: 158.108.32.49

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

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 188645427
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:40:48 GMT


Sensitive client information

IP address: 158.108.32.49

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

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 150803136
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:40:50 GMT


Sensitive client information

IP address: 158.108.32.49

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

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

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

---

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

---

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

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

หา 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}}$

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

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

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

ให้ $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.

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 175414965
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:40:53 GMT


Sensitive client information

IP address: 158.108.32.49

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

---

Proof: จากนิยาม เราได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 179995384
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:40:53 GMT


Sensitive client information

IP address: 158.108.32.49

$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=\sum \limits _{i=1}^{n}{X_{i}}$

ดังนั้น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 156737047
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:41:18 GMT


Sensitive client information

IP address: 158.108.32.49

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

เมื่อ แทนสัมประสิทธิ์ทวินาม ที่มีค่าเท่ากับ

ทั้งนี้เนื่องจาก ในการทดลอง n ครั้ง จะทดลองสำเร็จ a ครั้ง มีจำนวนรูปแบบที่เป็นไปได้ทั้งหมดเท่ากับ แบบ และแต่ละแบบ มีความน่าจะเป็นที่จะเกิดขึ้นเท่ากับ

3. Geometric R.V.

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

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

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

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

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

เมื่อกล่าวว่าเหตุการณ์ใดเกิดขึ้นด้วยความน่าจะเป็นสูง จะหมายความว่า เหตุการณ์ดังกล่าวขะไม่เกิดขึ้นด้วยความน่าจะเป็นไม่เกิน เมื่อ 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}$] =

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

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

ดังนั้น

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

Pr[ความสูงไม่เกิน k] = 1 - Pr[มีข้อมูลบางตัวมีระดับมากกว่า k]

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 90189228
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:41:26 GMT


Sensitive client information

IP address: 158.108.32.49

$\leq 1-{\frac {n}{2^{k}}}=1-{\frac {n}{2^{clogn}}}=1-{\frac {1}{n^{c-1}}}$

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

---

Pr[เดิน k node] =

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 21322219
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:40:54 GMT


Sensitive client information

IP address: 158.108.32.49

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

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

---

Proof

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

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

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 181109641
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:41:28 GMT


Sensitive client information

IP address: 158.108.32.49

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

---

Hashing

ในส่วนนี้ จะให้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 182485844
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:40:54 GMT


Sensitive client information

IP address: 158.108.32.49

${\mathbb {K} }=\{1,\ldots ,M\}$ แทนเซตของคีย์ และ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 59687298
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Jul 2026 23:40:55 GMT


Sensitive client information

IP address: 158.108.32.49

${\mathbb {I} }=\{1,\ldots ,N\}$ แืทนเซตของดัชนีในตาราง

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

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

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

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

Lemma

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

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

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

Proof

ให้

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

(1) ถ้า

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

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 ที่

$ay+b\equiv 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}}$ คู่