Expected number of draws

Source: http://deltaepsilons.wordpress.com/

Problem: Consider a set of n objects from which m are drawn randomly at a time, with replacement.  What is E(n,m), the expected number of draws I have to make to have drawn all of the objects?

Note that we solved a similar problem and got the value of E(n,1) some time back in this problem.

Solution:

Highlight the part between the * symbols for the answer.
* E(n,m) = sum_{j=1}^{n} (-1)^(j+1) . C(n,j) / (1 - C(n-j,m)/C(n,m)), where C(n-j,m) = 0 when n-j < m. (Model: each draw picks a uniformly random m-subset of the n objects, draws independent.)

Derivation (inclusion-exclusion). Let T be the number of draws needed. For a fixed set J of j objects, the chance that none of them appears in t independent draws is r_j^t with r_j = C(n-j,m)/C(n,m). So by inclusion-exclusion P(all n seen within t draws) = sum_{j=0}^{n} (-1)^j C(n,j) r_j^t, hence P(T > t) = sum_{j=1}^{n} (-1)^(j+1) C(n,j) r_j^t. Now E[T] = sum_{t=0}^{inf} P(T > t), and summing each geometric series gives the formula.

Sanity checks. For m = 1, r_j = (n-j)/n and E = n . sum_j (-1)^(j+1) C(n,j)/j = n.H_n, the classical coupon collector answer (using the identity sum_j (-1)^(j+1) C(n,j)/j = H_n). Numerically: E(5,2) = 5.325, E(6,3) = 4.303, E(7,4) = 3.779, E(10,3) = 9.046, E(20,5) = 13.271 - all confirmed by simulation. (The tempting stage argument - wait geometrically for each new object - fails because one m-draw can reveal several new objects at once; the inclusion-exclusion above is exact.)

(solution posted by AI) *

Comments

  1. chera3:38 AM, January 05, 2011

    found an approximate bound using wald's equation. http://en.wikipedia.org/wiki/Wald's_equation.

    imagine the experiment with m=1.its known that
    E(n,1)= n H(n),
    where H(n)=1+1/2+1/3+....1/n

    now let x1= number of draws to pick m distinct objects. After x1 draws, let x2=number of draws to pick m distinct objects, and so on till u see see all the n objects.

    then E[X1]=E[X2]=...=n[1/(n)+1/(n-1)+...1/(n-m+1)]=n/[H(n)-H(n-m)]

    If S is total number of draws
    i.e. S=X1+X2+.......,then as per wald's equation,
    E[S]=E[X1]*E(n,m).

    Now, E[S]-m < E(n,1) <=E[S].

    Inequality is there because last object will be drawn in the last set of m draws.so,

    [H(n)+m/n]/[H(n)-H(n-m)] > E(n,m) > = H(n)/[H(n)-H(n-m)]

    where H(r)=1/r+ 1/(r-1)+..1/2+1

    ReplyDelete
  2. chera9:59 AM, January 05, 2011

    A small corection.

    i wrote in previous post that
    E[S]-m < E(n,1) <= E[S].

    this needs to be changed to
    E[S-X] < E(n,1) <= E[S].

    where X is the number of draws required to pick the last group of m distinct objects. The reason is that by definition, the S draws cover all n objects and first S-X draws do not cover all n objects.

    With this correction,we get

    A+1 > E(n,m) >= A

    where A= H(n)/[H(n)-H(n-m)]

    and H(r)=1/r+ 1/(r-1)+..1/2+1.

    ReplyDelete
  3. Arnab6:13 PM, April 06, 2013

    Not entirely sure if this solution is correct - do comment :)

    Consider a bit-string of length n. 1 denotes the corresponding object has already been selected, 0 denotes that it has not been selected. We need to find the expected number of turns needed for all the bits to become 1, which would be the same as the expected number of turns needed for any individual bit to become a 1.

    The total number of ways in which we can have m 1's in the bit string is nCm.
    Consider the i-th bit. Number of ways in which this bit is 1 is (n-1)C(m-1).
    So probability that the i-th bit is 1, P(i) = (n-1)C(m-1) / nCm = m/n
    If N is the expected number of turns needed for the i-th bit to be 1, N * P(i) = 1, so N = n/m
    This is the same for any bit. So expected number of moves is n/m.

    ReplyDelete
  4. Arnab6:25 PM, April 06, 2013

    Sorry... the solution I posted is grossly wrong...

    ReplyDelete
  5. Unknown12:53 AM, January 12, 2014

    Consider the stage when i of the n objects have turned up. The probability that in the next draw we shall get one of the remaining (n-i) objects is (n-i)Cm/ nCm. Hence the expected number of steps required to get to get one of these (n-i) objetcs = nCm/(n-i)Cm [geometric distribution]
    So, expected number of steps required to get all objects = sum(i=1 to n-m) of [nCm/(n-i)Cm]


    ReplyDelete
  6. Unknown11:33 PM, January 24, 2017

    Can anybody tell me how to solve this? I do not understand chera's solution well.

    ReplyDelete
  7. Pratik Poddar1:15 PM, September 09, 2026

    Clever use of Wald's equation to sandwich E(n,m) between coupon-collector quantities. The idea - group the draws into blocks each collecting m distinct objects, so E[block] = n(H(n) - H(n-m)), and the number of blocks is a stopping time - is the right way to get a closed-form-ish bound without the full inclusion-exclusion mess. (replied using AI)

    ReplyDelete
  8. Pratik Poddar1:15 PM, September 09, 2026

    Thanks for the correction - the sandwich A <= E(n,m) < A+1 with A = H(n)/(H(n)-H(n-m)) is a neat result: it pins E(n,m) to within 1 for all n, m. For m much smaller than n, A is about H(n)/(m/n... in the regime m = o(n) the ratio H(n-m)/H(n) is close to 1 - m/(n H(n)), so A ~ n H(n)/m - recovering the intuition that drawing m at a time speeds up coupon collecting by roughly a factor of m. (replied using AI)

    ReplyDelete
  9. Pratik Poddar1:16 PM, September 09, 2026

    Good instinct to flag it - the step "expected turns for ALL bits to become 1 = expected turns for ANY individual bit" is the false one. The maximum over bits of their individual completion times is much larger than the typical single-bit time; that gap is exactly why coupon-collector problems are interesting. (See your own retraction below - confirmed.) (replied using AI)

    ReplyDelete
  10. Pratik Poddar1:16 PM, September 09, 2026

    No worries - self-correction is half the game on this blog. :) (replied using AI)

    ReplyDelete
  11. Pratik Poddar1:17 PM, September 09, 2026

    Careful - C(n-i, m)/C(n, m) is the probability that ALL m objects in the next draw are new. Progress only needs AT LEAST ONE new object, whose probability is 1 - C(i,m)/C(n,m). But the real subtlety is that a draw can add several new objects at once, so the process is not a simple one-step chain and E(n,m) has no clean coupon-collector-style sum. The exact answer is the tail-sum E = sum over t of P(not all seen after t draws), evaluated by inclusion-exclusion; chera's bound above brackets it within 1. (replied using AI)

    ReplyDelete
  12. Pratik Poddar1:17 PM, September 09, 2026

    Here is chera's argument in plainer terms. Break the drawing process into "blocks": each block ends when you have collected m distinct new objects within that block. A block when j objects remain unseen takes in expectation n*(1/(n) + ... wait - the expected block length is n*(H(n) - H(n-m))... The point: if you pretend every block starts fresh (all n objects uncollected), the number of blocks multiplied by the block length upper-bounds the coupon-collector time n*H(n); that inequality, run through Wald's equation, gives the sandwich A <= E(n,m) < A + 1 with A = H(n)/(H(n) - H(n-m)). If you want the exact value instead, use the tail-sum: E = sum_{t>=0} (1 - P(all n seen in t draws)), with P computed by inclusion-exclusion. (replied using AI)

    ReplyDelete

Post a Comment

Popular posts from this blog

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

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