Timeline for Determining the distribution of results of a simple algorithm
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 13, 2014 at 20:27 | comment | added | R B | @AriTrachtenberg - So I guess I didn't read the question thoroughly. I assumed the sets come one at a time and only the current set can add an element (which is what the recurrence is built for) | |
| Jun 13, 2014 at 0:47 | comment | added | Ari Trachtenberg | @R.B. I'm afraid I still don't follow. It is possible for no elements to be marked until the last set appears, and then all elements are marked. For example, N={1,2,3,4,5}, s1={1,2}, s2={2,3}, s3={3,4}, s4={4,5} and only when s5={5} are all N elements marked. | |
| Jun 12, 2014 at 22:13 | comment | added | R B | By the way, of course there exists a closed form (as there is a solution for the recurrence) $P[s,t]=f(s,t,N)$, but in general $f(s,t,N)$ could be a complicated formula that grows exponentially large as $s,t$ grows. I'm not sure if this function has a compact form (which was what I asked about). In any case, you might be able to feed the recurrence formula into some solver and hope for a solution. I wouldn't be too optimistic. | |
| Jun 12, 2014 at 21:59 | comment | added | R B | @AriTrachtenberg - $P_k$ is the probability of the $k$'th element being marked by the next random set (given that $k-1$ elements are marked). This means that $P_k$ formula should only hold for $k\leq N$ (thought it was clear, but it's written formally now). You could verify that $\lim_{s\to \infty}P[s,N]=1$. | |
| Jun 12, 2014 at 21:56 | history | edited | R B | CC BY-SA 3.0 |
added 98 characters in body
|
| Jun 12, 2014 at 20:58 | comment | added | Ari Trachtenberg | How did you get the recurrence? If s grows large, P[s,N] should go to 1 ... yours appears to go to 0. | |
| Jun 12, 2014 at 11:21 | comment | added | Ari Trachtenberg | Sorry ... I mistakenly assumed that k was non-negative. Is there a reason that a closed form does not exist? | |
| Jun 12, 2014 at 11:12 | comment | added | R B | No problem, just notice that $P[1,0]=0+P[0,0]\cdot (1-P_1)=1-\frac{1}{N}$, as needed. | |
| Jun 12, 2014 at 8:13 | history | edited | R B | CC BY-SA 3.0 |
added 8 characters in body
|
| Jun 12, 2014 at 8:07 | history | answered | R B | CC BY-SA 3.0 |