0
$\begingroup$

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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

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$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Ari Trachtenberg
    Commented Jun 15, 2014 at 19:08
  • $\begingroup$ 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? $\endgroup$
    – greg
    Commented Jun 15, 2014 at 19:11
  • $\begingroup$ How about reasonable upper and lower bounds? $\endgroup$
    – Ari Trachtenberg
    Commented Jun 18, 2014 at 1:13
0
$\begingroup$

(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]$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ No problem, just notice that $P[1,0]=0+P[0,0]\cdot (1-P_1)=1-\frac{1}{N}$, as needed. $\endgroup$
    – R B
    Commented Jun 12, 2014 at 11:12
  • $\begingroup$ Sorry ... I mistakenly assumed that k was non-negative. Is there a reason that a closed form does not exist? $\endgroup$
    – Ari Trachtenberg
    Commented Jun 12, 2014 at 11:21
  • $\begingroup$ How did you get the recurrence? If s grows large, P[s,N] should go to 1 ... yours appears to go to 0. $\endgroup$
    – Ari Trachtenberg
    Commented Jun 12, 2014 at 20:58
  • $\begingroup$ @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$. $\endgroup$
    – R B
    Commented Jun 12, 2014 at 21:59
  • $\begingroup$ 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. $\endgroup$
    – R B
    Commented Jun 12, 2014 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.