92 views
There is a bag containing 5 white and 5 black balls. You repeat the following experiment till you see a white ball : take a ball uniformly at random out of the bag. If it is white, stop. Otherwise, put it back in the bag. What is the expected number of times you will need to draw a ball from the bag ?
| 92 views

+1 vote
We have 5 white and 5 black balls..

probability of getting white in each trial $\frac{5}{10} = \frac{1}{2}$,

similarly, probability of getting black is $\frac{1}{2}$,

one way to calculate expected number of trials is as follows:

E(no of trials) = $\sum x\cdot P\left (x \right )$

E = $1\times \frac{1}{2}+2\times \frac{1}{2}\times \frac{1}{2}+3\times\frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}+\ ...$

=$1\times\left ( \frac{1}{2} \right )^{1} + 2\times\left ( \frac{1}{2} \right )^{2} + 3\times\left ( \frac{1}{2} \right )^{3} + ...$                                         --(i)

multiply eqn (i) by $\frac{1}{2}$,

$\frac{E}{2}\ =1\times\left ( \frac{1}{2} \right )^{2} + 2\times\left ( \frac{1}{2} \right )^{3} + 3\times\left ( \frac{1}{2} \right )^{4} + ...$                      --(ii)

subtract eqn(ii) from eqn(i), we get:

$E - \frac{E}{2} = \left (\left ( \frac{1}{2} \right )^{1} + 2\times\left ( \frac{1}{2} \right )^{2} + 3\times\left ( \frac{1}{2} \right )^{3} + .. \right )-\left (\left ( \frac{1}{2} \right )^{2} + 2\times\left ( \frac{1}{2} \right )^{3} + 3\times\left ( \frac{1}{2} \right )^{4} + ... \right )$

$\frac{E}{2} = \left ( \frac{1}{2} \right )^{1}+\left [2\times\left ( \frac{1}{2} \right )^{2} - \left ( \frac{1}{2} \right )^{2} \right ]+\left [3\times\left ( \frac{1}{2} \right )^{3} - 2\times\left ( \frac{1}{2} \right )^{3} \right ]+\left [4\times\left ( \frac{1}{2} \right )^{4} - 3\times\left ( \frac{1}{2} \right )^{4} \right ] +\ ...$

$=\left (\frac{1}{2} \right )^{1} + \left (\frac{1}{2} \right )^{2} + \left (\frac{1}{2} \right )^{3} + \left (\frac{1}{2} \right )^{4} + \ ....$

using the formula for infinte G.P

$\sum = \frac{a}{1-r}$

$\frac{E}{2} = \frac{\frac{1}{2}}{1-\frac{1}{2}} = \frac{\frac{1}{2}}{\frac{1}{2}} = 1$

which gives,

$E = 2$
by (87 points)
selected
0

It gives fibonacci function, right?

$\sum_{.}^{.}kP(k)$ generates fibonacci functions. How are you doing without fibonacci?

https://gateoverflow.in/3778/gate2005-it-32

0

No, $\sum kP\left (k \right )$ doesn't generalize to fibonacci numbers,

for example consider the followimg distribution:

 k 0 1 2 P(k) 0.5 0.3 0.2

this is a valid distribution as $\sum P(k) = 1$,

but $\sum kP\left (k \right )$ isn't giving any fibonacci number here, or it may be somehow which i cann't see..

$\sum kP\left (k \right )$ is the definition of expectation of a discrete random variable.

let me explain above solution more thoroughly,

step 1:  decide your random variable:

let 'k' be a random variable which denotes the no of times you need to pick a ball from bag.

k=1,  it means you get white ball in first trial only

$p(k=1) = \frac{1}{2}$

k=2, you don't get a white in first go, but you get it in second one,

$p(k=2) = p(not getting white)\times p(getting white) = \frac{1}{2}\times \frac{1}{2}$

$p(k=2) =\left ( \frac{1}{2} \right )^{2}$

k=3, you get white in 3rd attempt(or trial):

$p(k=3) = p(not getting white)\times p(not getting white)\times p(getting white) = \frac{1}{2}\times \frac{1}{2} \times \frac{1}{2}$

$p(k=3) =\left ( \frac{1}{2} \right )^{3}$

and so on..

so our distribution looks like this:

 k 1 2 3 4 .. p(k) $\left ( \frac{1}{2} \right )^{1}$ $\left ( \frac{1}{2} \right )^{2}$ $\left ( \frac{1}{2} \right )^{3}$ $\left ( \frac{1}{2} \right )^{4}$ ..

step3: we have to conform that this is a valid random distribution,

to do so, we have to prove $\sum p(k) = 1$.

$\sum p\left (k \right ) = \left ( \frac{1}{2} \right )^{1} + \left ( \frac{1}{2} \right )^{2} + \left ( \frac{1}{2} \right )^{3} + \left ( \frac{1}{2} \right )^{4} + ...$

$=\frac{ \frac{1}{2}}{1 - \frac{1}{2}} = 1$

Therefore this is a valid distribution.

step4: Calculate expected value of random variable

$E\left ( k \right ) = \sum k\cdot p\left ( k \right )$

$E = E\left ( k \right ) = 1\times\left ( \frac{1}{2} \right )^{1} + 2\times\left ( \frac{1}{2} \right )^{2} + 3\times\left ( \frac{1}{2} \right )^{3} + ...$        --(I)

Now, all we have to do is to calculate the sum of this sequence,

these's many ways to solve this sequence, one way is how i did it..

Multiply above equation by half

$\frac{E}{2} =\frac{1}{2}\times \left (1\times\left ( \frac{1}{2} \right )^{1} + 2\times\left ( \frac{1}{2} \right )^{2} + 3\times\left ( \frac{1}{2} \right )^{3} + ... \right )$

$\frac{E}{2}\ =1\times\left ( \frac{1}{2} \right )^{2} + 2\times\left ( \frac{1}{2} \right )^{3} + 3\times\left ( \frac{1}{2} \right )^{4} + ...$               --(II)

subtract eq (II) from eq (I) as follows ( eq (II) - eq(I) ):

$E=1\times\left ( \frac{1}{2} \right )^{1} + 2\times\left ( \frac{1}{2} \right )^{2} + 3\times\left ( \frac{1}{2} \right )^{3} +4\times\left ( \frac{1}{2} \right )^{4} + ...$

$- \frac{E}{2}\ =\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1\times\left ( \frac{1}{2} \right )^{2} + 2\times\left ( \frac{1}{2} \right )^{3} + 3\times\left ( \frac{1}{2} \right )^{4} + ...$

-----------------------------------------------------------------------------------------------------------------

$E - \frac{E}{2}\ =\ \ \ \ \ \ \left (\frac{1}{2}\right )^{1} + \ \ \ \ \ \left ( \frac{1}{2} \right )^{2} +\ \ \ \ \ \ \ \left ( \frac{1}{2} \right )^{3} +\ \ \ \ \ \ \ \left ( \frac{1}{2} \right )^{4} + ...$

which gives,

$\frac{E}{2}=\left (\frac{1}{2} \right )^{1} + \left (\frac{1}{2} \right )^{2} + \left (\frac{1}{2} \right )^{3} + \left (\frac{1}{2} \right )^{4} + \ ....$

Now this is GP, use infinite sum formula

$\frac{E}{2} = \frac{\frac{1}{2}}{1-\frac{1}{2}} = \frac{\frac{1}{2}}{\frac{1}{2}} = 1$

$E = 2$

This is it. No need to use fibonacci formula

I should mention there are lot of ways to solve this same problem

0

@ankitgupta.1729

Can you plz tell me, how expectation to be 2?

See, if we take 2 balls from the bag at random and both are black, then how will you stop experiment? How expected number of ball drawn is 2?

0

@srestha

expectation is kind of weighted average. So, here on average you need to draw a ball 2 times.

You can think it like :

Suppose you draw a ball 10000 times then you would expect the white ball to come $10000 \times \frac{5}{10} = 5000$ times. So, on average you would need $10000/5000 = 2$ times for white ball to come.

In the given question, random variable $X=$ no. of times you need to draw a ball follows Geometric Distribution with pararmeter $p=5/10$ and in case of geometric distribution, expectation is $E[X] = 1/p = \frac{1}{5/10} = 2$.

0

@ankitgupta.1729

what is wrong if I do like this?

Say $x=5/10=1/2$

$E=\sum kP\left ( k \right )=1.\left ( 5x \right )+2.\left ( 5x^{2} \right )+3.\left ( 5x^{3} \right )+......$

$=5\left ( 1.x+2x^{2}+3x^{3}+4x^{4}+... \right )$

$=\frac{5x}{\left ( 1-x \right )^{2}}=5\frac{\frac{1}{2}}{\frac{1}{4}}=10$

0
why 5x ?
0
@srestha

P(k) is supposed to be the probability of getting success in $k^{th}$ trial..

you are taking that factor of 5 in each terms, that shouldn't be there.
0

@ankitgupta.1729

@Nikhil_dhama

it will be something more.

See this image

So, Possibility of completion in 1st stage will be $5$ [as only one of five white ball can stop the task]

completion  in 2nd stage completion will be $5^{2}$

completion  in 3rd stage completion will be $5^{3}$....

So, equation will be $E=\sum kP(k)=1.\left ( 5x \right )+2.\left ( 5^{2}x^{2} \right )+3.\left ( 5^{3}x^{3} \right )+....$

right?

0
$E=1.\left ( 5x \right )+2.\left ( 5x \right )^{2}+3.\left ( 5x \right )^{3}+....$

$5x.E=$              $1.\left ( 5x \right )^{2}+2.\left ( 5x \right )^{3}+3.\left ( 5x \right )^{4}+....$

--------------------------------------------------------------------------------------------------------------------------------------------

$(1-5x).E=\left ( 5x \right )+\left ( 5x \right )^{2}+\left ( 5x \right )^{3}+\left ( 5x \right )^{4}+....$ [by subtraction]

Therefore $E=\frac{1}{(1-5x)}.\frac{5x}{(1-5x)}=\frac{\frac{5}{2}}{(\frac{3}{2})^{2}}=\frac{10}{9}$

So, ans $\frac{10}{9}$

Anything wrong?
+1 vote

"expected number of times you will need to draw a ball"-This line is not clear in question. Still you can think like this.

There are $5$ white and $5$ black ball.

If we pick up $1$ white ball, then just stop the experiment.

Otherwise repeat.

So, the probability value will be like this$=\frac{1}{5}+\frac{1}{5}.\frac{1}{5}+\frac{1}{5}.\frac{1}{5}.\frac{1}{5}+.....=\frac{1}{4}$

by (755 points)
0
I have 1 question. Probability of getting a white ball is should be 1/5 or 5/10? Can u plz Clarify?
0
5/10..
+1 vote
A more eligant way to solve this is exploiting the recursion out of it.

$E = 1\times p\left (getting\ white \right ) + p\left (not\ getting\ white\right )\times \left [ E + 1 \right ]$

$E = \frac{1}{2} + \frac{1}{2}\times\left [ E + 1 \right ]$

$E - \frac{E}{2}= \frac{1}{2} + \frac{1}{2}$

$\frac{E}{2}= 1$

$E = 2$

Explanation of this recurive equation..

$E = 1\times p\left (getting\ white \right ) + p\left (not\ getting\ white\right )\times \left [ E + 1 \right ]$

E : expected value of random variable

$1\times p\left (getting\ white \right )$ : we get white in first trial

now, it we don't get white in frist trial, then we are expecting it to come in 2nd, if not then in third so on..

we know it doesn't appear in first trail..

$p\left (not\ getting\ while\right )\times \left [ E + 1 \right ]$

this '+1' signifies that we already lost one trail white calculating previous expected value, that's why we multiply by E+ 1.

This method is a bit complicated to understand. that's why i followed a more simple way to solve this earlier.
by (87 points)
0
I understand what you mean

But can it be done in mathematical equation, where E  is total trial and inside equation u are taking E+1 trial? Recurrence relation cannot be like this . right?
0
yes, you are right, this doesn't looks like a recurrence relation,

To get this method one should  understand and fell :p what expectation really means..

I myself have some doubts about this method like why this method works? it is confirm that this works always, but i need to discover why?