Timeline for How many trial picks expectedly sufficient to cover a sample space?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 28, 2010 at 0:52 | answer | added | Douglas Zare | timeline score: 2 | |
| Jan 27, 2010 at 21:21 | comment | added | Kevin P. Costello | As you expected, it is always rational. If you let F(n,k,r) denote the expected number of additional sets you need when you already have covered k elements of your n, then you can set up a linear recurrence for F(n,k,r) in terms of F(n, k-1, r), F(n, k-2, r), ..., F(n, k-r, r) by looking at how many elements are covered by your next set. Combined with the boundary condition F(n,0,r)=0, you could in theory solve to get F(n,0,r) as a rational number. This is what is done in the "coupon collector" problem referenced by Tal K (the case r=1), but is impractical for, say, n/r bounded. | |
| Jan 27, 2010 at 20:47 | answer | added | Zev Chonoles | timeline score: 1 | |
| Jan 27, 2010 at 20:41 | answer | added | Tal K | timeline score: 2 | |
| Jan 27, 2010 at 20:26 | history | edited | Steve Huntsman |
edited tags
|
|
| Jan 27, 2010 at 20:15 | comment | added | Zev Chonoles | You should edit your question to not use $n$ for both the cardinality of the set and the number of steps to cover the set. Also, interesting question! I look forward to seeing what people come up with for this one. | |
| Jan 27, 2010 at 19:52 | history | asked | amaanush | CC BY-SA 2.5 |