Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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}, ...
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 ...
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$...
4 votes
1 answer
264 views

Information for discovering an item-colour assignment in a combinatorial game

We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all ...
2 votes
1 answer
218 views

Probability distribution optimization problem of distances between points in $[0,1]$

Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $X, Y, Z$ three i.i.d. random variables with distribution $\mathcal{D}$, and $T$ a random variable uniformly distributed in $[...
3 votes
1 answer
395 views

Symmetric distribution optimization problem of distances between points in $[0,1]$

Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $x, y, z$ the outcomes of three i.i.d. random variables $X, Y, Z$ with distribution $\mathcal{D}$, sorted in increasing order, ...
2 votes
2 answers
280 views

Combinatorial optimization problem with interdependent constraints on points in $[0,1]$

We are given a set $S$ of $n$ real numbers in $[0,1]$, with $0,1\in S$, and a value $\alpha\in(0,1/2)$. For each ordered triplet $(i,j,k)$ of values contained in $S$ (with $i\le j \le k$), we define ...
2 votes
2 answers
379 views

Probabilistic combinatorial optimization problem on the distances between pairs of points in $[0,1]$

Let $S$ be a set of $n \gg 1$ points lying on the interval $[0,1]$. Given a point $p\in[0,1]$, let $S_p\subseteq S\times S$ be the set formed by all pairs of points $(x,y)$ with $x,y\in S$, such that ...
0 votes
1 answer
340 views

Expectation of the ratio of two discrete random variables with combinatorial constraints

We are given a set $S=\{1, 2, \ldots, n\}$ where $n\gg 1$, and for all indices $1\le i \le n$, $i$ is associated with a real value $\alpha_i\!\cdot\! v_i$, where $\alpha_i\in[0,1]$ and $v_i\in(0,1]$. ...
2 votes
3 answers
290 views

Geometric probabilistic problem on triangles on a plane

We are given a triangle $T$ on a plane $P$, with sidelengths $a$, $b$ and $c$, where $c \ge b \ge a > 0$. A straight line $L$ on $P$ is selected uniformly at random from the set of all the ...
1 vote
1 answer
158 views

Bound for multinomial expansion involving Poisson random variables

Let $x_i, i=1, \ldots n$ be Poisson random variables with parameters $\lambda_i$ correspondingly with condition that $\sum_{i=1}^nx_i=T$. Due to linearity of the expectation one can write: $$ E\left(\...
1 vote
1 answer
134 views

Random optimization problem

Let $V$ be a set of $n$-dimensional vectors such that, for each ${\bf v}\in V$ and for each index $i\in [n-1]$, we have $0\le v_{i+1}\le v_i$. Let $P(\cdot)$ be a discrete probability distribution ...
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. ...
13 votes
1 answer
869 views

Lotteries, Turan's problem, and minimization of risk

Suppose I am a high-volume broker aiming to make some money on a state lottery. In this lottery, six balls are drawn from a population of (let's say) 50, without replacement. A ticket is a choice of ...