All Questions
Tagged with co.combinatorics pr.probability
802 questions
0
votes
0
answers
55
views
Modeling player interactions in multi-dimensional rating systems
In traditional rating systems (such as Elo), a player's strength is represented by a single scalar value, which is assumed to be consistent across different opponents. However, in some games, the ...
- 1
3
votes
0
answers
54
views
Multi-type Galton-Watson-like process where only majority-type is allowed to reproduce
Are you aware of any research papers that have explored a multi-type Galton-Watson process in which only particles of the majority type are permitted to reproduce in each generation?
I've been unable ...
- 56
4
votes
2
answers
427
views
Binomial coefficient asymptotics
What is the probability that the number of heads in $n$ fair coin tosses is exactly $\lfloor n/2 + c\sqrt{n} \rfloor$
for $c \leq O(1)$, $n > \omega(1)$?
Of course the answer is
$$ \frac{1}{2^n} \...
- 359
1
vote
0
answers
62
views
Nonintersecting witnesses of connectivity events in graphs
In my research I stumbled across a following result:
Let $G = (V, E)$ be a multigraph with three chosen vertices $a, b, c \in V$. We color its edges into red and blue colors: $E = R \sqcup S$. Events ...
0
votes
2
answers
239
views
Computing the expectation of a quadratic matrix form involving Bernoulli and Gaussian distributed matrices
I am working with two random matrices, $Z$ and $H$:
$Z$ is an $n \times K$ matrix with entries sampled i.i.d. from a Bernoulli distribution: $Z_{ij} \sim \mathrm{Bernoulli}(p)$.
$H$ is a $K \times K$ ...
- 37
1
vote
0
answers
91
views
Large deviation inequalities for number of coupon types collected by a coupon collector with fixed budget
In the generalized Coupon Collector's Problem, there are $N$ types of coupon, and for any $i \in [N] := \{1,2,\ldots,N\}$, $p_i \ge 0$ is the probability of obtaining a type-i coupon on any trial. ...
- 6,853
2
votes
0
answers
56
views
Dirichlet series solution to Poisson Point Process question (repost from math.SE)
Reposting here because the bounty on the original math.SE post expired, with no solutions or comments received.
For any discrete subset $S$ of $\mathbb{R}^d$, consider a digraph formed by placing an ...
- 121
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}, ...
4
votes
1
answer
197
views
On a double sum involving binomial coefficients
For natural $n$, let
\begin{equation}
p_n:=2^{1-n}\sum_{v=1}^l \binom l{(v+l)/2}1(v\equiv l)
\sum_{u=1-v}^{v-1}\binom k{(u+k)/2}1(u\equiv k), \tag{1}\label{1}
\end{equation}
where $k:=\lfloor(n+1)/...
- 128k
1
vote
0
answers
60
views
Correct dependence for "Local Coloring"
In Alon-Spencer's book, Probabilistic Lens #8, it is proven that for each $k$, there exists $\epsilon = \epsilon(k)>0$ such that for all large $n$, there exists an $n$-vertex graph $G$ with ...
- 3,499
-3
votes
1
answer
117
views
Combinatorial meaning of a reduced fraction in a simple probability problem?
A routine exercise for undergraduates says: Given that the number of successes in $20$ independent Bernoulli trials was $8,$ what is the conditional probability that exactly $3$ of those $8$ successes ...
1
vote
0
answers
92
views
Can we prove the following statement for recurrence relation?
For every integer $n$, we have the following recurrence:
$a_{i}= p^i(1-p)^{n-i}\binom{n}{i} -\sum_{j=i+1}^na_j\binom{j}{i}$.
Can we prove that for every $n$ and $p<1/\sqrt{n}$, it holds that $\...
- 11
1
vote
0
answers
77
views
Distribution of colour pairs from a random matching
Given $a$ many red balls and $b$ many blue balls, with $a+b$ even, suppose we chose a random matching between the $a+b$ balls. What is the distribution of the number of red-red and red-blue (and blue-...
- 129
1
vote
1
answer
186
views
Expected cardinal of the intersection between a random subset and a fixed subset
I have a set of size $n$, and a fixed subset $A$ of cardinal $k$. I take a random subset $X$ of cardinal $d$. I need to compute the expected cardinal of the intersection between $A$ and $X$.
I tried ...
- 11
2
votes
1
answer
115
views
Randomly chosen walk of fixed length
Let $G=(V, E)$ be the graph on vertices $V = \{0, \cdots, k\}^n$, where vertices $(v_1, \cdots, v_n)$ and $(w_1, \cdots, w_n)$ share an edge iff $\lvert v_i - w_i\rvert \leq 1$ for all $i$.
A walk of ...
- 138
1
vote
0
answers
216
views
Classical and free cumulants, symmetric functions, and inverses (references), related to associahedra, parking functions, noncrossing partitions
Looking for references for one or more of the following four sets of partition polynomials 1a) through 4a), particularly those which present geometric / topological combinatorial interpretations.
...
- 10.5k
9
votes
1
answer
1k
views
The length of the longest consecutive string of heads or tails that occur asymptotically almost surely when a unbiased coin is flipped repeatedly
Consider an unbiased coin being flipped $n$ times, and suppose we label the outcomes as Heads = 0, and Tails = 1. Then the result of the flipping is a finite binary sequence of length $n$. Let us ...
- 91
3
votes
2
answers
257
views
Grouping lists together in a proportional election: image of a Dirichlet distribution by the D'Hondt method of proportional allotment
A real-world motivation for this question is given below. But first let me recall what the Jefferson-D'Hondt “greatest divisors” method of proportional allotment (often used in electoral systems to ...
- 32.5k
6
votes
1
answer
355
views
Probabilistic problem on random spanning trees
Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....
- 1,677
3
votes
1
answer
229
views
Maximum cardinality of separated sets in the Hamming distance
This question is motivated by section 15.1 (Codes) of Alon and Spencer's The probabilistic method.
Fix $\alpha<\frac{1}{2}$ and for each $n\in\mathbb{N}$ let $\{0,1\}^n$ be the length $n$ binary ...
- 10.6k
1
vote
1
answer
195
views
Concentration of a certain simple / well-structured random multilinear polynomial with growing degree
Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
- 6,853
0
votes
1
answer
119
views
How many samples do you need to get constant dispersion?
Let $C_n$ be the hypercube $[-1,1]^n$. For $a_1,\cdots,a_s \in C_n$, define its dispersion $D(a_1,\cdots,a_s)$ as $\max_{x \in C_n}\min_{i \in [s]} \|x-a_i\|_{2}$. Let $0< \lambda < 1$ be a ...
- 261
2
votes
0
answers
148
views
Union of two copies of uniform spanning forest on $\mathbb{Z}^3$ is transient? [closed]
Let $G$ be the (random) graph which is the union of two independent copies of the uniform spanning forest on $\mathbb{Z}^3$.
Question: Is (the simple random walk on) $G$ transient almost surely?
- 41
2
votes
1
answer
201
views
Dispersion of a "random" subset of $[-1,1]^2$
Let $C$ be the square $[-1,1]^2$. Let $a_1,\dots,a_m$ be points chosen independently and uniformly at random from $C$. Let $d_m$ (dispersion) be the random variable $\max_{x \in C}{\min_{j \in [m]}{\|...
- 261
4
votes
0
answers
414
views
Explicit formula for tournament sequence
I am looking for an explicit formula for a sequence. The sequence is generated as follows:
There is a tournament with $10$ teams. In the beginning, all teams have a 0-0 win-loss record. The teams are ...
- 41
4
votes
1
answer
167
views
A probability problem in the conjugacy classes of symmetric group
Assume that $\sigma\in S_n$ has the cycle type $(p,.,p,1,..,1)$ where $p>2$ is a prime and the numbers of $1$ maybe $0$. If $\sigma_1$ and $\sigma_2$ are chosen uniformly in the conjugacy class of $...
- 253
2
votes
1
answer
224
views
Approximate size of the image of functions $f:[n]\to[n]$ [closed]
The following is inspired from the most recent riddle of the week of the German news magazine Der Spiegel.
For any positive integer $n\in\mathbb{N}$, let $[n]$ denote the set $\{1,\ldots,n\}$. Let $...
- 48.9k
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 + \...
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 ...
- 48.9k
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, ...
- 282
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
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] \...
- 390
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 ...
- 1,677
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 ...
- 57
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_\...
- 715
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 ...
- 1,677
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,677
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 ...
- 33
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
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
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
6
votes
2
answers
723
views
Threshold function for a graph not being planar
A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.
It is well-known that every ...
- 557
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,...
