Skip to main content

All Questions

4 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3 votes
0 answers
190 views

Probabilistic optimization problem on tree vertex selection without replacement proportional to the degree

We are given a tree $T(V,E)$ with $|V|=n$ vertices, where $V=\{v_1,v_2,\ldots, v_n\}$. We denote by $d_i$ the degree of vertex $v_i$ for all $i\in\{1,2,\ldots,n\}$. In a sequential fashion, we select ...
Penelope Benenati's user avatar
3 votes
0 answers
178 views

Partitioning the coupons collected in the classical coupon collector's problem

Suppose that there is an urn containing $n$ different coupons, from which $m$ coupons are being collected, equally likely, with replacement. Let $C(m)$ be the whole set of the $m$ collected coupons. ...
Penelope Benenati's user avatar
2 votes
0 answers
68 views

What is an efficient non-adaptive group testing scheme if the number of defectives, $d$, grows proportionally to the number of items, $n$?

Suppose that for some $p \in \left(0, 1\right)$ and some $n \in \mathbb{N}$, we have $n$ independent Bernoulli random variables, $X_{1}, X_{2}, \dots, X_{n}$, each with mean $p$. We shall call $X_{1}, ...
Matthew Barber's user avatar
2 votes
0 answers
103 views

Optimization problem on randomly selecting subintervals from a given interval with combinatorial constraints

We select uniformly at random $k$ pairwise disjoint intervals from a given interval $[0,s]$ with length respectively equal to $\ell_1, \ell_2, \ldots, \ell_k\ $, i.e., we select uniformly at random $k$...
Penelope Benenati's user avatar