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$

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