<p>I suspect you won't get a closed form solution for the distribution you're looking for. Think of the seemingly easier problem where $k$ is always chosen to be exactly $2$, and where you get the set $\{1\}$ "for free". This problem is just like asking for a closed-form distribution of the cardinality of the connected component in the Erdos-Renyi graph $G(n,s)$ that contains a specific vertex $v_1$. I'm pretty sure that there's no known closed-form description of this distribution, and that in fact the lower order terms are poorly understood, especially around the critical value $s \sim n \log n$.</p>

CC BY-SA 3.0
2014-06-15T19:08:45.777Z
This is an interesting connection ... is there a reason to think that $k=2$ is necessarily a simpler problem?  Also, I'd be happy with an approximate solution.
Ari Trachtenberg
CC BY-SA 3.0
2014-06-15T19:11:16.577Z
I have no idea whether $k=2$ is a simpler problem. All I was saying is that it's a special case for which there isn't a closed form solution known, and very likely will never be.
what kind of approximation would you be interested in?
greg
CC BY-SA 3.0
2014-06-18T01:13:37.457Z
How about reasonable upper and lower bounds?
Ari Trachtenberg
CC BY-SA 3.0
2014-06-15T01:00:00.023Z
2014-06-15T01:00:00.023Z
greg
<p>(More of an extended comment - it's not readable as a comment).</p>

<p>Are you sure a closed form for it exist?</p>

<p>This is solvable by the following recurrence formula:
$$P[m,k]=P[m-1,k-1]\cdot P_k + P[m-1,k]\cdot(1-P_{k+1})$$</p>

<p>Where </p>

<p>$$P_k = \begin{cases} \frac{(N+1)^{k-2} (N + k )}{N^k} &amp;\mbox{if } k \leq N \\
\ \ \ \ \ \ \ \ \ 0 &amp; \mbox{else}\end{cases} $$</p>

<p>and </p>

<p>$$ P[0,0]=1, \forall k\neq 0: P[0,k]=0$$</p>

<p>The answer you're looking for (the probability of $t$ marked elements) is $P[s,t]$.</p>

CC BY-SA 3.0
2014-06-12T11:12:43.677Z
No problem, just notice that $P[1,0]=0+P[0,0]\cdot (1-P_1)=1-\frac{1}{N}$, as needed.
R B
CC BY-SA 3.0
2014-06-12T11:21:08.580Z
Sorry ... I mistakenly assumed that k was non-negative.  Is there a reason that a closed form does not exist?
Ari Trachtenberg
CC BY-SA 3.0
2014-06-12T20:58:50.480Z
How did you get the recurrence?  If s grows large, P[s,N] should go to 1 ... yours appears to go to 0.
Ari Trachtenberg
CC BY-SA 3.0
2014-06-12T21:59:00.947Z
@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$.
R B
CC BY-SA 3.0
2014-06-12T22:13:26.450Z
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.
R B
CC BY-SA 3.0
2014-06-13T00:47:44.560Z
@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.
Ari Trachtenberg
CC BY-SA 3.0
2014-06-13T20:27:59.223Z
@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)
R B
CC BY-SA 3.0
2014-06-12T08:07:15.383Z
2014-06-12T21:56:36.357Z
2014-06-12T21:56:36.357Z
R B
<h2>Setting</h2>
<p>Consider repeating the following process on the numbers <span class="math-container">$N=\{1, 2, 3, \ldots, n\}$</span>:</p>
<ul>
<li>Pick an integer <span class="math-container">$k \in N$</span>, uniformly at random.</li>
<li>Pick a subset of <span class="math-container">$k$</span> elements from <span class="math-container">$N$</span>, uniformly at random.</li>
</ul>
<p>After picking <span class="math-container">$s$</span> such sets, we repeatedly (until exhaustion) mark each number that is in a set whose other numbers are all marked.</p>
<h2>Example</h2>
<p>For example, if <span class="math-container">$N=\{1,2,3,4,5\}$</span> and <span class="math-container">$s=3$</span>, we might pick the sets <span class="math-container">$s_0=\{1,3,5\}$</span>, <span class="math-container">$s_1=\{1,4\}$</span> and <span class="math-container">$s_2=\{4\}$</span>.  In the marking phase, we'd first mark <span class="math-container">$4$</span> (because in <span class="math-container">$s_2$</span> all 0 other elements are marked), then we'll mark <span class="math-container">$1$</span> (from set s_1), and we'll be done.</p>
<p>More generally, if <span class="math-container">$s=1$</span>, then we know that <span class="math-container">$\frac{1}{N}$</span> fraction of times, we will have marked exactly one element with this process, and <span class="math-container">$\frac{N-1}{N}$</span> fraction of times we will mark no elements.</p>
<h2>Question</h2>
<p>Can anyone provide a closed-form expression for the distribution of the number of marked elements after this procedure for arbitrary <span class="math-container">$s$</span>?</p>
<p><em>P.S.  I am purposefully leaving out the motivation or reference for this algorithm so as not to bias answers.  Those who recognize the motivation are kindly asked not to mention it, unless it specifically helps with the solution.</em></p>

<ds.algorithms><co.combinatorics><pr.probability><coding-theory>
Determining the distribution of results of a simple algorithm
Ari Trachtenberg
# Determining the distribution of results of a simple algorithm

(Asked by: username_0 on 2014-06-12)

## Setting

Consider repeating the following process on the numbers $N=\{1, 2, 3, \ldots, n\}$:

* Pick an integer $k \in N$, uniformly at random.
* Pick a subset of $k$ elements from $N$, uniformly at random.

After picking $s$ such sets, we repeatedly (until exhaustion) mark each number that is in a set whose other numbers are all marked.

## Example

For example, if $N=\{1,2,3,4,5\}$ and $s=3$, we might pick the sets $s\_0=\{1,3,5\}$, $s\_1=\{1,4\}$ and $s\_2=\{4\}$. In the marking phase, we'd first mark $4$ (because in $s\_2$ all 0 other elements are marked), then we'll mark $1$ (from set s\_1), and we'll be done.

More generally, if $s=1$, then we know that $\frac{1}{N}$ fraction of times, we will have marked exactly one element with this process, and $\frac{N-1}{N}$ fraction of times we will mark no elements.

## Question

Can anyone provide a closed-form expression for the distribution of the number of marked elements after this procedure for arbitrary $s$?

*P.S. I am purposefully leaving out the motivation or reference for this algorithm so as not to bias answers. Those who recognize the motivation are kindly asked not to mention it, unless it specifically helps with the solution.*

**Tags:** ds.algorithms, co.combinatorics, pr.probability, coding-theory


---

## 2 answers

### Answer by username_1 on 2014-06-15. Score: 2

I suspect you won't get a closed form solution for the distribution you're looking for. Think of the seemingly easier problem where $k$ is always chosen to be exactly $2$, and where you get the set $\{1\}$ "for free". This problem is just like asking for a closed-form distribution of the cardinality of the connected component in the Erdos-Renyi graph $G(n,s)$ that contains a specific vertex $v\_1$. I'm pretty sure that there's no known closed-form description of this distribution, and that in fact the lower order terms are poorly understood, especially around the critical value $s \sim n \log n$.

> **Comments:**
> **username_0**: This is an interesting connection ... is there a reason to think that $k=2$ is necessarily a simpler problem?  Also, I'd be happy with an approximate solution.  
> **username_1**: I have no idea whether $k=2$ is a simpler problem. All I was saying is that it's a special case for which there isn't a closed form solution known, and very likely will never be. what kind of approximation would you be interested in?  
> **username_0**: How about reasonable upper and lower bounds?  

---

### Answer by username_2 on 2014-06-12. Score: 0

(More of an extended comment - it's not readable as a comment).

Are you sure a closed form for it exist?

This is solvable by the following recurrence formula:
$$P[m,k]=P[m-1,k-1]\cdot P\_k + P[m-1,k]\cdot(1-P\_{k+1})$$

Where

$$P\_k = \begin{cases} \frac{(N+1)^{k-2} (N + k )}{N^k} &\mbox{if } k \leq N \\
\ \ \ \ \ \ \ \ \ 0 & \mbox{else}\end{cases} $$

and

$$ P[0,0]=1, \forall k\neq 0: P[0,k]=0$$

The answer you're looking for (the probability of $t$ marked elements) is $P[s,t]$.

> **Comments:**
> **username_2**: No problem, just notice that $P[1,0]=0+P[0,0]\cdot (1-P_1)=1-\frac{1}{N}$, as needed.  
> **username_0**: Sorry ... I mistakenly assumed that k was non-negative.  Is there a reason that a closed form does not exist?  
> **username_0**: How did you get the recurrence?  If s grows large, P[s,N] should go to 1 ... yours appears to go to 0.  
> **username_2**: @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$.  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_2**: @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)  

---

