Expected Value(এক্সপেক্টেড ভ্যালু)

In Probability Theory expectation is known as the mean value.

Expected Value is summation of all possible values of a random variable multiplied by the respective probabilities.

Q : What is Random Variable?

Random Variable  is a variable whose value is unknown  or a function that assign values to each of an experiment's outcomes. we all know that one coin toss have two event. Head or tail. Suppose X is a Random Variable. We toss a coin if it will be a head than X = 1 or if it will be a tail X = 0.

Mind that, 

               Probability of an event = P(i),

               Amount of time the event happen = V(i)  [ its also called value. ]

So,

                Expected Value = ∑ P(i) *  V(i)

Q1 :  ধরো তোমার কাছে একটা কয়েন আছে, কয়েনটা একবার টস করলে হেড পাবার প্রোবাবিলিটি P এবং টেইল পাবার প্রোবাবিলিটি (১-P) তুমি কয়েনটা টস করছো যতক্ষণ না পর্যন্ত হেড পাও। হেড পাবার জন্য গড়ে (এক্সপেক্টেড) তোমার কয়বার কয়েন টস করা লাগবে?

    এক্সপেক্টেড ভ্যালু,

                                     E = P * 1 + (1-P) * (1 + E)

                               

                                     E = P + 1 - P + (1-P)*E

    

                                     E = 1/P

Q2 : একটা কয়েন আছে যেটা টস করলে হেড পাবার প্রোবাবিলিটি হলো P এবং  টেইল পাবার প্রোবাবিলিটি হলো (১-P) পরপর দুটি হেড পেতে হলে গড়ে (এক্সপেক্টেড) কয়বার টস করতে হবে?

    এক্সপেক্টেড ভ্যালু,

                                    E = P*P*2 + P*(1-P)*(2+E) + (1-P)*(1+E)

                                    E = (1+P) / P²

Q3 : একটা কয়েন n বার টস করা হলে তুমি এক্সপেক্টেড কয়টি হেড পাবে? (এখানে n বার টস একটা event)

এক্সপেক্টেড ভ্যালু,  

                                E = P*(1 + E(n-1)) + (1-P)*E(n-1)

                                E = P*1 + E(n-1)

                                E = n*P

Q4 : n টা হেড পেতে হলে তোমাকে এক্সপেক্টেড কয়বার কয়েন টস করতে হবে?

এখানে হেড পাবার প্রোবাবিলিটি হলো P এবং  টেইল পাবার প্রোবাবিলিটি হলো (১-P).

এক্সপেক্টেড ভ্যালু,  

                                E(n) = P * (1 + E(n-1)) + (1-P) * (1 + E(n))

                                E(n) = 1/P + E(n-1)

                                E = n * 1/P

Base Case : E(0) = 0

Q5 : n টা বাল্ব আছে, শুরুতে সবগুলো বাল্ব অফ। প্রতিটা মুভ এ তুমি random একটা বাল্ব সিলেক্ট করতে পারো। এখন বাল্বটা যদি অফ থাকে তাহলে তুমি একটা কয়েন টস করবে, যদি হেড পাও তাহলে বাল্বটা অন করবে, যদি টেইল পাও তাহলে কিছুই করবে না। আর বাল্বটা যদি আগেই অন থাকে তাহলে সেই মুভে তোমার কিছুই করা দরকার নেই। এক্সপেক্টেড কয়টা মুভে তুমি সবগুলো বাল্ব অন করতে পারবে? কয়েনটা ফেয়ার কয়েন না, প্রতিবার হেড  পাবার প্রোবাবিলিটি p।

ধরো বর্তমানে x টা বাল্ব অফ  আছে. এবং এক্সপেক্টেড মুভ লাগবে E(x) 

  এক্সপেক্টেড ভ্যালু,  

                            E(x) = x/n * [P * ( 1 + E(x-1) ) + (1-P) * ( 1 + E(x) )] + (n-x)/n * [1 + E(x)]

                            E(x) * xP/n = 1 + Px/n * E(x-1) 

                            E(x) = n/Px + E(x-1)

Some Property of Expected Value : 

E(X + Y) = E(X) + E(Y)

E(a*X) = a*E(X)  [ এখানে a হচ্ছে একটা constant ]

inversion :      a = [ 1, 4, 2, 5, 3 ]        যদি i < j হয় কিন্তু a[i] > a[j] হয় তাহলে এইটা একটা inversion.

এখানে 4 এবং 3 হচ্ছে inversion

Q5 : n size এর একটা array এর permutation দেওয়া আছে, বের করতে হবে Expected Number of Inversion?

ধরি n = 3 size এর একটা permutation দেওয়া আছে তাহলে সম্ভাব্য গুলা permutation এবং number of inversion গুলা হলো :

    

                       All Permutation  ----------  Number of Inversion

                        

                        [ 1, 2, 3 ]                                         0

                        [ 1, 3, 2 ]                                         1

                        [ 2, 1, 3 ]                                         1

                        [ 2, 3, 1 ]                                         2

                        [ 3, 1, 2 ]                                         2

                        [ 3, 2, 1]                                          3

মোট number of inversion = (0 + 1 + 1 + 2 + 2 + 3) = 9

সুতরাং, Expected Number of Inversion = 9/6 = 1.5

ধরি একটা array এর মধ্যে দুইটি element i এবং j যেখানে i < j

এই দুইটি element দুই ভাবে থাকতে পারে permutation এর মধ্যে : 

                                     

যখন j আগে থাকবে i এর তখনই inversion হবে, inversion হওয়ার probability হচ্ছে, P(i, j) = ১/২

(i, j) এই দুইটা element inversion হবে তার Expected Value, 

                                  E(i, j) = P(i, j) * 1 + (1 - P(i, j)) * 0  

                                  E(i, j) = 1/2 * 1 + (1 - 1/2) * 0 

                                        

                                  E(i, j) = 1/2

এভাবে সমস্ত array এর Expected Inversion, 

                                  E = (1, 2) এর expected inversion + (1, 3) এর expected inversion + (1, 4) এর expected inversion + ............... + (i, j) এর expected inversion + ................ + (n-1,  n) এর expected inversion 

                                 E = ∑ E(i, j) * 1/2      [ যেখানে i < j ]

                                 E = ⁿC₂ * 1/2

                                 E = (n*(n-1)) / 2 * 1/2

                                 E = (n*(n-1)) / 4

Q6 : At least ১ টা হেড এবং ১ টা টেইল পেতে হলে তোমাকে এক্সপেক্টেড কয়বার কয়েন টস করতে হবে ?

             f(x) = (n-x)/n * f(x) + (x/n) * f(x-1) + 1

             f(x) - (n-x)/n * f(x) = 1 + (x/n) * f(x-1)

             f(x) * (1 - (n-x)/n) = 1 + (x/n) * f(x-1)

            

             f(x) * (x/n) = 1 + (x/n) * f(x-1)

             f(x) = (n/x) + f(x-1)

সুতরাং, Expected Value, f(2) = 2/1 + 2/2 = 3