All Questions
Tagged with pr.probability co.combinatorics
802 questions
3
votes
1
answer
271
views
The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones
What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically ...
- 32.1k
3
votes
1
answer
142
views
Probabilistic method Alon and Spencer Azuma's inequality
Theorem 7.5.2 states:
Let $v_1, \dots, v_n$ be vectors with $\|v_i\| \leq 1.$ Let $\epsilon_1, \dots, \epsilon_n \in \{-1, 1\}$ be independent with uniform probability and let $X=\|\epsilon_1 v_1 + \...
- 128k
8
votes
1
answer
478
views
Scheduling "parent talks" at school
Real life motivation. In my younger son's class, there are $18$ students. His teacher provided $18$ time slots for the parents of each child to have a 30-minute conversation of their kid's progress in ...
- 54.2k
1
vote
1
answer
268
views
Entropy upper bound for the union of uniform distributions over union-closed families
The following question is motivated by the recent breakthrough result by Justin Gilmer on the union-closed sets (aka Frankl) conjecture.
Let $\mathcal{F}\subseteq\mathcal{P}(\mathbb{N})$ be a finite, ...
- 23.2k
1
vote
1
answer
199
views
Rademacher complexity for a family of bounded, nondecreasing functions?
Let $\{\phi_k\}_{k=1}^K$ be a family of functions mapping from an interval $[a, b]$ to $[-1, 1]$.
That is, $\phi_k \colon[ a,b] \to [-1, 1]$ are nondecreasing maps on some finite interval $[a, b] \...
- 410
7
votes
0
answers
464
views
Mistakes in Logan and Shepp's famous paper on Young Tableaux?
In their landmark paper from 1977 named "A Variational Problem for Random Young Tableaux" Logan and Shepp obtained a number of results concerning asymptotic properties of Young Diagrams ...
- 116
3
votes
0
answers
187
views
Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets
Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
- 1,677
7
votes
0
answers
162
views
Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets
We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
- 1,677
3
votes
1
answer
266
views
A linearly distributed version of the balls into bins problem
Some years ago, I found a paper with all the formulas for the balls into bins problem when the "areas" (i.e., probabilities to capture a ball) of the bins are all different. However, the ...
- 1,677
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$...
- 1,677
1
vote
1
answer
318
views
How to calculate this limit (if exist)?
I have just asked the calculation of the following summation see here $$S(a,b,m,n_1,n_2)=\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k}, $$
which is motivated by the calculation of the ...
- 128k
4
votes
0
answers
93
views
(Asymptotic) Cycle structure in a random permutation given total number of cycles?
A random $N$-permutation is the one drawn uniformly from all possible permutations on $N$ points.
We know that the expected number of cycles of length $\ell$ in a random $N$-permutation, $\mathbb{E}C_\...
- 12.9k
3
votes
1
answer
218
views
Bounding the number of facets of a polytope to approximate a given convex shape in higher dimensions
We are given a convex shape $S$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume $V(S)$ of $S$ be $\tfrac12$ (I guess nothing changes for any other fixed ...
- 60.5k
4
votes
0
answers
144
views
Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$
We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...
- 1,677
7
votes
1
answer
186
views
$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary
Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...
- 1,043
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$?
- 716
1
vote
0
answers
84
views
Constructing k-wise independent variables over a general set
We have seen in class a polynomials based construction that builds in $O(n^k)$ time, $n$ random variables, $k$-wise independent, over a field with $n$ elements. More specifically, you generate all the ...
- 11
6
votes
0
answers
164
views
Hamilton cycles in random graphs with just enough connectivity
What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
- 7,545
16
votes
0
answers
1k
views
Optimal monotone families for the discrete isoperimetric inequality
Background: the discrete isoperimetric inequality
Start with a set $X=\{1,2,...,n\}$ of $n$ elements and the family $2^X$ of all subsets of $X$.
For a real number $p$ between zero and one, we consider ...
- 63.9k
15
votes
1
answer
1k
views
Has the technique of "sprinkling" been used in studying random matrices?
In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...
- 114k
0
votes
1
answer
116
views
What's the cumulative probability of these particular bags of liquorice allsorts?
After eating a bag of liquorice allsorts in one sitting, as one does, I noticed that it had contained an unusual amount of brown ones (which, you will agree, are an abomination that should never have ...
- 123
3
votes
3
answers
2k
views
Probability of a given string being a substring of another string
I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$ over $...
- 1,171
41
votes
4
answers
2k
views
What is the probability two random maps on n symbols commute?
It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
- 7,545
0
votes
0
answers
222
views
Convergence to normal distribution in total variation distance
Let $X_i$ be independent, identically distributed random variables with a uniform distribution on $\{M+1,...,2M\}$ (say), where $M$ is a positive integer. What would be a lower bound for how rapidly $...
- 20.2k
3
votes
0
answers
151
views
Permutahedra Euler characteristic polynomials from cumulant-moment relation, a combinatorial proof?
Given the formal Taylor series, or e.g.f.,
$f(x) = 1 + \sum_{n \geq 1} m_n \; \frac{x^n}{n!}$,
the classical formal cumulants $c_n$ are generated from the formal moments $m_n$ via
$ \sum_{n \geq 1} ...
- 10.5k
0
votes
0
answers
45
views
Lower bound for the gap in an interval randomly divided into $M$ pieces
Assume we randomly take $M$ integers $t_1 \le t_2 \le \dots \le t_M$ from the set of integers $\{ 1, 2, \dots, T \}$ such that $t_M = T$. We further denote $t_0 = 1$ for convention. For each $s \in [1,...
39
votes
9
answers
3k
views
The shortest path in first passage percolation
Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)
Consider a square planar grid. (The vertices are pair of ...
- 2,821
23
votes
2
answers
910
views
Random permutations of Z_n
In "The maximum number of Hamiltonian paths in tournaments" by Noga Alon, the author states the following without proof (equation 3.1):
"Consider a random permutation $\pi$ of $\mathbb{...
- 4,713
6
votes
3
answers
855
views
Series involving power of the index
How to prove the following identity
$$ \sum_{n=1}^{\infty} \frac{n^{n-1} e^{-n}}{n!} = 1$$
analytically (which can be confirmed with $Mathematica$)? The standard trick for geometrical series does not ...
- 14.2k
9
votes
1
answer
1k
views
Vertex connectivity of random graphs?
Consider simple, undirected Erdős–Rényi graphs $G(n,p)$, where $n$ is the number of vertices and $p$ is the probability for each pair of vertices to form an edge. Many properties of these graphs are ...
- 1,354
7
votes
2
answers
366
views
On permanent of a square of a doubly stochastic matrix
Let $A = (a_{i,j})$ be a double stochastic matrix with positive entries. That is, all entries are positive real numbers, and each row and column sums to one. A permanent of a matrix $A = (a_{i,j})$ is ...
- 341
1
vote
0
answers
123
views
On probability of coprimality of a list of numbers
We know $r$ randomly chosen integers are coprime with probability $\frac1{\zeta(r)}$.
Pick a bound $N$ and pick $k\lceil N^{\alpha}\rceil$ uniformly random integers in $[0,N^{\alpha+\beta}]$ where $\...
- 13.9k
1
vote
1
answer
183
views
Expectation of edge weights on the complete graph
Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random ...
- 37.7k
2
votes
1
answer
272
views
A generalization of negative binomial distribution
Assume we have a set of $n$ balls. For each step, we uniformly pick one ball and label it if it is not labeled. Or otherwise move on to next step. I am wondering what is the distribution of number of ...
- 13.9k
3
votes
1
answer
135
views
Cycle counts in Ewens measure as $\theta$ diverges
For $w$ a permutation, let $c(w)$ denote the total number of cycles and $c_i(w)$ denote the number of $i$-cycles.
The Ewens measure is a one-parameter probability distribution on permutations where ...
- 24.2k
2
votes
1
answer
383
views
Lower bound and limit of a sum with binomial coefficients
Let
$$A_k = \sum_{i=1}^k i {3k-2i-1 \choose i-1} {2i-2 \choose k-i}$$
$$B_k = \sum_{i=1}^k i {3k-2i-2 \choose i-1} {2i-1 \choose k-i}$$
$$C_k = \sum_{i=1}^k (3k-2i-2) {3k-2i-3 \choose i-1} {2i\...
- 2,836
6
votes
0
answers
99
views
q-binomial-like series with exponentials defining probability distribution
Recently I encountered the series
$$f(d) = \frac{1}{(t;t)_\infty} \sum_{k=0}^\infty \frac{(-1)^k t^{\binom{k}{2}}}{(t;t)_k} e^{-t^{d-k}}$$
where $(t;t)_n = \prod_{i=1}^n (1-t^i)$, and $0 < t < 1$...
- 568
4
votes
3
answers
269
views
Existence of (near) equidistant codewords
My question is originally related to coding theory, but fairly easy to state in pure combinatorial way.
Fix $k\in\mathbb{N}$, $\beta\in(0,1)$ and consider the binary cube $\Sigma_n = \{0,1\}^n$ ...
- 1,096
5
votes
4
answers
917
views
Limit of a sum with binomial coefficients
Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$
$$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$
$$C_k = \frac{\sum_{i=1}^k(...
- 34.3k
1
vote
1
answer
905
views
Balls and bins: Exact probability
Suppose there are $m$ balls to be randomly thrown into $n$ bins ($m>n$). Let $X_i$ be the number of balls ending up in bin $i$.
Let $X_{max}$ be the heaviest bin and $X_{min}$ be the lightest bin. ...
- 1,446
0
votes
0
answers
58
views
Impact of reducing the number of distinct elements in the Count distinct problem
I am dealing with the Count distinct problem and Space saving algorithm. The problem goes like that:
I have a stream of $N$ elements. The number of distinct elements is $D$. Space saving algorithm is ...
- 11
1
vote
2
answers
302
views
Counting permutations defined by a simple process
Consider $n$ labeled balls, $k$ of which are red and $(n-k)$ blue. Given a permutation of these balls, we tick $n-1$ times. For the $i$-th tick, if the $i$-th ball in the permutation is red, then it ...
- 128k
3
votes
1
answer
162
views
Recurrence relation for the moments of the GOE
The Harer-Zagier formula provides a three term recurrence relation for the expected value of the single-trace operator $\mathrm {Tr}(X^k)$ where $X$ is a $N\times N$ matrix from the GUE. Is there an ...
- 1,295
14
votes
3
answers
2k
views
Concentration bounds for sums of random variables of permutations
I'm trying to find theorems regarding random variables derived from sampling permutations, specifically concentration bounds.
As an example, let $X_i$ be the $\{0,1\}$-random variable that represents ...
- 1,724
8
votes
0
answers
304
views
"Meritocratic" pyramid schemes
There have been a couple of times in my life when people from multi-level marketing organizations attempted to recruit me. I listened to what they had to say, and both times I did not get involved ...
- 63.9k
7
votes
1
answer
390
views
Combinatorial/probabilistic statements having $F_{\text{un}}$/$F_q$ geometric interpetation
$\newcommand{\Fun}{F_\text{un}}$There was lots of "Fun with $\Fun$" (field with one element) in recent years.
One of the points is that it provides bridge between geometrical and ...
- 12.9k
1
vote
0
answers
122
views
Probability puzzle on partitions
Consider a set $U$ of size $n$ and let $\mathcal{S}$ be the set of all $(n/2)$-subsets of $U$ (assume $n$ is divisible by 4). Let $P$ be a partition of $\mathcal{S}$ into $k$ blocks $B_1,\dots,B_k$.
...
- 11
17
votes
1
answer
1k
views
Can this probability be obtained by a combinatorial/symmetry argument?
Suppose that $a_1,\dots,a_n,b_1,\dots,b_n$ are iid random variables each with a symmetric non-atomic distribution.
Let $p$ denote the probability that there is some real $t$ such that $t a_i \ge b_i$ ...
- 1,989
20
votes
3
answers
1k
views
The Angel and Devil problem with a random angel
In the classic version of Conway's Angel and the Devil problem, an angel starts off at the origin of a 2-D lattice and is able to move up to distance $r$ to another lattice point. The devil is able ...
- 31