All Questions
Tagged with pr.probability co.combinatorics
802 questions
0
votes
1
answer
82
views
Median of cardinality of set union
Let $U$ be an arbitrary finite universe (you can just think of it as $[N]=\{1,2,\ldots,N\}$), and $\mathbf{S} = (S_i)_{i \in [n]}$ ($S_i \subseteq U$) be the sets that we are drawing from. Define a ...
- 29
-1
votes
1
answer
93
views
Variance of bins for N balls into M bins [closed]
If I throw N balls independently into M bins with uniform probability, the expected mean of the M bins is N/M balls.
What is the expected variance of the M bins?
I was thinking of what bin size I ...
- 111
3
votes
1
answer
405
views
Moments of a random variable related to uniform distribution on sphere
Let $u$ be taken uniformly from the unit sphere $\mathbb S^{n-1}$ and $D$ be a diagonal matrix. I'd like to find a general formula for
$$
\mathbb E[(u^\top D u)^m]
$$
for $m=1,2,3, \dots$, in terms of ...
- 188k
3
votes
0
answers
81
views
Combinatorial/probabilistic interpretation of a quantity of union closed family
Let $\mathcal{F}\subseteq2^{[n]}$ be a union-closed family of sets. For a set $S\in[n]$ (not necessary belong to $\mathcal{F}$), define $w_{\mathcal{F}}(S)$ to be the number of subset of $S$ which ...
- 32.5k
8
votes
1
answer
534
views
The cars problem, again
Consider the following simple problem: We are given $2n$ parking spots, labelled from 0 to $2n-1$. There are $n$ cars on the first $n$ spots, and the remaining $n$ spots are free. At every step, every ...
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 ...
CommunityBot
- 1
0
votes
2
answers
116
views
Upper bounds on quotients of binomial coefficients
Let $\gamma>1$ be a real number and let $n\in \mathbb{N}$.
Define $f\colon\mathbb{N}\to[0,1]$
$$
f(n_0) = \frac{\binom{n-n_0}{m}}{\binom{n}{m}},
$$
where
$$
m = \Big\lfloor{\frac{n}{\lceil\gamma ...
- 128k
21
votes
7
answers
14k
views
A balls-and-colours problem
A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the ...
9
votes
1
answer
1k
views
Bounding the probability that two binomials are equal
Note: This question was migrated from this earlier post, where it initially appeared. Following suggestions, I moved this into its own question.
Let $B_{n,p}$ denote the usual binomial random ...
CommunityBot
- 1
2
votes
1
answer
208
views
Proving an exponential sum inequality for symmetric Hamming distance sequences in binary vectors
Background: Let $X = \{0,1\}^k$ represent the set of all binary vectors of length $k$. For two binary vectors $x, y \in X$, the Hamming distance $d_H(x, y)$ is defined as the number of positions where ...
- 349
1
vote
1
answer
75
views
Probability of correctly guessing the maximum event probability of a multinomial distribution
I have a sample from multinomial distribution with $n$ trials, and $k=3$ options. I know that one of the event probabilities $p_i$ is larger than the two others (who are equal). I'm trying to guess ...
- 258
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 ...
- 13.6k
4
votes
0
answers
145
views
Is it easier to exit a box to the right of a box in $\mathbb{Z}^2$ if I remove some edges to the left?
Suppose that I am given the graph $G = (V,E)$ where
$V = \{ 1, 2, \dots 2N+1 \} \times \{ 1, 2, \dots 2N+1 \} $
and there is an edge between two vertices $(n,m)$ and $(n',m')$ if and only if
$\vert n-...
- 1,054
10
votes
2
answers
635
views
Largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$?
What is known about the largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$? I am especially interested when $q=2$, and in the regime where $k$ is fixed an $n\to\infty$. Here are ...
- 46
19
votes
4
answers
1k
views
Generalization of a mind-boggling box-opening puzzle
Motivation. Suppose we are given $6$ boxes, arranged in the following manner:
$$\left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array}\right]$$
Two of these boxes contain a ...
- 1,299
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 128k
21
votes
2
answers
1k
views
Generating random finite groups
I would like a method to efficiently generate a random finite group of a given order $n$.
If there are $g(n)$ non-isomorphic groups of order $n$,
ideally each group would occur with probability $1/g(n)...
- 4,713
1
vote
0
answers
72
views
How to understand "sparse graph limits"
For an $n$-vertex graph $G$, we say it is a sparse graph if $e(G)=o(n^2)$. Otherwise if $e(G)=\theta (n^2)$, we say it is a dense graph.
For a sequence of dense graphs $G_1,G_2,\dots,$ we know that it ...
- 349
5
votes
0
answers
190
views
Number of discrete Lipschitz functions with given Lipschitz constant
Fix $T, K, N \in \mathbb Z_+$. How many distinct Lipschitz functions $f: \{0, \dots, T\} \to \mathbb Z$ are there with Lipschitz constant $K$, and supremum norm at most $N$ satisfying $f(0) = 0$?
In ...
- 6,195
3
votes
0
answers
81
views
Can we remove the restriction on a parameter in Talagrand concentration inequality?
Recently I am trying to use Talagrand concentration inequality to do something on graphs. I find a version from the book of Molloy and Reed ''Graph Colouring and Probabilistics Method''. I attached a ...
- 4,219
2
votes
1
answer
262
views
Randomly fixing elements and transcendence degree
Given $f_1,\ldots,f_n \in \mathbb{F}_q[x_1,\ldots,x_m]$ such that $\deg(f_i) \leq d < q$. Suppose we have for some $1 \leq j \leq m$
$$ \operatorname{trdeg}_{\mathbb{F}(x_1,\ldots,x_j)}\{f_1,\ldots,...
- 341
11
votes
1
answer
992
views
Choosing a relative large density subsequence from a low density sequence
My question is somewhere in the interface of combinatorics, probability, and measure theory. It is quite ad-hoc, and I wonder if there is a counter example.
Consider for example the unit interval $[0,...
- 114k
1
vote
0
answers
44
views
Constrained random sampling from partitioned sets with quotas
Let $D$ be a finite set, $\mathcal{P} = \{D_{i,j}\}_{(i,j) \in I \times J}$ a partition of $D$, $N: J \to \mathbb{N}$ a quota function, and $k \in \mathbb{N}^+$. A subset $F \subseteq D$ is considered ...
- 63.9k
5
votes
2
answers
792
views
How to calculate an integral over the complex unit sphere
We want to calculate the following integral over the complex unit sphere $S^{2n-1}$:
$$\int_{S^{2n-1}} \frac{1 }{|1 - \langle z, \zeta \rangle|^2} \, d\sigma(\zeta),$$
where $ z $ is a fixed point in ...
0
votes
0
answers
63
views
Arrangements of fixed $k$-polyplets in a $n\times n$ matrix
Recently, I asked a question about the number of arrangements of $k$ elements inside a $n\times n$ matrix with certain restrictions. The one I´m actually interested in for this question is in its 2. ...
- 12.9k
1
vote
0
answers
134
views
Number of ways to place 4 kings on nxn chessboard
I have a $n\times n$ chessboard and 4 kings inside it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example:
In the case where the $4$...
- 47
2
votes
1
answer
199
views
Average cluster size of a n-size vector
Given a vector of $n$ cells and $k$ elements in it, we can define a cluster of elements as a contiguous sequence of elements inside the vector.
My goal is to calculate the average cluster size for all ...
- 800
-3
votes
1
answer
144
views
Count arrangements with pairs of attacking kings [closed]
I have a $1\times n$ chessboard and $2$ pairs of kings in it. Both components of each pair of kings must be adjacent in the chessboard, that is, they must be attacking.
Now, I want to calculate the ...
- 13.4k
1
vote
1
answer
170
views
Mean of probability distribution
I have a probability distribution defined by the following density function:
$f(k,j,n,m)=\frac{(m n)! \mathcal{S}_k^{(j)}}{(m n)^k (m n-j)!}$ (With $\mathcal{S}_k^{(j)}$ being the Stirling number of ...
- 188k
0
votes
0
answers
55
views
Counting matrix paths for (n,m>2) matrices
Given a $n\times m$ matrix with $k$ elements inside it, I need to calculate the number of arrangements of those $k$ elements that form at least 1 path from the top to bottom matrix row composed of the ...
- 47
1
vote
1
answer
1k
views
Hamming distance distribution induced by binary hypercube
The following problem arises in a particular machine learning problem:
Assume that we have $n$ independent Bernoulli random variables with parameters $p_i$, e.g. $n=5$ and the $p$ vector is $(0.2, 0....
- 10.4k
9
votes
1
answer
889
views
Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory
In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
- 12.9k
3
votes
1
answer
208
views
The signs of some mean-zero random variables
Let $X$ be a discrete random variable supported on $\{−5,\dots, 6\}$ in which the outcomes have the following respective probabilities: $$\begin{array}{rc}
n & p(n) \\ \hline −5 & 6/36 \\ −4 &...
- 19.7k
5
votes
1
answer
226
views
A polynomial identity involving Wick ordering of a complex power
The problem is related to the paper 1509.02093 by Oh and Thomann, where the authors considered the 2D Wick ordered NLS.
Let $g=a+ib$ be a complex number. Then it is claimed (see (2.7) in the paper and ...
- 7,226
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 ...
9
votes
1
answer
497
views
Quantum probabilistic method?
The probabilistic method uses arguments from probability to prove deterministic statements. This has been applied to diverse fields such as combinatorics, topology and number theory. In this method, ...
- 188k
1
vote
0
answers
84
views
Percolative process distribution not equivalent to coupon collector problem distribution
I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a ...
- 63.9k
2
votes
0
answers
94
views
Concentration inequalities for functions of random binary strings
Let $(X_1,\ldots,X_n)$ be a vector in $\{0,1\}^n$ drawn uniformly at random among all vectors with exactly $k$ $1'$s. I am interested in inequalities for tail probabilities for the random variables $X,...
- 2,183
4
votes
1
answer
261
views
What is the convergence rate of this "infinite monkey"-type probability?
Cross-posted from Math Stack Exchange, where it hasn’t received an answer yet:
Let $S$ be a finite set and $n,m\in\mathbb N$. Consider the process $R=(R_i)_{i\in\mathbb N}$ where all $R_i$ are iid ...
- 1,043
2
votes
1
answer
118
views
Probability that at least one of the first $k$ right-to-left maxima of $\{1, ..., n+m\}$ contains a number from $\{n+1, ..., n+m\}$
Given a permutation $\sigma$ on $[n]=\{1, ..., n\}$, we say an element $i$ is a right-to-left maximum if $\sigma(i)=\max(\sigma(1), ..., \sigma(i))$.
Suppose we sample a random permutation from $\{1, ....
- 34.3k
12
votes
3
answers
2k
views
How to efficiently sample uniformly from the set of $p$-partitions of an $n$-set?
Let $n,p \in \mathbb{N}_+$ with $p \leq n.$ Let $\mathcal{P}$ denote the set of partitions of $\{1, \ldots, n\}$ into $p$ nonempty sets. How can I efficiently sample uniformly from $\mathcal{P}$?
- 4,713
4
votes
2
answers
307
views
Lower bounding a partition-related sum
We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\...
- 43.7k
1
vote
2
answers
305
views
Joint moments like $\tau(XYXYXY)$ in terms of individual moments of free variables $X,Y$
Terry Tao RMT book has the following formula for joint moment of freely independent random variables $X,Y$ in Section 2.5
$$\tau(XYXY)=\tau(X)^2\tau(Y^2)+\tau(X^2)\tau(Y)^2-\tau(X)^2\tau(Y)^2$$
...
2
votes
1
answer
259
views
The probability that iid draws from a mean zero random variable sum to zero
Suppose we have a probability distribution $p(\cdot)$ supported on the integers between $-m$ and $m$ for some positive integer $m$, with $\sum_k kp(k) = 0$. Suppose furthermore that all $p(k)$ are ...
- 24.2k
1
vote
1
answer
976
views
Concentration of the load of the maximally loaded bin ($m$ balls $n$ bins) with nonuniform bin probabilities
There is a common argument used when investigating the concentration of the maximally loaded bin (say $X$ is the maximum load) when $m$ balls are thrown into $n$ bins under the uniform distribution. I ...
CommunityBot
- 1
6
votes
4
answers
452
views
Counting card distributions when cards are duplicated
If we have a deck of $48$ different cards and $4$ players each get $12$ cards, it is well known how to calculate the number of possible distributions: $\frac{48!}{12!12!12!12!}$
In a german card came (...
- 32.1k
3
votes
1
answer
206
views
Fast sampling of matroids
In his classic paper, Donald E. Knuth described how random matroids of fixed rank can be generated.
What is the currently the fastest (in terms of mixing behaviour) known way to sample matroids of ...
- 32.1k
18
votes
2
answers
1k
views
In an Erdős–Rényi random graph, what is the threshold for the property "every edge is contained in at least one triangle"?
Let $G(n,p)$ denote the Erdős–Rényi random graph, where $n$ is the number of nodes and $p$ is the probability for each edge. I'm interested in precisely what range of $p$ the random graph has at least ...
CommunityBot
- 1
5
votes
1
answer
297
views
Expected number of coin flips before you see a $k$-term arithmetic progression of heads
Let $\{X_i\}_{i \in \mathbb Z_+} $ be independent fair coin flips. Write $S := \{i \in \mathbb Z_+\, | \, X_i \text{ is heads}\}$, and define, for an integer $k \geq 3$,
$$Y := \inf \{n \in \mathbb N \...
- 7,514
2
votes
0
answers
109
views
The fluctuations of a random path
Suppose I have a $n \times n$ square grid and for each square, I assign 1 with probability $\frac{1}{2}$ and 0 with probability $\frac{1}{2}$. On the boundary, I put 1s on the lower half and 0s on the ...
- 1,054