Saturday, August 12, 2006

การสร้างรากฐานรัฐด้วยการศึกษา

ที่แอลเอ หน้าประตูเข้าสวนกุหลาบ หน้าบริเวณจัดแสดงใหญ่ ที่เป็นที่ตั้งของพิพิธภัณฑ์ประวัิติศาสตร์ธรรมชาติ (Natural History Museum) และศูนย์วิทยาศาสตร์ (Science Center) มีเสาประตูสองอันสลักเป็นประโยคว่า

เสาประตูซ้าย: "THE END OF ALL GOOD GOVERNMENT IS THE HAPPINESS OF THE PEOPLE"

เสาประตูขวา: "THE FOUNDATION OF EVERY STATE IS ITS EDUCATION OF ITS YOUTH"

บังเอิญเหลือเกินที่พกหนังสือ "หลังโครงสร้างนิยม: ฉบับย่อ" เขียนโดยแคทเธอรีน เบลซีย์ แปลโดยอภิญญา เฟื่องฟูสกุล ติดมือไปด้วย แล้วก็บังเอิญเช่นกันที่อ่านเจอข้อความนี้:
"[...] ประเด็นหลักของอัลตูแซร์ก็คือโรงเรียนและมหาวิทยาลัยไม่เพียงผลิตคนหนุ่มสาวป้อนตลาดแรงงานทุกระดับของโครงสร้างเศรษฐกิจเท่านั้น ทว่าในกระบวนการสอนอ่านเขียนและคิดเลข ก็ผลิตคำสอนเรื่องความเชื่อฟัง ความสุภาพอ่อนน้อม จิตวิทยาเบื้องต้น [...] คุณค่าของประชาธิปไตยเสรีนิยม วิธีออกคำสั่ง และวิธีทำงานรับใช้ชุมชน กล่าวสั้น ๆ ก็คือ สถาบันการศึกษาทำให้วินัย โดยเฉพาะวินัยในตัวเองหยั่งรากฝังลึกในความคิดและสนับสนุนให้นักเรียนออกไปสู่สังคมและผดุงรักษาสภาพต่าง ๆ ที่เป็นอยู่ 'ด้วยตัวของพวกเขาเอง"
อืม พอได้อ่านข้อความข้างล่างแล้ว การตีความและการทำความเข้าใจประโยคที่สองข้างต้นก็คงจะเหมือนเดิมไม่ได้แล้ว

Sunday, June 18, 2006

เพลงเก่า-เพลงใหม่

(exteen หยุดให้บริการไปหลายวัน เขียนที่นี่ก่อนแล้วกัน---คงไม่มีใครมาอ่าน)

ใหม่

ซีดีใหม่ที่เพิ่งซื้อมา มีศิลปินสองกลุ่ม (คน) ที่ชื่นชอบมากทั้งคู่ มาทำเพลงด้วยกัน ในอัลบั้ม Give#1

เพลงชื่อ "แสงและเงา" ร้องโดยญารินดา เนื้อร้องโดย วาสิต มุกดาวิจิตร (day tripper) ทำนอง/เรียบเรียงโดยทวนทอง นิยมชาติ (day tripper) เนื้อเพลงที่เขียนโดยอู วาสิต มุกดาวิจิตร นั้นล่องลอย แล้วก็กัดกร่อนความรู้สึกแบบแปร่งแปลก วลีต่อวลีที่เหมือนจะไม่เกี่ยวกัน แต่รวมกันได้ความหมายแบบเฉพาะตัว เป็นเอกลักษณ์ของเนื้อที่เขาแต่ง ตั้งแต่สมัยที่อยู่วงครับแล้ว ส่วนญารินดานี่ชอบมานานแล้ว ยิ่งมาทำเพลงเองก็ทำได้เก๋มาก

อัลบั้มชุดนี้ก็ทำให้ได้ฟังเพลงของอพาร์ตเมนต์คุณป้า ซึ่งเป็นเพลงประหลาดอีกเพลงหนึ่ง คนร้องจะไปฆ่ากามเทพ โยนคันศรทิ้ง ถ้าเธอต้องการ

เก่า

นั่งรถไปศรีราชา ฟังเพลงในรถตู้เป็นเพลงเก่ามาก ของนกแล "อย่าลืมน้องสาว" เพลงขึ้นว่า "ข้าวในนาแลเหลียว มือน้อยคอยเคียว มาเกี่ยวเก็บไป..." (ฟังได้ที่นี่)

"ไปเป็นด๊อกเตอร์ หรือเป็นนักศึกษาที่ไหน เป็นคุณนายบ้านใด บ้านใด ส่งเงินมามากพอแล้ว อย่าให้ส่งตัวพี่ไป หรือรวยแล้วมีน้องใหม่ลงลืมน้องสาว"

ตอนเด็ก ๆ ฟังก็ไม่ได้คิดอะไร แต่ฟังอีกที เพลงนี่จะมีความหมายอื่น ๆ หรือเปล่า? พี่สาวที่กล่าวถึง (เธอเป็นชาวเขา) ไปในเมืองไปทำอะไร? เธอจะไปเป็นด๊อกเตอร์ได้หรือเปล่า? แล้วตอนนี้ล่ะ

คงเป็นเพลงคลาสสิกเพลงหนึ่งเลยทีเดียว

หมายเหตุ: อ้อ.. ระหว่างหา ค้น ๆ เจอว่า นกแล กลับมาอีกครั้ง ชื่อ ดอยเต่าดอตคอม

Friday, April 14, 2006

การแก้สมการเวียนบังเกิดเชิงเส้น

พิจารณาความสัมพันธ์เวียนบังเกิด (recurrence relations): $F(n) = A\cdot F(n-1) + B\cdot F(n-2)$ และมีค่าเริ่มต้น $F(0)$ และ $F(1)$

ข้อสังเกต 1: ถ้าฟังก์ชัน $f$ และ $g$ สอดคล้องกับความสัมพันธ์เวียนบังเกิดข้างต้น $f+g$ ก็จะสอดคล้องด้วย
บทพิสูจน์: พิสูจน์โดยการแทนค่า
[X]

ข้อสังเกต 2:
ฟังก์ชันดังกล่าวเป็นฟังก์ชัน exponential ถ้า $A> 0$ และ $B\geq 0$
บทพิสูจน์:
(lowerbound): เราจะแสดงว่า $F$ มีค่ามากกว่า exponential function บางอัน

สามารถตรวจสอบได้ว่า $F$ เป็นฟังก์ชันไม่ลดลง นั่นคือ $F(n')\geq F(n)$ เมื่อ $n'\geq n$

ให้ $k$ เป็นจำนวนเต็มที่มากกว่า $2\cdot(2/A)$ (จริง ๆ ควรใช้สัญลักษณ์ ceiling แต่ยังหาไม่เจอว่าทำใน ASCIIMathMLได้อย่างไร) พิจารณา
$F(n+k)=AF(n+k-1) + BF(n+k-2) $
$= AF(n+k-1) + AF(n+k-3) + BF(n+k-4)$
$= AF(n+k-1) + AF(n+k-3) + AF(n+k-5) + BF(n+k-6)$
$=\sum_{i=1}^{k//2} AF(n+k+1-2i) + BF(n) \geq (k/2)\cdot AF(n+1) \geq 2F(n)$
นั่นคือ $F(n+k)\geq 2F(n)$ หรือ $F(n)\geq C\cdot 2^(n//k)$ สำหรับค่า $C$ บางค่า

(upperbound): เราจะแสดงว่า $F$ มีค่าไม่เกิน exponential function บางอันเช่นกัน
$F(n)=AF(n-1)+BF(n-2)\leq AF(n-1)+BF(n-1)=(A+B)F(n-1)$ หรือ
$F(n)\leq C'\cdot (A+B)^n$ สำหรับค่าคงที่ $C'$ บางค่า
[X]

ดังนั้นวิธีการที่เราจะพิจารณาต่อไปก็คือการพยายามหา exponential function ที่สอดคล้องกับเงื่อนไขดังกล่าว

คราวหน้ามาต่อครับ...

Monday, April 10, 2006

บทกวีแบบฟิบ

ฝน
ฟ้า
อากาศ
สุดแสนเงียบ
ฉันนอนอยู่ในห้อง
รอคอยเวลาที่จะตื่นขึ้น
เพียงเพื่อพบกับวันใหม่ที่รออยู่อย่างไม่เปลี่ยนแปลง

บทกวีรูปแบบใหม่ ที่ชื่อว่าฟิบ (เสนอโดย Gregory K. ผมอ่านเจอจาก Geomblog) แต่ละบรรทัดจะประกอบด้วยจำนวนพยางค์เป็นไปตามเลขฟิโบนัชชี คือ 1, 1, 2, 3, 5, 8, 13, 21, ... ที่มีลักษณะคือตัวเลขตัวใด ๆ มีค่าเท่ากับตัวก่อนหน้าสองตัวบวกกัน หรือ ถ้าเขียนเป็นสูตรคณิตศาสตร์ก็คือ $F(1) = 1$, $F(2) = 1$, $F(n) = F(n-1) + F(n-2) $ กว่าจะเขียนได้ห้าบรรทัดก็แทบแย่แล้ว

ลองอีกอัน...

อิ่ม
ง่วง
อยากนอน
ท้องที่อิ่ม
มันทำให้สมอง
หยุดและไม่อยากคิดอะไรอีก

แล้ว closed form ของ $F(i)$ เป็นเช่นใด?

ลำดับฟิโบนัชชีนี้ เป็นรูปหนึ่งของ linear recurrence ซึ่งมีรูปทั่วไปเป็น $x_n = Ax_(n-1)+Bx_(n-2)$ เมื่อ $n\geq 3$ และในกรณีนี้เรามี $x_1=x_2=1$

ขอเอาเรื่องนี้แทรก Central limit theorem สักหน่อยนะครับ... ไว้มาต่อพรุ่งนี้ครับ

Saturday, April 08, 2006

ทฤษฎีบทขีดจำกัดกลาง (1)

กฎแห่งจำนวนมาก บอกกับเราว่า ถ้าข้อมูลตัวอย่างที่สุ่มมามีจำนวนมาก ค่าเฉลี่ยที่ได้ก็จะใกล้กับค่าเฉลี่ยจริง ๆ ทฤษฎีบทขีดจำกัดกลาง (Central Limit Theorem) ให้ข้อมูลที่มากขึ้นกับเรา นั่นคือ ลักษณะของการแจกแจงของค่าเฉลี่ยที่ได้เป็นอย่างไร

Central Limit Theorem กล่าวว่าการแจกแจง (distribution) ของค่าเฉลี่ยเมื่อจำนวนข้อมูลที่สุ่มมามีจำนวนมากจะเข้าใกล้การแจกแจงปกติ (Normal distribution) ซึ่งจะมีรูปโค้งเป็นแบบระฆังคว่ำ (สุดฮิต) ดังรูปด้านล่าง


(รูปจากวิกิพีเดีย)

ในรูปแสดงกราฟการแจกแจงปกติที่ค่าเฉลี่ยและความแปรปรวนต่าง ๆ กัน

ค่าความหนาแน่นน่าจะเป็นของตัวแปรสุ่มที่มีการแจกแจงปกติซึ่งมีค่าเฉลี่ย $\mu$ และความแปรปรวน $\sigma^2$ คือ $f(x) = 1/(\sigma\sqrt((2\pi)))\exp(-\frac{(x-\mu)^2}{2\sigma^2})$

การแจกแจงปกตินี้ถูกนิยามขึ้นโดย Abraham de Moivre (ราชบัณฑิตเรียกเขาว่า เดอมัวฟวร์) ซึ่งใช้การแจกแจงนี้ในการประมาณค่าของการแจกแจงทวินามของจำนวนครั้งที่โยนเหรียญได้หัวจากการโยนเหรียญที่เป็นกลาง 1800 ครั้ง จากนั้น Laplace ได้ขยายทฤษฎีของ de Moivre ให้ใช้ได้กับการแจกแจงทวินามใด ๆ

ถ้าเราทดลองแบบสุ่มไม่ขึ้นต่อกัน $n$ ครั้ง แต่ละครั้งจะทดลองสำเร็จด้วยความน่าจะเป็น $p$ ตัวแปรสุ่มที่นับจำนวนครั้งของการทดลองสำเร็จจะมี การแจกแจงทวินาม ยกตัวอย่างเช่นจำนวนที่ได้หัวจากการโยนเหรียญที่เป็นกลาง 1800 ครั้ง มีการแจกแจงแบบทวินาม ที่มีค่า $n=1800$ และ $p=0.5$ เป็นต้น

ครั้งต่อไปเราจะพิสูจน์ทฤษฎีบทท้องถิ่นเดอมัวฟวร์-ลาปลาส (local theorem of DeMoivre-Laplace)

Friday, April 07, 2006

กฎแห่งจำนวนมาก (2)

เมื่อเรามีอสมการของเชบิเชฟแล้ว เราสามารถพิสูจน์ กฎแห่งจำนวนมาก ได้ไม่ยากนัก

ก่อนอื่นเราต้องการหาค่าความแปรปรวนของผลรวมของตัวแปรสุ่มก่อน พิจารณาตัวแปรสุ่ม $X$ และ $Y$ เราจะใช้ความจริง (ที่อาจจะไปพิสูจน์กันในวันหลัง)

ความจริง 1 (Linearity of Expectation): $E[X+Y] = E[X] + E[Y]$

ความจริง 2 (ผลคูณของตัวแปรสุ่มที่ไม่ขึ้นต่อกัน): ถ้า $X$ และ $Y$ ไม่ขึ้นต่อกัน เราจะได้ว่า $E[X\cdot Y] = E[X]\cdot E[Y]$

สำหรับตัวแปรสุ่ม $X$ ใด ๆ ค่าความแปรปรวนมีนิยามเป็น $Var[X]=E[X^2]-E[X]^2$ ดังนั้น

$Var[X+Y]=E[(X+Y)^2] - E[X+Y]^2 $
$= E[X^2 + 2X\cdot Y+Y^2]-(E[X]+E[Y])^2$
$= E[X^2] + E[2X\cdot Y]+ E[Y^2]-E[X]^2-2E[X]E[Y] - E[Y]^2$ (ใช้ความจริง 1 ในการกระจาย)

จากความจริง 2: เราจะได้ว่า E[2X\cdot Y] = 2E[X\cdot Y] = 2E[X]E[Y] นั่นคือ

$Var[X+Y]=E[X^2] + E[Y^2] - E[X]^2 - E[Y]^2$
$= (E[X^2] - E[X]^2) + (E[Y^2] - E[Y]^2)$
$= Var[X] + Var[Y]$

นั่นคือ:

ความจริง 3: ถ้าตัวแปรสุ่ม $X$ และ $Y$ ไม่ขึ้่นต่อกัน $Var[X+Y] = Var[X] + Var[Y]$

ดังนั้น, ถ้า $X$ เป็นผลรวมของตัวแปรสุ่ม $X_1,X_2,\ldots,X_n$ ที่ไม่ขึ้นต่อกัน แต่ละตัวมีค่าคาดหวัง $\mu$ และมีความแปรปรวน $\sigma^2$ เราจะได้ว่า

$Var[X]=Var[\sum_{i=1}^n X_i] = n\sigma^2$

เรายังต้องการความจริงอีกข้อหนึ่ง

ความจริง 4: สำหรับค่าคงที่ $c$ ใดๆ $Var[cX] = c^2 Var[X]$

หมายเหตุ: อาจจะสงสัยว่า $Var[2X] = Var[X+X]$ น่าจะเท่ากับ $2Var[X]$ ตามความจริง 3 แต่จากข้างบนเราจะได้ว่า $Var[X+X] = Var[2X] = 4Var[X]$ นั่นเป็นเพราะ $X$ กับ $X$ นั้นไม่ใช่ตัวแปรสุ่มที่ไม่ขึ้นต่อกัน

บทพิสูจน์ (กฎแห่งจำนวนมากแบบอ่อน):
พิจารณา $X_n=(X_1+X_2+\cdots+X_n)//n$ จากความจริงข้างต้น เราทราบว่า $E[X_n] = (E[X_1]+E[X_2]+\cdots+E[X_n])//n = \mu$ และ $Var[X_n] = \frac{1}{n^2}Var[X_1+X_2+\cdots+X_n] = \frac{n}{n^2}\sigma^2 = \sigma^2/n$

เราต้องการหา
$Pr[|X_n-\mu|<\epsilon] =1-Pr[|X_n-\mu|\geq\epsilon]$ พิจารณา $Pr[|X_n-\mu|\geq\epsilon]$ ตามอสมการเชบิเชพ เราจะได้ว่า $Pr[|X_n-\mu|\geq\epsilon]\leq (\sigma^2//n)/epsilon^2 = \sigma^2/(n\cdot\epsilon^2)$ นั่นคือ $\lim_{n\rightarrow\infty}\Pr[|\bar{X}_n-\mu|<\epsilon] \geq 1-\sigma^2/(n\cdot\epsilon^2)=1$ ตามต้องการ
[X]

Tuesday, April 04, 2006

เกี่ยวกับปัญหา P กับ NP

ปัญหานี้เป็นปัญหาเชิงทฤษฎีที่สำคัญที่สุดและโด่งดังที่สุดของวิทยาการคอมพิวเตอร์ หลายคนบอกว่าวิทยาการคอมพิวเตอร์เชิงทฤษฎีไม่สามารถจะพูดเกี่ยวกับผลงานของสาขาตนเองได้มากนัก เพราะแม้แต่ปัญหาที่เป็นพื้นฐานที่สุด เรายังไม่สามารถตอบได้เลย

สำหรับคนที่เคยผ่านหูผ่านตาปัญหาชื่อประมาณนี้มาบ้าง ขอผมทบทวนสักหน่อยโดยใช้ภาษาที่ไม่เป็นทางการนัก

เวลาผมกล่าวถึง "ปัญหา" ผมหมายถึงปัญหาที่ต้องการคำตอบว่า "ใช่" หรือ "ไม่ใช่" เช่น ปัญหาจำนวนเฉพาะ ที่ให้จำนวนเต็มบวกมาหนึ่งจำนวน แล้วถามว่าจำนวนหนึ่งเป็นจำนวนเฉพาะหรือไม่?
  • ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา P คือปัญหาที่เรามีวิธีที่หาคำตอบได้อย่างมีประสิทธิภาพ
  • ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา NP คือปัญหาที่ถ้าคำตอบของปัญหาหนึ่ง ๆ คือใช่ เรามีวิธีการที่จะยืนยันคำตอบนั้นอย่างมีประสิทธิภาพ
(อ่านเพิ่มที่วิกิพีเดียไทย)

ปัญหานี้เป็นเรื่องพื้นฐานมาก ๆ ของการหาคำตอบ กับการยืนยันคำตอบ ซึ่งหลาย ๆ คนเชื่อกันว่า อย่างหลังน่าจะง่ายกว่า

ผมจำได้ว่าได้อ่านจาก โพล ที่ทำโดย William Gasarch เกี่ยวกับปัญหา P และ NP คำตอบหนึ่งของ Luca Trevisan ในโพลนั้น (ที่หลาย ๆ คนคงคิดคล้าย ๆ กับเขา) ก็คือ เขากลัวว่าการพิสูจน์ปัญหาดังกล่าวจะเกิดจากการที่บางคนสังเกตเห็นความเกี่ยวข้องบางอย่างระหว่างปัญหานี้กับคณิตศาสตร์แปลก ๆ แล้วก็พิสูจน์ปัญหานี้ออกมาโดยการทำงานในคณิตศาสตร์แปลก ๆ นั้น แล้วเราซึ่งเป็นนักวิทยาการคอมพิวเตอร์ซึ่งรู้เรื่องแค่คอมบินาทอริคส์ จะไม่มีทางเข้าใจบทพิสูจน์นั้นเลย

(ผมได้ข่าวจากบล็อกของ Luca) ในงานการประชุมนักคณิตศาสตร์นานาชาติที่กรุงมาดริก (ICM'06) ที่จะถึงนี้ Avi Wigderson จะนำเสนอบทความ ที่สรุปความคืบหน้าของการพิสูจน์ปัญหา P กับ NP ตอนต้นบทความเขาอ้างถึงคำพูดของ Steve Smale ว่า "ปัญหา P กับ NP --- ของขวัญสำหรับคณิตศาสตร์จากวิทยาการคอมพิวเตอร์"

เราอาจได้เห็นความคืบหน้าบางอย่าง และสิ่งที่ Luca กลัวที่สุดอาจเป็นจริงก็ได้

Sunday, April 02, 2006

เกี่ยวกับ MathML และ ASCIIMathML

จากที่มีหลาย ๆ คนเข้ามาอ่าน แล้วมีปัญหาเกี่ยวกับการใช้ MathML หรือได้ให้ความเห็นเกี่ยวกับการใช้ MathML เอาไว้ (ดู mk หรือ comment ของ bact')

จริง ๆ ผมก็ไม่ค่อยทราบเท่าไหร่นักเกี่ยวกับตัว MathML นี่ พอดีคุยกับ Kanat (ชื่อไทยเขียนไงนะ) ก็แนะนำวิธีที่ได้จาก นุ มา คือให้เอาบรรทัดนี้

<script src="http://www1.chapman.edu/~jipsen/mathml/ASCIIMathML.js" type="text/javascript"></script>

ใส่ลงไปที่หัวบล็อก script นี้เป็นของคุณ Peter Jipsen ชื่อว่า ASCIIMathML

เวลาใช้ก็เขียนแบบที่เขียนใน LaTex คือ ใส่นิพจน์ทางคณิตศาสตร์ในเครื่องหมายดอลลาร์ เช่น
$n^2+b^2/c$
จะได้เป็น $n^2+b^2/c$

สะดวกมาก (สำหรับคนเขียน) ครับ

อสมการของเชบิเชฟ

จะพิสูจน์กฎแห่งการมีจำนวนมาก เราจะใช้ต้อง อสมการของเชบิเชฟ (ดูรายละเอียดแบบเป็นทางการได้ที่ วิกิพีเดียไทย) ซึ่งกล่าวว่าถ้าตัวแปรสุ่ม $X$ มีค่าคาดหวัง $\mu$ และความแปรปรวน $\sigma^2$ เราจะได้ว่า
$\Pr[|X-\mu|\geq t]\leq (\sigma^2)/(t^2)$

ก่อนอื่นต้องระบุก่อนว่าผมไม่ค่อยแน่ใจว่าบล็อกนี้จะเขียนให้ใครอ่าน คือ.. ไม่ค่อยแน่ใจว่าต้องเขียนถึงเรื่องพื้นฐานแค่ไหน เป้าหมายจริง ๆ ผมพยายามจะเขียนเกี่ยวกับ central limit theorem และการพิสูจน์ (เพราะว่าตอนนี้กำลังอ่านเรื่องที่เกี่ยวข้องกับเรื่องนี้อยู่) ผมก็จะเขียนลึกบ้างตื้นบ้างตามสะดวกแล้วกันนะครับ

คิดว่าหลาย ๆ คนคงเคยเห็นการพิสูจน์อสมการของเชบิเชฟที่ใช้อสมการของมาร์คอฟแล้ว ผมเลยจะเขียนการพิสูจน์โดยตรงแทน (ซึ่งมีแนวคิดเหมือนกัน) ผมตามหนังสือของ Gnedenko ครับ

เอากรณีที่เป็นดิสครีตแล้วกันนะครับ เราทราบว่า
$\Pr[|X-\mu|\geq t] = \sum_{x:|x-\mu|\geq t}\Pr[X=x]$
สังเกตว่าในส่วนที่เราหาผลรวมนั้น $(|x-\mu|)/t\geq 1$ เราจะได้
$\sum_{x:|x-\mu|\geq t}\Pr[X=x]\leq \sum_{x:|x-\mu|\geq t}((|x-\mu|)/t)^2\Pr[X=x] $
$= 1/(t^2) \sum_{x:|x-\mu|\geq t}(x-\mu)^2\Pr[X=x]$
เนื่องจาก $(x-\mu)^2$ นั้นไม่น้อยกว่าศูนย์ ดังนั้นเราสามารถขยายขอบเขตของการหาผลรวมได้ โดยไม่ทำให้ผลที่ได้ลดลง นั่นคือ
$\sum_{x:|x-\mu|\geq t}\Pr[X=x]\leq 1/(t^2) \sum_{x=-\infty}^{\infty}(x-\mu)^2\Pr[X=x]=(\sigma^2)/(t^2)$
เพราะว่า $\sum_{x=-\infty}^{\infty}(x-\mu)^2\Pr[X=x]=\sigma^2$ ตามนิยามของความแปรปรวน

Saturday, April 01, 2006

กฎแห่งการมีจำนวนมาก (1)

(ในบล็อก wonam.exteen.com ผมมักจะเขียนเรื่องทั่ว ๆ ไป แต่สำหรับบล็อกนี้ ผมจะพยายามเีขียนเรื่องที่เกี่ยวข้องกับวิทยาการคอมพิวเตอร์เชิงทฤษฎี ซึ่งอาจเป็นเรื่องที่ผมศึกษาอยู่ หรือไปผ่าน ๆ ตามา)

ให้เหรียญที่เที่ยงตรงมาหนึ่งอัน โยน 2 ครั้ง แล้วนับจำนวนหัวที่ออกมา ตามหลักความน่าจะเป็น ค่าคาดหวัง (expected value) ของจำนวนหัวก็คือ 1 แต่อย่างไรก็ตาม ไม่จำเป็นที่ผลที่ได้เป็นเช่นค่าคาดหวังเสมอไป ถ้าลองคำนวณดูจะพบว่า ความน่าจะเป็นที่จะได้หัว 1 ครั้งพอดี มีค่าเท่ากับ 0.5 เท่านั้น

แล้วความน่าจะเป็นที่เราคำนวณมาเนี่ยะ มันจะมีประโยชน์อะไร? เช่นถ้าเราบอกว่าเหตุการณ์หนึ่งจะเกิดขึ้นด้วยความน่าจะเป็น 0.5 จริง ๆ แล้วมีความหมายอะไรหรือไม่?

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

ความเข้าใจหนึ่งที่เรามีเกี่ยวกับความน่าจะเป็นก็คือจำนวนครั้ง โดยเฉลี่ย ที่เหตุการณ์หนึ่ง ๆ จะเกิดขึ้น แน่นอนคำว่าโดยเฉลี่ยนั้น มีนัยยะของจำนวนอยู่ด้วย นั่นคือ ยิ่งมีการทดลองมากครั้งเข้า จำนวนครั้งของการเกิดขึ้นของเหตุการณ์ที่เรานับได้ ก็ควรจะมีสัดส่วนเข้าใกล้กับความน่าจะเป็น นี่คือ "กฎแห่งการมีจำนวนมาก" หรือ Law of large number (ดูเพิ่มที่ en.wikipedia.org)

ถ้าเราจะอธิบายในเชิงคณิตศาสตร์ เราก็อาจเขียนได้ดังนี้ (นี่คือรูปของ weak law of large numbers): ให้ $X_1,X_2,\ldots$ เป็นลำดับของตัวแปรสุ่ม ที่ไม่ขึ้นต่อกัน มีค่าคาดหวัง $\mu$ และค่าความแปรปรวน $\sigma^2$ ให้ค่าเฉลี่ยของตัวแปรสุ่ม $n$ ตัวแรก $\bar{X}_n = (X_1 + X_2 +\cdots + X_n)/n$ สำหรับ $\epsilon$ ใด ๆ ที่มากกว่าศูนย์

    $\lim_{n\rightarrow\infty}\Pr[|\bar{X}_n-\mu|<\epsilon] = 1$

สำหรับการพิสูจน์จะมาเขียนต่ออีกครั้ง

Thursday, March 23, 2006

ชื่อซ้ำ ชื่อต่าง

เพิ่งมาใช้ last.fm (สถิติของผม http://www.last.fm/user/wonam/) ซึ่งเป็น social network ของการฟังดนตรี หลาย ๆ คนสังเกตว่า
  • มีวงดนตรีหลายวงที่ชื่อซ้ำกัน (อาจจะมาจากหลายประเทศ)
  • วงดนตรีวงหนึ่ง เขียนได้หลายแบบ เช่น Modern dog กับ Moderndog หรือ P2 Warship กับ P 2 Warship กับ P II W P2 Warship
ผมกำลังคิดว่าเป็นไปได้หรือไม่ที่จะพยายามแก้ปัญหาเหล่านี้โดยอัตโนมัติ