Baseball Party

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!

Comments

  1. chera9:23 PM, October 21, 2010

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

    I 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.

    ReplyDelete
  2. Pratik Poddar1:18 AM, October 22, 2010

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

    @chera.. Are you Gaurav Sinha from IITK?

    ReplyDelete
  3. chera11:31 AM, October 22, 2010

    yes pratik

    i 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.

    ReplyDelete
  4. Unknown6:12 AM, November 20, 2010

    I think a more compact solution can be:

    X_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

    ReplyDelete
  5. AA4:26 PM, November 20, 2010

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

    Let 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

    ReplyDelete
  6. chera10:56 PM, November 20, 2010

    Abhishek,

    Given 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.

    ReplyDelete

Post a Comment

Popular posts from this blog

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)
Read more