IIT Kanpur Test Sample Paper

Question

(Overfed  pets)  The  Jones  family have  n pet  cats. The  caretaker who is charged  to  feed these  cats  is very careless.  Everytime he goes into the pet zone, he takes food along and feeds a random  cat - he does not care whether  the cat seems to be hungry  or if it seems to be bursting  with overfeeding.  Also assume that the  unfed cats  are unable  to draw  the  attention of the  caretaker towards  them  - the  cat  which is fed is chosen purely  randomly  (and  independently) each time.

Suppose the caretaker has already fed k of the cats at least once. On an expectation, how many more trips would he have to make before he feeds one of the unfed (n− k) cats for the first time?

Comments

One more doubt...how many trips will be needed on an average to feed all the cats?

---

I have given the answer below in the answer section tell me if anything is wrong

---

It is correct

Answer 1

Here in this question we want to find the expected number of trips made by the caretaker to feed one of the unfed (n-k) cats.

Let us assume Success = Caretaker feeds at one of (n-k) unfed cats

AND                   Failure  = Caretaker feeds one of k fed cats

So, the probability he feeds one of the (n-k) unfed cats is (n-k)/n = p (say) ( probability of success)

and the probability he feeds one of the k cats is k/n = q (say) (probability of failure)

Let us assume that X is the random variable of the number of trips made until the first success comes.

Suppose X=k then the caretaker feeds one of the unfed (n-k) cats at the k^th trip.

Now, P{X=k} = q^k-1p                                                                                                                                                                               

So, E[X] =^∞∑_k=1  kq^k-1 p

              =   (p/q) ^∞∑_k=0  kq^k

              =    p/q  * ( q/(1-q)²) )     ( using the formula  ^∞∑_x=0 xa^x = (a/(1-a)² )

              =    p/q  *  q/p² 

              =    1/p.

Thus the expected number of trips to feed  one unfed cat is 1/p = 1/ ( (n-k)/n ) = n/(n-k)

So, the required expected number of trips made by the caretaker to feed one unfed cat is n/(n-k)  (ANSWER)

Answer 2

This is geometric distribution. Let X be a random variable which means the number of trips needed to feed the first unfed cat.There are k cats which have been fed at-least once.The Probability that next fed cat is fed already = p =k/n. The probability that next fed cat will be fed first time = 1-p.Suppose t trips are needed.

Hence,   P(X=t)= $p^{t}*(1-p)$

Expected value is = 1/1-p hence 1/ 1- k/n

Comments

p should be the probabaiity of success. You have chosen it for failure. Read answer by @Kushagara.

---

Thank you so much..I have corrected my mistake.