บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
จดบันทึกคำบรรยายโดย:
- นายมนต์ชัย สารทอง
- นายอุกฤษณ์ กุลดิลก 50653971
บทนี้จะกล่าวถึงทฤษฎีความน่าจะเป็นพื้นฐาน จากนั้นจะพิจารณาโครงสร้างข้อมูลแบบสุ่มสองแบบ คือ skip list และ universal hash
Balls & Bins
- มีถัง n ถัง
- มีบอล n ลูก
![{\displaystyle {\rm {Pr[first\ bin\ is\ empty]=}}\left({{\rm {1-}}{\frac {\rm {1}}{\rm {n}}}}\right)^{\rm {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/872ae7759506a112be7071c0d265611466e058b1)
Random Variable
- นิยาม
- สำหรับตัวแปรสุ่ม X
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle \sum \limits _{i=-\infty }^{\infty }{i\cdot \Pr[X=i]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e3c91784fe9c9663e402366d27ca41b9012a195)
Ex.1 มีลูกเต๋า 2 ลูก โยนทีละลูก
ให้ตัวแปรสุ่ม
-
Wikimedia Error
Error
Too many requests (f061ab2)
แต้มบนลูกเต๋าลูกที่ 1
-
Wikimedia Error
Error
Too many requests (f061ab2)
แต้มบนลูกเต๋าลูกที่ 2
-
Wikimedia Error
Error
Too many requests (f061ab2)
แต้มรวม
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[Y_{1}]=(1+2+3+...+6)\cdot {\frac {1}{6}}=3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f77b660319b5ac06155587ebf8aea3cc6b6c4db)
![{\displaystyle E[Y_{2}]=(1+2+3+...+6)\cdot {\frac {1}{6}}=3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/844ed0f7193d0ef657f6bcccf2eef0f6e44ce5df)
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5609739b81381559b0049f44f8e8deb79cce8b01)
Linearity of Expectation
สำหรับตัวแปรสุ่ม X, Y
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X+Y]=E[X]+E[Y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2251900ec2b03db1d6f870336155a2a09ff7f1)
จาก Ex.1 ให้ตัวแปรสุ่ม X แทนจำนวนถังว่าง
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X]=?}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fed450511cffa0a2dc75677b3834b8e8eac00989)
ให้ตัวแปรสุ่ม
-
Wikimedia Error
Error
Too many requests (f061ab2)
ถ้าถังที่ i ว่าง
กรณีอื่นๆ
สังเกตว่า
-
Wikimedia Error
Error
Too many requests (f061ab2)
ดังนั้น
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X]=E[\sum \limits _{i=1}^{n}{X_{i}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/801de500a1e2efcb14962d97f5b66467a5cfad32)
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X]=\sum \limits _{i=1}^{n}{E[X_{i}]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf4ad4e1484061a7df295923212bd111778bf5cb)
โดย Linearity of Expectation
![{\displaystyle E[X_{i}]=0\cdot Pr[X_{i}=0]+1\cdot Pr[X_{i}=1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3760a6ac32ce42b59374146bacff546dcb2c4692)
![{\displaystyle E[X_{i}]=Pr[X_{i}=1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4a09691e19daaccd3bfd412a6d0f965794b7f68)
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X_{i}]=(1-{\frac {1}{n}})^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d51e4c1cb6e93ec8a9b0e4f0e9029a7cb2d54e3)
![{\displaystyle E[X]=\sum \limits _{i=1}^{n}{(1-{\frac {1}{n}})^{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0557ac0e512b3f4a4c7596fee061461dc318d88)
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X]=n(1-{\frac {1}{n}})^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/201a81a125622b9c3f670015530f328eec2f407e)
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X]\approx {\frac {n}{e}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62ae210f164cc3574d76e37624609fd08df4cf7e)
-
Wikimedia Error
Error
Too many requests (f061ab2)
-
Wikimedia Error
Error
Too many requests (f061ab2)
-
Wikimedia Error
Error
Too many requests (f061ab2)
มีบอล m ลูก
มีถัง n ถัง
ให้ 
จำนวนถังว่าง
หา E[X]
-
Wikimedia Error
Error
Too many requests (f061ab2)
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X]=\sum \limits _{i=1}^{n}{(1-{\frac {1}{n}})^{m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ac8d92a4cf6d0c157d83c76f3a2d9d01644bc10)
![{\displaystyle E[X]=n(1-{\frac {1}{n}})^{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b99da437eb4248c993a8b471f5520595d2c30c2c)
ต้องโยนบอลกี่ลูก X จะเข้าใกล้ 0
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X]=[n(1-{\frac {1}{n}})^{n}]^{\frac {m}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b102b3aaf43f9c3e911fead1dcf4f3f9c4a444d)
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X]\leq n(e^{-1})^{\frac {m}{n}}={\frac {n}{e^{\frac {m}{n}}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37bd3e4e1b2a73d962acfe9cd9ea9b3b2bb47869)
-
Wikimedia Error
Error
Too many requests (f061ab2)
-
Wikimedia Error
Error
Too many requests (f061ab2)
-
Wikimedia Error
Error
Too many requests (f061ab2)
ให้
![{\displaystyle E[X]=n(1-{\frac {1}{n}})^{cn\ ln\ n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/951924294a8c657f690973fdb0080bc312bf5ab0)
- Thm
- สำหรับตัวแปรสุ่ม X, Y
- Proof
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X+Y]=\sum \limits _{i=-\infty }^{\infty }{i\cdot [\sum \limits _{j=-\infty }^{\infty }{Pr[X=j,Y=i-j]}]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7ea0acc1a12bf4bda04b7a363aa239e5b302cba)
- ให้
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle 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]}]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cdf8f500331398d760391cf25291846ae13b5c0)
- ตามต้องการ
ตัวแปรสุ่มที่สำคัญ
1. ตัวแปรสุ่มแบบ indicator
มีตัวแปรสุ่มที่มีค่า 0 หรือ 1 สังเกตว่า
Proposition: ถ้า X เป็น Indicator R.V.
Proof: จากนิยาม เราได้ว่า
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle E[X]=0\cdot \Pr[X=0]+1\cdot \Pr[X=1]=\Pr[X=1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81d0d41e711bf017e80e36dc0fbe634cc5377eff)
2. ตัวแปรสุ่มแบบ binomial
- มีการทดลองสำเร็จด้วยความน่าจะเป็น p
- ทดลอง n ครั้ง แบบไม่ขึ้นต่อกัน
- จำนวนครั้งของการทดลองที่สำเร็จ จะเป็นตัวแปรสุ่มแบบ
- binomial => มี พารามิเตอร์ (n, p)
สำหรับตัวแปรสุ่ม X แบบ binomial ที่มี parameter (n, p)
ให้
- ถ้าการทดลองครั้งที่ i สำเร็จ
- กรณีอื่นๆ
-
Wikimedia Error
Error
Too many requests (f061ab2)
ดังนั้น
-
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle Pr[X=a]=C(n,a)\cdot p^{a}(1-p)^{n-a}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f2d422c3102289f0149a89780f9bad8b5bdb55d)
เมื่อ แทนสัมประสิทธิ์ทวินาม ที่มีค่าเท่ากับ
Wikimedia Error
Error
Too many requests (f061ab2)
ทั้งนี้เนื่องจาก ในการทดลอง n ครั้ง จะทดลองสำเร็จ a ครั้ง มีจำนวนรูปแบบที่เป็นไปได้ทั้งหมดเท่ากับ 
แบบ และแต่ละแบบ มีความน่าจะเป็นที่จะเกิดขึ้นเท่ากับ
3. Geometric R.V.
- มีเหรียญที่ออกหัวด้วยความน่าจะเป็น p
- จำนวนครั้งที่โยนจนได้หัว เป็นตัวแปรสุ่มแบบ geometric [พารามิเตอร์ p]
- ให้ r.v. X เป็นตัวแปรสุ่มแบบ geometric ที่มี parameter p
![{\displaystyle Pr[X=i]=p(1-p)^{i-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/421486504d4498fb008c9b838202cac98ac73faa)
Skip List
#---------------->O---------->#
|
#---->O---------->O------->O->#
| | |
#---->O------->O->O---->O->O->#
| | | | |
#->O->O->O->O->O->O->O->O->O->#
ในการตัดสินใจว่าแต่ละโหนดจะมีความสูงขึ้นไปเท่าไหร่ จะใช้ความน่าจะเป็น เช่น การโยนเหรียญ เมื่อมีการเพิ่มข้อมูลใหม่ จะค้นหาจนกระทั่งพบช่องที่สามารถลงได้ จากนั้นก็ใช้ความน่าเป็น ในการดูว่าจะให้โหนดที่เพิ่มลงไปใหม่ควรจะมีความสูงเท่าไหร่
เมื่อกล่าวว่าเหตุการณ์ใดเกิดขึ้นด้วยความน่าจะเป็นสูง จะหมายความว่า เหตุการณ์ดังกล่าวขะไม่เกิดขึ้นด้วยความน่าจะเป็นไม่เกิน
Wikimedia Error
Error
Too many requests (f061ab2)
เมื่อ c>0 และ n คือ parameter ของระบบ
Lemma: skip list ที่มีข้อมูล n ตัวจะมีความสูง O(log n) ด้วยความน่าจะเป็นสูง
Proof: พิจารณาข้อมูล x ใดๆ ความน่าจะเป็นที่ระดับของ x>k
- Pr[ระดับ x>k] =
ให้เหตุการณ์ 
แทนเหตุการณ์ที่ข้อมูลตัวที่ i มีระดับมากกว่า k
- Pr[] =
ให้เหตุการณ์ A แทนเหตุการณ์ที่มีข้อมูลบางตัวมีระดับมากกว่า k
ดังนั้น
ให้ K = c log n = O(log n) จะได้ว่า
- Pr[ความสูงไม่เกิน k] = 1 - Pr[มีข้อมูลบางตัวมีระดับมากกว่า k]
ถ้า c>2 , เหตุการณ์ดังกล่าวจะเกิดด้วยความน่าจะเป็นสูง
- Pr[เดิน k node] =
Wikimedia Error
Error
Too many requests (f061ab2)
Theorem: Expected search time ของ skip list ที่มีข้อมูล n ตัว คือ O(log n)
Proof
- ให้ H = ความสูง = O(log n)
- ให้ เป็นเวลาที่ใช้ในชั้นที่ i
-
Wikimedia Error
Error
Too many requests (f061ab2)
Hashing
ในส่วนนี้ จะให้
Wikimedia Error
Error
Too many requests (f061ab2)
แทนเซตของคีย์
และ แืทนเซตของดัชนีในตาราง
hash function
Wikimedia Error
Error
Too many requests (f061ab2)
จะส่งคีย์ไปยังตำแหน่งในตาราง
นิยาม: Family of hash function เป็น 2-universal ถ้า สำหรับทุก ๆ
สมาชิก ที่
Wikimedia Error
Error
Too many requests (f061ab2)
,
Wikimedia Error
Error
Too many requests (f061ab2)
![{\displaystyle \Pr _{h\in H}[h(x)\neq h(y)]\leq {\frac {1}{N}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef1c4089c1503714b6a3c8af6a8c35eb1d324880)
เลือกจำนวนเฉพาะ p > M
ให้ สำหรับ และ
Wikimedia Error
Error
Too many requests (f061ab2)
-
Wikimedia Error
Error
Too many requests (f061ab2)
- Lemma
- สำหรับ x, y ที่
- จำนวน ที่
- ไม่เกิน
ตัว
- Proof
- ให้
-
Wikimedia Error
Error
Too many requests (f061ab2)
-
Wikimedia Error
Error
Too many requests (f061ab2)
- (1) ถ้า
Wikimedia Error
Error
Too many requests (f061ab2)
- พิสูจน์ด้วยข้อขัดแย้ง
- assume
- x = y
- (2) ถ้า แล้ว
- จำนวนคู่ r, s ที่สอดคล้อง
- (3) พิจารณา คู่ r, s คู่หนึ่ง ที่
Wikimedia Error
Error
Too many requests (f061ab2)
- จะหาค่า a, b ที่
-
Wikimedia Error
Error
Too many requests (f061ab2)
-
Wikimedia Error
Error
Too many requests (f061ab2)
-
Wikimedia Error
Error
Too many requests (f061ab2)
- แต่ละคู่ r, s จะมี a, b คู่เดียว
จาก (1), (2), (3), มี a, b ไม่เกิน คู่
