jittat

พิจารณาความสัมพันธ์เวียนบังเกิด (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 fun

ฝน ฟ้า อากาศ สุดแสนเงียบ ฉันนอนอยู่ในห้อง รอคอยเวลาที่จะตื่นขึ้น เพียงเพื่อพบกับวันใหม่ที่รออยู่อย่างไม่เปลี่ยนแปลง บทกวีรูปแบบใหม่ ที่ชื่อว่าฟิบ (เสนอโดย 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 สักหน่อยนะครับ... ไว้มาต่อพรุ่งนี้ครับ

กฎแห่งจำนวนมาก บอกกับเราว่า ถ้าข้อมูลตัวอย่างที่สุ่มมามีจำนวนมาก ค่าเฉลี่ยที่ได้ก็จะใกล้กับค่าเฉลี่ยจริง ๆ ทฤษฎีบทขีดจำกัดกลาง (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 ให้ใช้ได้กับการแจกแจงทวินามใด ๆ ถ้าเราทดลองแบบสุ่มไม่

เมื่อเรามีอสมการของเชบิเชฟแล้ว เราสามารถพิสูจน์ กฎแห่งจำนวนมาก ได้ไม่ยากนัก ก่อนอื่นเราต้องการหาค่าความแปรปรวนของผลรวมของตัวแปรสุ่มก่อน พิจารณาตัวแปรสุ่ม $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$ ที่ไม่ขึ้น

ปัญหานี้เป็นปัญหาเชิงทฤษฎีที่สำคัญที่สุดและโด่งดังที่สุดของวิทยาการคอมพิวเตอร์ หลายคนบอกว่าวิทยาการคอมพิวเตอร์เชิงทฤษฎีไม่สามารถจะพูดเกี่ยวกับผลงานของสาขาตนเองได้มากนัก เพราะแม้แต่ปัญหาที่เป็นพื้นฐานที่สุด เรายังไม่สามารถตอบได้เลย สำหรับคนที่เคยผ่านหูผ่านตาปัญหาชื่อประมาณนี้มาบ้าง ขอผมทบทวนสักหน่อยโดยใช้ภาษาที่ไม่เป็นทางการนัก เวลาผมกล่าวถึง "ปัญหา" ผมหมายถึงปัญหาที่ต้องการคำตอบว่า "ใช่" หรือ "ไม่ใช่" เช่น ปัญหาจำนวนเฉพาะ ที่ให้จำนวนเต็มบวกมาหนึ่งจำนวน แล้วถามว่าจำนวนหนึ่งเป็นจำนวนเฉพาะหรือไม่? ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา P คือปัญหาที่เรามีวิธีที่หาคำตอบได้อย่างมีประสิทธิภาพ ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา NP คือปัญหาที่ถ้าคำตอบของปัญหาหนึ่ง ๆ คือใช่ เรามีวิธีการที่จะยืนยันคำตอบนั้นอย่างมีประสิทธิภาพ (อ่านเพิ่มที่ วิกิพีเดียไทย ) ปัญหานี้เป็นเรื่องพื้นฐานมาก ๆ ของการหาคำตอบ กับการยืนยันคำตอบ ซึ่งหลาย ๆ คนเชื่อกันว่า อย่างหลังน่าจะ ง่าย กว่า ผมจำได้ว่าได้อ่านจาก โพล ที่ทำโดย William Gasarch เกี่ยวกับปัญหา P และ NP คำตอบหนึ่งของ Luca Trevisan ในโพลน

จากที่มีหลาย ๆ คนเข้ามาอ่าน แล้วมีปัญหาเกี่ยวกับการใช้ 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

(ในบล็อก wonam.exteen.com ผมมักจะเขียนเรื่องทั่ว ๆ ไป แต่สำหรับบล็อกนี้ ผมจะพยายามเีขียนเรื่องที่เกี่ยวข้องกับวิทยาการคอมพิวเตอร์เชิงทฤษฎี ซึ่งอาจเป็นเรื่องที่ผมศึกษาอยู่ หรือไปผ่าน ๆ ตามา) ให้เหรียญที่เที่ยงตรงมาหนึ่งอัน โยน 2 ครั้ง แล้วนับจำนวนหัวที่ออกมา ตามหลักความน่าจะเป็น ค่าคาดหวัง (expected value) ของจำนวนหัวก็คือ 1 แต่อย่างไรก็ตาม ไม่จำเป็นที่ผลที่ได้เป็นเช่นค่าคาดหวังเสมอไป ถ้าลองคำนวณดูจะพบว่า ความน่าจะเป็นที่จะได้หัว 1 ครั้งพอดี มีค่าเท่ากับ 0.5 เท่านั้น แล้วความน่าจะเป็นที่เราคำนวณมาเนี่ยะ มันจะมีประโยชน์อะไร? เช่นถ้าเราบอกว่าเหตุการณ์หนึ่งจะเกิดขึ้นด้วยความน่าจะเป็น 0.5 จริง ๆ แล้วมีความหมายอะไรหรือไม่? ถ้าถกกันเรื่องความหมายแล้ว จริง ๆ ก็ตอบได้ยาก แต่ถ้าเรายึดโมเดลมาตรฐานทั่วไปของความน่าจะเป็น เราสามารถแสดง "ความหมาย" ของตัวเลขความน่าจะเป็นพอได้บ้าง ความเข้าใจหนึ่งที่เรามีเกี่ยวกับความน่าจะเป็นก็คือจำนวนครั้ง โดยเฉลี่ย ที่เหตุการณ์หนึ่ง ๆ จะเกิดขึ้น แน่นอนคำว่าโดยเฉลี่ยนั้น มีนัยยะของจำนวนอยู่ด้วย นั่นคือ ยิ่งมีการทดลองมากครั้งเข้า จำนวนครั้งของการเกิดขึ้น