**Source**: MIT OCW Course 6.041 / 6.431 Probabilistic Systems Analysis and Applied Probability

**Problem**:

Your n guests (n>0) are all baseball fans and they wear baseball caps. There is a total of s teams (s>0) in the league. Everyone of your guests is equally likely to be a fan of any one of these teams.

Compute the expected number of people who will pick a cap from their own team.

**Clarification**:

The number of caps is also n. You have brought the caps so that if the people behaved in an intelligent manner, each person would have got the cap of his team. The guests already had their team caps and after their arrival they had put their caps in a basket. After the party is over, the guests pick cap randomly from basket.

Update (22 Oct 2010)

Solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments!

Answer is (n+s-1)/s.

ReplyDeleteI think the problem statement could be made more clear. For example, we could say that

(i) after arrival of guests, the host had arranged the n caps and mixed them in a basket and the fans have randomly picked caps from this basket.

or

(ii) the guests already had their team caps and after their arrival they had put their caps in a basket. After the party is over, the guests pick cap randomly from basket.

Solution: Let the teams be numbered 1,2,3,...s

Let X= total number of fans who pick cap of their team.

Let Xi= number of fans of team i who pick a cap of team i . [i.e. correct cap]

Then X=X1+X2+….+Xs.

E[X]=E[X1]+E[X2]+….+E[Xs]

By symmetry ,

E[X1]=E[X2]=….=E[Xs]

Fix and Concentrate on any particular team, say team 1.

Then we may write E[X] = s*E[X1].

To find E[X1], suppose that there are r fans of team 1. If r=0, then clearly E[X1]=0. So suppose r>0 and the fans of team 1 are F1,F2,…,Fr. {r can be any number from 1 to n.}

Let a random variable Yi {i from 1 to r} be defined as Yi=1 iff fan Fi chooses cap of team 1.

Then , X1=Y1+…+Yr.

So E[X1]= E[Y1]+E[Y2]+….+E[Yr]

=r * E[Y1] because E[Yi]=E[Yj] by symmetry for all i,j.

Now E[Y1]=r/n because there are r caps of team 1 out of total n caps.

So given an r, E[X1]=r*E[Y1]= r *r/n=r^2/n.

So E[X1]= sigma r^2/n * P(r).,

Where p(r) is probability that team 1 has r fans and where summation sigma ranges from r= 0 to n.

It is readily seen that

P(r)= comb(n,r)*((s-1)^(n-r) )/ s^n.

So E[X1]= sigma r^2/n * comb(n,r)*((s-1)^(n-r) )/ s^n; {where summation sigma is from r = 0 to n.}

= ((s-1)/s)^n * sigma r^2/n * comb(n,r)* (s-1)^(-r)

=(n+s-1)/s^2.

Where we use identity sigma r^2 * comb (n,r) *x^r = n*x*(1+n*x) * ((1+x) ^(n-2)) by putting x=1/ (s-1).

This identity can be proved by differentiating w.r.t. x both sides in binomial expansion of (1+x)^n, multiplying the resultant equation with x and differentiating again.

So required answer is E[X]= s*E[X1]= (n+s-1)/s.

Bingo! Correct solution. Thanks for the answer and the suggestion :)

ReplyDelete@chera.. Are you Gaurav Sinha from IITK?

yes pratik

ReplyDeletei am gaurav sinha, cse 1996 graduate of iitk,

now working in indian revenue service (Customs and Excise).

its real fun and refreshing solving maths problems on ur blog. Thanx for same.

I think a more compact solution can be:

ReplyDeleteX_i: 1 if fan i picks his cap correctly, 0 otherwise

E[X_i]=P(X_i=1)=Pr(he picks his own cap)+P(he picks j's cap and j is fan of the same team as i)

=1/n + (n-1)/n(1/s) = (n+s-1)/ns

Now X= X_1+X_2...X_n

By linearity of expectation:

E[X]=E[X_1]+E[X_2]...E{X_n]

=n*(n+s-1)/ns

=(n+s-1)/s

I got my answer as n/s ... and I can't figure out where I'm wrong:

ReplyDeleteLet I(X_i) = 1 if person i gets his team cap, 0 otherwise

Let X = nos of people that get their team caps

Now , X = I(X_1) + I(X_2) + ... + I(X_N)

therefore

E[X] = E[I(X_1) + I(X_2) + ... + I(X_N)]

=> E[X] = N * E[ I(X_1) ]

=> E[X] = N * (Probability that person 1 gets his team cap)

Let P = (Probability that person 1 gets his team cap)

therefore

P = (k sums over 1 to N) [ P(team size of person 1 = k) * (probability that person 1 gets his team cap given his team size is k) ]

(probability that person 1 gets his team cap given his team size is k) = k/N

therefore

P = (k sums over 1 to n) [ P(team size of person 1 = k) * k/N ]

=> P = (1/N) * (expected team size of person 1)

since expected team size of person 1 = expected size of any team = N/s

therefore

P = 1/s

therefore

E[X] = N/s

Abhishek,

ReplyDeleteGiven that person 1 is in team T, there are remaining N-1 persons, who are equally likely to be in any team. So, expected size of T = 1 + expected no. of people , other than person 1 , who are in Team T.

=1+(N-1)/s.