โจทย์ความน่าจะเป็น
 

คือ สงสัยมานาน ช่วยบอกวิธีทำด้วยนะครับ โจทย์มีอยู่ว่า

ในสี่เหลี่ยมผืนผ้ารูปหนึ่ง สุ่มจุดมาคู่หนึ่งแล้วลากเส้นเชื่อม แล้วก็สุ่มจุดมาอีกคู่หนึ่งในสี่เหลี่ยมเดียวกัน ลากเส้นเชื่อม ถามว่า ความน่าจะเป็นที่เส้นเชื่อมทั้งสองจะตัดกันเป็นเท่าใด

(ผมลองมั่วๆดูแล้ว ไดประมาณ 1/(2 x sqrt(3)) แต่มันดูไม่ค่อยจะถูกต้องเท่าไหร่)

ลองบอกแนวคิดที่ลองคิดดูมาหน่อยสิครับ.
ผมอ่านดูแล้วมันงง ชอบกล
เพราะการตัดกันมันมีได้หลายรูปแบบ
แล้วโจทย์จากที่ไหนครับ

โทษทีครับ ผมพิมพ์ผิดไป จริงๆแล้วผมมั่วได้ประมาณ 1 / (3 x sqrt(2)) ไม่ใช่ 1 / (2 x sqrt(3))

ก็ วิธีคิดของผม (มันผิดแน่ๆนะครับ) คือ เนื่องจากเมื่อเราสุ่มจุดมาสองจุดบนเส้นจำนวนในช่วง [a, b] จะได้ว่าผลต่างเฉลี่ยของสองจุดเป็น (b - a) / 3 ดังนั้น แสดงว่าความยาวเส้นตรงเฉลี่ยในแกน 2 มิติก็ควรจะเป็น sqrt((1/3)^2 + (1/3)^2) = sqrt(2) / 3 เมื่อคำนวณในสี่เหลี่ยมจัตุรัสที่มีความยาวด้าน 1 หน่วย
จากนี้ ผมก็ลองมั่ว คิดให้เส้นตรงที่สุ่มได้เส้นแรกอยู่ตรงกลางของสี่เหลี่ยม เส้นตรงอีกเส้นจะตัดเส้นแรกได้ก็ต่อเมื่อจุดปลายทั้งสองอยู่คนละฝั่งกัน (ใช้เส้นที่ 1 เป็นตัวแบ่ง) ความน่าจะเป็นที่จุด 2 จุดอยู่คนละฝั่งกัน ก็ควรจะเป็น 1/2 ส่วน
แต่ ปัญหาคือ เส้นตรงเส้นแรก มีความยาวเป็น sqrt(2) / 3 ซึ่งสั้นกว่าแกนสมมติที่ใช้แบ่งฝั่งของจุด (ซึ่งประมาณว่ายาว 1) ความน่าจะเป็นที่เส้นที่สองจะตัดกับเส้นแรกเลยเป็น (sqrt(2) / 3) x (1 / 2) เลยได้ 1 / (3 x sqrt(2))

รบกวนบอกที่มาด้วยครับ.
โจทย์จากที่ไหน
ใครเป็นตั้ง
คืออย่างน้อยถ้าที่มามันน่าเชื่อถือ
ว่ามันมีคนเคยคิดและหาคำตอบออกมาได้จริง ๆ
ผมจะได้ลองนั่งคิดดูจริง ๆ จัง ครับ. :confused:

อ๋อ ครับ จริงๆแล้วมันเป็นโจทย์ของคอมพิวเตอร์น่ะครับ เค้าให้หาความน่าจะเป็นนี่แหละ แต่ให้ใช้คอมพิวเตอร์ทำ โดยสุ่มเส้นมา 2 เส้นแล้วตรวจสอบว่าตัดกันรึเปล่า แล้วก็สุ่มใหม่มาเรื่อยๆ บันทึกจำนวนครั้งที่มันตัดกันกับจำนวนครั้งที่ทดลองทั้งหมด นำมาหารกัน ผลที่ได้ประมาณ 0.22 (มันไม่ค่อยแน่นอนเพราะทดลองแค่ 10000 ครั้ง) ผมเลยคิดว่ามันน่าจะมีวิธีทางคณิตศาสตร์ที่แน่นอนกว่าน่ะครับ แต่คิดแล้วคิดไม่ออก ไม่รู้ว่าต้องคิดยังไง

ว่าแต่ ลากเชื่อมนี่
ลากเป็นเส้นตรง หรือ ส่วนของเส้นตรงเหรอ
แล้วมันก็น่าจะขึ้นอยู่กับ ขนาดสี่เหลี่ยมด้วยนา

มันก็ต้องส่วนของเส้นตรงสิครับ

ส่วนเรื่องขนาดสี่เหลี่ยม ผมว่ามันไม่น่าจะต่างกันนะ

ตกลงผมจะลองคิดดูซักตั้งนะครับ.
ถ้าออกก็จะบอก ท่าทางปวดหัวน่าดู
แต่ผมลองคิดดูคร่าว ๆ แล้ว ขนาดของสี่เหลี่ยมน่าจะมีผลนะ
เอาเป็นว่าผมจะลองตั้งสมมติฐานว่ามันเป็นสี่เหลี่ยมจัตุรัสก็แล้วกัน
จะได้ simplified ขึ้นอีกหน่อย :eek:

คือผมก็จะลองคิดดูครับ

ผมลองใช้ Monte Carlo method ทำดูได้ผลแตกต่างจาก
ของคุณ tunococ มาก คือจากการทดลอง 10,000 ถึง
100,000,000 ครั้ง ค่าที่ได้ก็ตกอยู่ที่ 0.38 กว่าๆตลอดเลย
ขนาดของสี่เหลี่ยมผืนผ้าไม่มีผลใดๆต่อคำตอบ คำอธิบาย
อย่างง่ายๆก็คือ สมมติว่าเราเริ่มทำการทดลองกับสี่เหลี่ยม
จตุรัสได้ผลมาอันหนึ่ง แล้วเราจินตนาการการเรายืดสี่เหลี่ยม
จตุรัสอันนี้ให้กลายเป็นสี่เหลี่ยมผืนผ้าผลการทดลองก็ยังคง
ต้องเหมือนเดิม - เสันที่เคยตัดกันมันก็ยังตัดกัน เส้นที่ไม่ตัด
กันก็ยังคงไม่ตัดกันอยู่ดี ผมก็อยากรู้มากเหมือนกันว่าโจทย์ข้อ
นี้มี analytic solution รึเปล่า แล้วก็อยากให้มีใครอีกสักคน
ลองทำ simulation ดูอีกสักครั้งว่าจะได้เท่าไหร่

ยังไม่ได้ simulation ดูเลย

เท่าที่ลองคิด มันติดหลายๆปัญหา เช่น ความน่าจะเป็นที่เส้นตรงทั้งสองนั้นแตะกัน (ไม่ได้ตัดข้ามกันไปเลย แต่ก็ถือว่าการแตะคือการตัดกันอย่างหนึ่ง) ยกตัวอย่างเช่น สมมติว่า เส้นตรงเส้นแรกที่สุ่มขึ้นมา บังเอิญเป็นด้านหนึ่งของสี่เหลี่ยมผืนผ้า ถามว่าความน่าจะเป็นที่เส้นตรงอีกเส้นที่สุ่มขึ้นมา จะไปตัด(หรือแตะ) กับเส้นตรงเส้นนี้เป็นเท่าไร ? หรือให้ง่ายไปกว่านั้น จงหาความน่าจะเป็นที่สุ่ม 2 จุดใดๆในสี่เหลี่ยมผืนผ้า แล้ว 2 จุดนั้นเป็นจุดเดียวกัน ? :confused:

เพื่อหลีกเลี่ยงปัญหานี้น่าจะแก้โจทย์เป็น ความน่าจะเป็นที่ เส้นตรงทั้งสองตัดข้ามกันไปเลย เป็นเท่าไร ?

ตามความเห็นของผมนะครับ - โดย measure theory
(ซึ่งผมเองก็ยังงูๆปลาๆอยู่) แล้วค่าความน่าจะเป็นที่เส้นสอง
เส้นจะแตะกันก็คือ 0 ส่วนความน่าจะเป็นที่สุ่มจุดขึ้นมาสอง
จุดแล้วเป็นจุดเดียวกันก็คือ 0 อีกเหมือนกัน เหตุผลก็ทำนอง
เดียวกับว่า ถ้าเราเลือกค่า x มาอย่างสุ่มจากช่วง [0,1] ถามว่า
โอกาสที่ x จะเท่ากับ 1 เป็นเท่าไหร่ คำตอบก็คือ 0 อะครับ
ถ้าเราเลือกเส้นตรงมาอันนึงอย่างสุ่มโอกาสที่ความชันของเส้น
ตรงนั้นจะเท่ากับ 1 ก็คือ 0 ถ้าเราเลือกจุดมาจุดหนึ่งจาก
สี่เหลี่ยมจตุรัส [0,1]x[0,1] โอกาสที่จะได้จุด (0.5,0.5) ก็
คือ 0 อีกเช่นกัน

ขอเล่าถึงวิธีทดลองแบบง่ายๆที่ผมทำหน่อยนะครับ
ในการทดลองแต่ละครั้งผมจะสุ่มเลขในช่วง (0,1) มา 8 ตัว
คือ a, b, c, d, e, f, g, h ถ้า a>c ก็จะสลับค่า a กับ c จาก
นั้นก็จะคำนวณหาจุดตัด (x,y) ระหว่างเส้นตรงที่ลากผ่านจุด
(a,b) ไปยัง (c,d) กับเส้นตรงที่ลากผ่านจุด (e,f) ไปยัง
(g,h) แล้วจึงเช็คว่า a < x < c หรือไม่ ถ้าใช่ก็แสดงว่าส่วน
ของเส้นตรงที่ลากจาก (a,b) ไปยัง (c,d) นั้นตัดกับส่วนของ
เส้นตรงที่ลากจาก (e,f) ไปยัง (g,h) ถ้าไม่ใช่ก็แสดงว่าส่วน
ของเส้นตรงทั้งสองไม่ตัดกัน ขอให้สังเกตว่าค่า y ไม่ได้ใช้
เลย และที่ผมทำจริงๆก็คำนวณแต่ค่า x ออกมาเท่านั้น

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

เมื่อคืนลองกลับไปทำ simulation มาแล้ว :) จะขออธิบายรูปแบบที่ผมไปทำมานะครับ

จะสุ่มตัวเลขในช่วง [0,1] ออกมา 100 ค่า ดังนั้นสำหรับสี่เหลี่ยมจัตุรัสขนาด 1*1 ตารางหน่วย จะได้พิกัด (x,y) ที่เป็นไปได้ทั้งสิ้น = 100*100 = 10,000 ค่า
เราจะทำการสุ่มพิกัดเหล่านี้ออกมาเป็น (x₁,y₁) , (x₂,y₂) , (x₃,y₃) , (x₄,y₄) จากนั้นลากส่วนของเส้นตรงระหว่าง (x₁,y₁) ไปยัง (x₂,y₂) และระหว่าง (x₃,y₃) ไปยัง (x₄,y₄) ถ้าให้การสุ่มพิกัดทั้ง 4 ออกมานี้นับเป็น 1 รอบ จะได้ว่า มันควรจะครอบคลุมทุกรูปแบบที่เป็นไปได้เมื่อ ทำไปถึงรอบที่ 10,000 ^ 4 = 100,000,000 รอบ (ขอโทษด้วย ตอนคิดครั้งแรกมันเบลอๆ เลยได้คำตอบออกมาแบบนี้:P หากคิดให้ถูกจริงๆแล้วต้องทำการ simulation ไปเป็นจำนวนมากๆเลย 10^16 รอบ) แต่บางทีมันอาจยังไม่ครบทุกกรณีก็ได้ เพื่อเป็นการเผื่อเอาไว้ จึงทำไปที่ 2,147,000,000 รอบ (เผื่อไว้เต็มที่เลย :D)

1. หาจุดตัดของส่วนของเส้นตรงทั้งสอง (x,y) ตรวจสอบว่าส่วนของเส้นตรงทั้งสองขนานกันหรือไม่ (ดูจากจุดตัดว่าอยู่ที่ infinity หรือไม่)

1.1 หากพบว่าไม่ขนานกัน(แสดงว่ามันต้องไปตัดกันที่ไหนสักแห่ง) ก็ให้ตรวจสอบจากเงื่อนไขทั้ง 4 นี้

• (x - x₁)(x - x₂) <= 0 (ตรวจสอบว่า x อยู่ระหว่าง x₁ กับ x₂)
• (x - x₃)(x - x₄) <= 0 (ตรวจสอบว่า x อยู่ระหว่าง x₃ กับ x₄)
• (y - x₁)(y - x₂) <= 0 (ตรวจสอบว่า y อยู่ระหว่าง y₁ กับ y₂)
• (y - x₃)(y - x₄) <= 0 (ตรวจสอบว่า y อยู่ระหว่าง y₃กับ y₄)

หากพบว่า เป็นจริงทุกข้อ(จุดตัดจะต้องอยู่ระหว่าง (x₁,y₁) กับ (x₂,y₂) และ (x₃,y₃) กับ (x₄,y₄)) แสดงว่าส่วนของเส้นตรงทั้งสองตัดกันจริง แต่หากเป็นจริงเพียงบางข้อแสดงว่ามันไม่ตัดกัน (ต้องต่อความยาวของส่วนของเส้นตรงใดเส้นตรงหนึ่งออกไป จึงจะเจอจุดตัดนั้น)

1.2 หากพบว่าขนานกัน จะทำการตรวจสอบว่า ส่วนของเส้นตรงจาก (x₂,y₂) ไปยัง (x₃,y₃) ขนานกับ ส่วนของเส้นตรงจาก (x₁,y₁) ไปยัง (x₂,y₂) หรือไม่

1.2.1 หากพบว่าไม่ขนานกัน แสดงว่าส่วนของเส้นตรงทั้งสอง วิ่งขนานกันไป (ไม่ได้อยู่ในแนวเส้นตรงเดียวกัน) จึงไม่ตัดกัน

1.2.2 หากพบว่าขนานกัน ก็ให้ตรวจสอบจากเงื่อนไขทั้ง 2 ข้อนี้

• (x₁ - x₃)(x₁ - x₄) <= 0 และ (y₁ - y₃)(y₁ - y₄) <= 0 (ตรวจสอบว่า (x₁,y₁) อยู่ระหว่าง (x₃,y₃) กับ (x₄,y₄))
• (x₂ - x₃)(x₂ - x₄) <= 0 และ (y₂ - y₃)(y₂ - y₄) <= 0 (ตรวจสอบว่า (x₂,y₂) อยู่ระหว่าง (x₃,y₃) กับ (x₄,y₄))

หากพบว่าเป็นจริงข้อใดข้อหนึ่ง แสดงว่าส่วนของเส้นตรงทั้งสองตัดกันจริง(มันมีการทับซ้อนกัน) แต่หากไม่เป็นจริงเลย แสดงว่ามันไม่ตัดกัน (มันแค่อยู่ในแนวเส้นตรงเดียวกันเท่านั้น)

ผลจากการทดสอบไปได้ 2,147,000,000 รอบ พบว่า ความน่าจะเป็นที่เส้นตรงทั้ง 2 ตัดกันเป็น 23.117% ;)

ผมลองทำแบบเยกกรณีแล้วพบว่า
ไม่ว่าสี่เหลี่ยมที่ให้มาจะมีขนาดเท่าไร่ก็ตามจะไม่เป็นผลครับและผมแยกกรณีได้ดังนี้ครับ
1. ทุกด้านมีจุด 1 จุด ตัดกันได้ 1 กรณี และในเวลาเดียวกันเราสามารถลากเส้นให้ไม่ตัดกันได้ด้วย รวมความเป็นไปได้ 2กรณี
2. มี 1 ด้านที่มี 2 จุด เหตุการณ์เดียวกับข้อ 1 คือในเวลาเดียวกันเราก็สามารถลากให้ไม่ตัดกันได้ด้วย
3. มีด้านละ 2 จุด ก็เป็นเหตุการณ์เดียวกับ ข้อ 1,2
4. มี 1 ด้านที่มี 3 จุด จะได้ว่าเราไม่สามารถลากจุดสองจุดใดๆให้ตัดกันได้ กรณีนี้จึงมีเหตุการณ์ที่เป็นไปได้เพียง 1 กรณีเท่านั้น
5. ทั้ง 4 จุด อยู่รวมกัมสามด้านเป็นเหตุการณ์เดียวกับข้อ 4
เารจึงสรุปจาก 3 กรณีได้ว่า
ความน่าจะเป็นคือ
( 1+1+1+0+0)/(2+2+2+1+1)=3/8

อิอิ...รู้สึกว่าผมจะทำผิดไปไกลเลย(อีกแล้ว!) ขอบคุณคุณ
TOP มากเลยครับที่ช่วยแสดงวิธีทำให้ผมได้เห็นที่ผิดของ
ตัวเอง แล้วก็ขอบคุณที่ช่วยรัน simulation ให้ซะเยอะเลย
ว่างๆผมจะลองกลับไปแก้ไขและรันใหม่ดูอีกที ได้ผลยังไง
แล้วจะมาเล่าให้ฟังนะครับ

หยุดนี้ไม่ได้ไปเที่ยวไหน เลยถือโอกาสแก้ไขโปรแกรมแล้วรันใหม่
คราวนี้ทำ 100,000,000 ครั้ง ตัดกัน 23,148,932 ครั้ง
หรือประมาณ 23.15% ครับ เป็นอันว่า 3 คนต่างคนต่างทำ
ได้ผลสอดคล้องกัน ตอนนี้ก็เหลือแต่ว่าโจทย์นี้จะมี analytic
solution หรือไม่ วอนผู้รู้ช่วยตอบด้วยนะครับ

Date: 12 Jul 2001 08:39:30 GMT
From: Mike ROBSON <robson@serveur3-1.labri.u-bordeaux.fr>
Newsgroups: sci.math.research
Subject: Re: A probability problem

On Thu, 12 Jul 2001 06:15:06 +0700, Warut Roonguthai <warut@ksc9.th.com> wrote:
>Someone asked me the following question that I couldn't solve:
>
>If we randomly select 2 points from a closed rectangular region and draw
>the line segment joining them. Then, randomly select another 2 points in
>this rectangle and draw the line segment joining these 2 points, too.
>What is the probability that these 2 line segments intersect?
>
>Monte Carlo simulations tell me that the probability is around 0.23 and
>is independent of the dimension of the rectangle. Is this a well-known
>problem? Does it has an analytic solution? Are there any references to
>this problem?
>
>Thanks in advance.
>Warut
>

The fact that the probability doesn't depend on the dimensions is fairly
obvious since linear scaling takes intersecting segments into intersecting
segments so let's assume the rectangle is in fact a square of side 1.

Consider choosing the 4 points by first choosing a set of four and then
choosing their order. If the four points form a triangle and a point in
the interior of the triangle, no order gives an intersection, otherwise
one third of them do.
So your probability is a third of the probability that the four points form
a convex quadrilateral, (which must be well known?)

Date: 12 Jul 2001 03:15:40 -0700
From: "Robert B. Israel" <israel@math.ubc.ca>
Newsgroups: sci.math.research
Subject: Re: A probability problem

The probability is exactly 25/108.

Note that the conditional probability of the segments intersecting,
given that the four points are (in any order) the vertices of
a convex quadrilateral, is 1/3 (i.e. of the three ways of pairing
up the vertices, one will have intersecting line segments). The
conditional probability, given that the four points form a
non-convex (non-degenerate) quadrilateral, i.e. one is in the
convex hull of the other three, is 0 (the segments can not
intersect in this case). So your probability is 1/3 the
probability that four random points in a rectangle are the
vertices of a convex quadrilateral. And that probability is
"well-known" to be 25/36. IIRC that result is due to
Sylvester.

Robert Israel israel@math.ubc.ca
Department of Mathematics (604) 822-3629
University of British Columbia fax 822-6074
Vancouver, BC, Canada V6T 1Z2

Date: Thu, 12 Jul 2001 13:44:03 +0200
From: Matthias Mahnke <acegi@web.de>
Newsgroups: sci.math.research
Subject: Re: A probability problem

Concerning your questions, there are many problems of this kind
around.
The Buffon needle problem surely the oldest and probably the most widely known.
If you are interested in the mathematics of theese,
you my want to look at

\bibitem[Stoyan et al.]{stokenmeck}
D.~Stoyan, W.~S.~Kendall,J.~Mecke\\
{\bf Stochastic Geometry and its Applications}\\
Wiley series in probability and statistics\\
John Wiley \& Sons, second Ed. 1995

In most of this kind of problems you have to rely on
simulations, which are often (like yours) easy to program.
Still some are quite tricky, like the 2d "lilly pond model".
For this last problem see:

D.J.Dalay, C.L.Mallows, L.A.Shepp
A one-dimensional Poisson groth model with non-overlapping intervals
Stochastic Processes and their Applications 90 (2000) 223-241
(1 dim. case)

D.J.Dalay, H.Stoyan, D.Stoyan
The volume fraction of a Poisson germ model with maximally
non-overlapping sperical grains
Adv. Appl. Prob. 31, 610-624 (1999)
(2 dim. case, mostly very tricky simulations)

Regards Matthias

ตกลงเป็นอันว่าค่าความน่าจะเป็นที่คุณ tunococ อยากทราบ
มีค่าเท่ากับ 25/108 = 0.23148148... นะครับ :)

ขอบคุณ คุณ warut มากๆเลยครับ ที่ได้เอาคำถามนี้ไปถามใน news group จนได้รับคำตอบที่แท้จริงมา (ที่ news group นี่สุดยอดจริงๆนะครับ ไม่รู้ว่าคิดกันได้ยังไง)

ตอนนี้ยังแปลบางส่วนไม่ออกเลย :( อย่างคำว่า "convex quadrilateral" นี่มันเป็นสี่เหลี่ยมด้านไม่เท่าแบบไหนหรือครับ :confused: แล้วความน่าจะเป็นของสี่เหลี่ยมแบบนี้ ที่บอกว่า "well-known" นี่ท่าทางว่าจะ "well-known" จริงๆ เพราะสังเกตว่า รู้กันแทบทุกคนเลย (แต่เราไม่ยักรู้ :D)

ไป ๆ มา ๆ ก็มีข้อสรุปจนได้นะครับ.
ใครมาดูครั้งแรกครั้งเดียวนี่ คงปวดหัวแหง ๆ เลย ฮ่า
ผมก็นั่งดูอย่างเดียวมานานแล้ว

ไปค้นมาหน่อยนึง "convex quadrilateral" คือรูปสี่เหลี่ยมด้านไม่เท่า ซึ่งไม่มีการเว้า (เช่นสี่เหลี่ยมที่มีรูปร่าง เหมือนบูมเมอแรง) ลองดูรูปข้างล่างเป็นตัวอย่างนะครับ

จากรูป ACDE เป็น convex quadrilateral แต่ ABCE ไม่ใช่เนื่องจากมีการเว้า

ตามความเห็นของผมแล้ว คำว่า "quadrilateral" น่าจะ
หมายถึง สี่เหลี่ยม (ใดๆ, เฉยๆ) มากกว่าการเจาะจงลงไปว่า
เป็นสี่เหลี่ยมด้านไม่เท่านะครับ

คุณ TOP อุตส่าห์ช่วยทำรูปประกอบมาให้อย่างนี้แล้วก็คง
จะช่วยให้เข้าใจการพิสูจน์ได้ง่ายขึ้นนะครับ :)

เห็นด้วยครับ พอดีผมแปลจาก Dictionary ตรงๆ ความจริงแล้วมันควรจะเป็นสี่เหลี่ยมทั่วๆไปมากกว่า แบบที่คุณ warut ว่าไว้นั่นละครับ :D

ขอบคุณครับ ที่หาคำตอบมาให้
ผมไม่ได้มาเยี่ยมที่นี่นานพอควร ไม่นึกว่าจะรื้อของเก่ามาคิดกัน

ยังไงๆก็ขอบคุณมากๆขอรับ