All Questions
23 questions
16
votes
6
answers
3k
views
analog of principle of inclusion-exclusion
When I teach elementary probability to my finite math students, a common error is to mix up the concepts of disjointness and independence. At some point I thought that it might be helpful to some ...
- 2,150
15
votes
2
answers
3k
views
Bounding sum of multinomial coefficients by highest entropy one
When does the following hold?
$$\sum_{(i_1,\ldots,i_k)\in E}
\frac{n!}{i_1! \ldots i_k!}
\le \exp(n H^*)$$
where $H^*=\max_{(i_1,\ldots,i_k)\in E} -(\frac{i_1}{n}\log \frac{i_1}{n}+\ldots +\frac{...
10
votes
1
answer
846
views
A Johnson-Lindenstrauss lemma for finite fields?
Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwise distances between ...
- 7,633
9
votes
1
answer
640
views
Inner product over finite fields
Let $F$ be a finite field,
For every $c \in F$, let $X_1, X_2,..., X_9, Y_1,..., Y_9$ be independent non-zero random variables over $F$.
Denote $X=(X_1,...,X_9)$, $Y=(Y_1,...,Y_9)$, also let $\...
- 93
9
votes
0
answers
467
views
Measuring the randomness of texts
The question concerns statistic properties of random words in a finite alphabet $A$.
By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$.
...
- 41.9k
8
votes
3
answers
411
views
Identifying a subset with as few tests as possible
Informal description: You are given a set of $n$ blood samples, each having probability $p$ of being infected with a disease. Your goal is to determine the set $P$ of infected samples with as few ...
- 32.5k
7
votes
3
answers
790
views
Expected cardinality of a randomly chosen element of the family of subsets of $\{1,\ldots,n\}$ with at most $k$-elements
Assume that $1\le k \le n$ and let $\mathscr{Z}$ be the family of all subsets of $\{1,\ldots,n\}$ with at most $k$ elements. Pick a random element $X$ of $\mathscr{Z}$ (we consider the probablity ...
- 1,658
7
votes
3
answers
330
views
Quantifying the noninvertibility of a function
Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is ...
- 19.7k
6
votes
1
answer
527
views
Can information be extracted more precisely using more random trials?
Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(x))$. What is the min of $n^{-1}H(y^n|f(x^n))$ over maps $f$ with range $\lbrace 1,\dots,\exp nR\}$, taking $n\to \infty$?
5
votes
3
answers
1k
views
A conjecture about the entropy of matrix vector products
Consider a random $m$ by $n$ partial circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$ and let $m < n$. Now consider a random $n$ dimensional vector $v$ ...
- 3,377
4
votes
1
answer
2k
views
Square of Binomial Coefficient
Background
I'm modeling Genetic Algorithm(GA) with Markov chains and deriving the expression for the expectation of the first hittig time in the MC with 1 absorbing state and $l-1$ transient states. ...
- 355
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 ...
- 1,677
4
votes
1
answer
839
views
A balls into bins problem with combinatorial constraints
We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into ...
- 1,677
3
votes
4
answers
1k
views
Apply doubly stochastic matrix M to a probability vector, then entropy increases?
Consider a vector $p =(p_1,\dots,p_n)$, $p_i>0$, $\sum p_i = 1$
and a matrix $M_{ij}$, which is doubly stochastic: $\sum_i M_{ij} = 1, \sum_j M_{ij} = 1, M_{ij} > 0$.
Question 1 Just apply ...
- 24.9k
3
votes
1
answer
376
views
The degrees in a random subgraph
Fix some positive integers $N$ and $d_k$, $k=1,2,\dots$ with $N=\sum_{k=1}^\infty d_k$.
Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ ...
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. ...
- 1,677
3
votes
0
answers
143
views
finding rank-3 tensors compatible with a rank-2 tensor projection
I am interested in the following problem: Consider a rank-3 symmetric tensor $\boldsymbol{\sigma}$ with $\sigma_{ijk}$ where $\sigma_{ijk}$ can be 0 or 1, and the symmetry is with respect to any ...
- 41
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}, ...
2
votes
1
answer
199
views
Do enough permutations of an initial set probably cover most permutations?
Fix $\alpha, \epsilon \in(0,1)$. Take $(S_n)_n$ to be any sequence of sets with each $S_n$ containing $ \lceil (n!)^\alpha\rceil$ permutations of $n$ elements. Also build another sequence of sets $(...
2
votes
0
answers
979
views
How to calculate/approximate expectation of function of a binomial random variable?
Hi,
I am stuck at following problem in my research.
Suppose that $M=m$ is a random variable with binomial distribution with parameters $n,p$. The constants $r$ and $\gamma$ are greater than zero. $\...
- 21
1
vote
1
answer
106
views
Almost-parallel corners of the hypercube in high dimensions
Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...
- 435
1
vote
1
answer
105
views
What is the distribution of a Cartesian power of a collection of iid uniform points? (renewed)
The following question was asked recently at https://mathoverflow.net/questions/326631/what-is-the-distribution-of-a-cartesian-power-of-a-collection-of-iid-uniform-poi :
Take a rectangle with ...
- 128k
1
vote
1
answer
197
views
Probability distribution on Python-dictionary-like objects?
I would like to examine information-theoretical properties of random variables that take as values objects which are akin to dictionaries in the Python programing language.
That is, each sample of the ...
- 11