Timeline for Coupon collector targeting a collection among many
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2020 at 18:30 | answer | added | RaphaelB4 | timeline score: 0 | |
| Dec 13, 2020 at 14:03 | comment | added | Suvrit | You may find the following relevant: jstor.org/stable/2308930?seq=1 | |
| Dec 12, 2020 at 19:38 | answer | added | esg | timeline score: 0 | |
| Dec 10, 2020 at 23:16 | history | edited | Iosif Pinelis |
edited tags
|
|
| Dec 10, 2020 at 23:15 | answer | added | Iosif Pinelis | timeline score: 2 | |
| Dec 10, 2020 at 19:18 | comment | added | Ian | (You also need to replace $\frac{1}{n}$ with $\frac{1}{n-|s|}$, my bad.) | |
| Dec 10, 2020 at 19:05 | comment | added | Ian | Now this particular problem has some structure that you can exploit. In particular, you can write a version of the system without self-loops Once you prune the self-loops by replacing that $1$ with $\frac{n}{n-|s|}$ and replacing $x \in U$ with $x \in U \setminus s$. Now the graph that you are moving on is a tree, leaving some more hope of an analytical solution of some kind. | |
| Dec 10, 2020 at 19:01 | comment | added | Ian | One can treat this process as a Markov chain on the power set of $U$ where at each time you go from $s$ to $s \cup \{ x \}$ where $x$ is chosen uniformly at random. Of course you don't care about duplicates, so in some cases $s \cup \{ x \} = s$. By conditioning on one step, you can calculate $u(s):=E[T \mid S_0=s]=1+\frac{1}{n} \sum_{x \in U} E[T \mid S_0=s \cup \{ x \}]$ if $s$ does not contain a collection, and $u(s)=0$ if $s$ does contain a collection. This is a system of $2^n$ linear equations in $2^n$ unknowns which you can solve. | |
| Dec 10, 2020 at 18:31 | comment | added | GBathie | @Ian Can you expand a bit on what you mean ? This is something I am not familiar with. | |
| Dec 10, 2020 at 18:29 | comment | added | Ian | Computationally speaking, getting the expectation is a fairly straightforward task with renewal theory that ultimately boils down to an inhomogeneous linear system. Doing this on some cases for the vector $(|C_1|,\dots,|C_n|)$ might give you some insight into e.g. scaling relationships. | |
| Dec 10, 2020 at 18:27 | review | First posts | |||
| Dec 10, 2020 at 19:38 | |||||
| Dec 10, 2020 at 18:21 | history | asked | GBathie | CC BY-SA 4.0 |