Gambler's Ruin Problem(গ্যাম্বলার রুইন)

Q : প্রথমে আসি Gambler's Ruin Problem টা কি?

Ans : একটা Gambler(জুয়াড়ি) আছে তার কাছে i পরিমান টাকা আছে সে Casino(ক্যাসিনো) তে গেছে জুয়া খেলার জন্য সে প্রতিবার ১ টাকা করে খেলবে যদি জিতে তাহলে তার ১ টাকা বাড়বে আর হেরে গেলে তার ১ টাকা করে কমবে, তাকে একটি n টাকার টার্গেট দেওয়া থাকবে। 

যদি খেলতে খেলতে তার টাকার পরিমান শুন্য হয়ে যায় তাহলে সে হেরে যাবে এবং খেলা শেষ হয়ে যাবে আর যদি খেলতে খেলতে তার টাকার পরিমান n হয়ে যায় তাহলে সে জিতে যাবে এবং খেলা শেষ হয়ে যাবে. Gambler কাছে যতক্ষণ টাকা আছে ততক্ষন সে খেলবে.

এখন আমাদের বের করতে হবে Gambler এর জিতার বা n টাকা হওয়ার probability কত? আর এটাই হচ্ছে Gambler's Ruin Problem.

ধরি Gambler ৫ টাকা নিয়ে খেলা শুরু করেছে এবং তার জিততে হলে তার সর্বমোট টাকা ৭ হওয়া লাগবে তাহলে কি হতে পারে?

শুরুতে Gambler  কাছে ৫ টাকা ছিল এখন যদি Gambler জিতে তাহলে তার  মোট ৬ টাকা হবে আর যদি হারে তাহলে ৪ টাকা হবে। এভাবে প্রত্যেকটা খেলার ২ টা স্টেপ থাকবে,হয়তো সে জিতবে না হয় হারবে.

ধরি Gambler এর জিতার probability হচ্ছে p টা এবং হারার probability হচ্ছে (১-p). p probability তে Gambler এর ১ টাকা বাড়বে আর (১-p) probability তে Gambler আর ১ টাকা কমবে.

আবার ধরি Gambler এর কাছে শুরুতে i টাকা ছিল এবং তার জিততে হলে n টাকাতে পৌঁছাতে হবে.যখন i = 0 হবে সে হেরে যাবে অথবা i = n হবে তখন সে জিতে যাবে এবং খেলা শেষ হয়ে যাবে  তাহলে 0 এবং n হচ্ছে Terminal Position.

এখানে i হতে একটা game win হওয়ার probability হচ্ছে  p. আর i হতে একটা game loss হওয়ার probability হচ্ছে (1-p). যদি Gambler win হয় তাহলে তার মোট টাকা হবে (i+1) আর যদি Gambler loss হয় তাহলে তার মোট টাকা হবে (i-1). বের করতে হবে i থেকে n এ যাওয়ার probability কত?

ধরি, 

        a(i) =  probability of winning from i.  (অর্থাৎ a(i) হচ্ছে i হতে শুরু করলে n এ যাওয়ার probability)

তাহলে লিখতে পারি,

                                    a(i) = p * (a+1) + (1-p) * (a-1)

এভাবে i = 1 হতে শুরু করে i = n-1 পর্যন্ত সবার জন্য এমন একটা করে equation পাওয়া যাবে.

Gambler's Ruin Problem এর Terminal Position :  a(0) = 0 এবং a(1) = 1.

যদি n = 4, p = 0.5 এবং 1-p = 0.5 হয় তাহলে,  a(0) = 0 এবং a(4) = 1.

                           

                          a(1) = 0.5 * a(2) + 0.5 * a(0)

              

           a(2) = 0.5 * a(3) + 0.5 * a(1)

           a(3) = 0.5 * a(4) + 0.5 * a(2)

এই Equation গুলা Linear Equation এখানে n-1 = 4-1 = 3 টা unknown variable আছে এবং n-1 = 4-1 = 3 টা equation আছে. এই Linear equation গুলা যদি Gaussian Elimination এর মাধ্যমে solve করি তাহলে প্রত্যেকটা Equation এর মান পাবো.

Gaussian Elimination দ্বারা Equation গুলা করলে ২ টা Case পাওয়া যায় :-

# Case 1 :  যদি p = 0.5 হয় তাহলে,

                                                        a(i) = ⁱ/_n  হবে.

ⁱ/_n একটা Significant Number এটা mean করে Gambler এর কাছে যত বেশি টাকা থাকবে তার টার্গেট n এ পৌঁছানোর probability তত বেশি.

ধরি Gambler এর টার্গেট n = ২৫ টাকা,

সে ২০ টাকা নিয়ে খেলা শুরু করে তাহলে win হওয়ার probability = ২০ / ২৫ = ০.৮ = ৮০%

সে ৫ টাকা নিয়ে খেলা শুরু করে তাহলে win হওয়ার probability = ৫ / ২৫ = ০.২৫ = ২৫%

# Case 2 : যদি p = 0.5 না হয় তাহলে ধরি একটা Constant, 

                                            

                                            r = ^(1-p)/_p

                                 এবং  a(i) = ^{(1 - ri)}/_{(1 - rⁿ)}

আরও জানতে চাইলে : Gambler's Ruin Problem

UVA Problem : UVA 11500