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 ...
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 ...
- 1,462
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 ...
- 1,608
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 ...
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 ...
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
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 ...
- 48.9k
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
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$ ...
- 13
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
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 ...
- 267
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 ...
- 1,190
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,...
- 502
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
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 ...
- 11
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 ...
- 109
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. ...
- 47
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
-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 ...
- 47
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 ...
- 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 ...
- 47
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
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 ...
- 333
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, ...
- 654
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 ...
- 47
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,288
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
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, ....
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 ...
- 141
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,442
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(\...
- 715
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 ...
- 19.7k
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 \...
- 6,195
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
0
votes
0
answers
82
views
High probability bound on number of sparse solutions to Gaussian linear system
Suppose we have a random matrix $A \in \mathbb{R}^{m \times n}$ with all entries i.i.d. from the standard Normal distribution $\mathcal{N}(0, 1)$. Suppose $k$ divides $n$, and let $S \subseteq \mathbb{...
- 43
0
votes
1
answer
189
views
Constructing a family of $3$-wise independence functions from $\mathbb{Z}_p^n \rightarrow \mathbb{Z}_p$
A family of function hash functions $\mathcal{H}:\{h:N\rightarrow M\}$ is call $k$-wise independent if whenenver $h$ is drawn uniformly from $\mathcal{H}$, let $x_1,\ldots,x_k$ be distinct elements of ...
- 121
1
vote
0
answers
84
views
How can one build a min-2-wise independent small sample space from min-3-wise permutations?
I have been studying a polynomial-size set of permutations from one of my lectures. The below image, taken from the lecture notes PDF, illustrates how to construct min-3-wise permutations.
My ...
- 43
2
votes
0
answers
71
views
Distance distribution for Cayley graphs of the fintie Heisenberg groups H3(Z/nZ) approaches Gaussian for large "n"?
I wonder several questions about Cayley graphs of finite Heisenberg groups H3(Z/nZ).
Question 1: do we know the diameter dependence on "n", at least for the standard choice of generators ? ...
- 24.9k
3
votes
1
answer
134
views
The pseudo-randomness/jumbledness of $G(n, p)$
In his original paper on pseudo-randomness, Thomason defines a graph to be $(p, \alpha)$-jumbled if, for every set of vertices $U$, $|e(U) - p\binom{|U|}{2}| \leqslant \alpha |U|$. The paper states ...
- 41
4
votes
0
answers
1k
views
Number of arrangements that contain at least 1 path from top to bottom of 2D matrix
I have a $n\times n$ matrix of objects. $n'$ objects are black, and the rest $n^2-n'$ are white.
With that information, I can easily calculate the total number of black element arrangements that exist ...
- 47
10
votes
1
answer
477
views
Where does the definition of ($\infty$-)groupoid cardinality come from?
The cardinality of a finite set $X$ is the number of its elements. Once you know that, you would define the groupoid cardinality of a $\infty$-groupoid $X$ as the quantity
$$\lvert X\rvert := \sum_{[x]...
- 609
7
votes
2
answers
347
views
Matrices over $\mathbb{F}_p$ that have nonzero determinant under any element permutation
$\DeclareMathOperator\GL{GL}$A few months ago, the following discussion took place on AoPS, concerning matrices that have nonzero determinant under any permutation of their entries: https://...
- 541
7
votes
1
answer
156
views
Nearest neighbors on random complete graph
Consider the complete graph on $2n$ vertices, where the ${2n \choose 2}$ edges have distinct lengths in uniform random
order. So each vertex $v$ has a nearest neighbor $N(v)$, across the shortest ...
- 236
0
votes
1
answer
231
views
Concentration inequalities for random sampling without replacement
Let a population $C$ consist of $N$ values $c_1, c_2, \cdots, c_N$, with $c_i\in \{0,1\}$. Let $X_1, X_2, \cdots, X_n$ denote a random sample without replacement from $C$ and let $Y_1, Y_2, \cdots, ...
- 105
0
votes
1
answer
335
views
How far does a random walker travel before returning to the origin?
Consider a (continuous time) simple symmetric random walk on $\mathbb Z$, starting from the origin. Let us denote this random walk by $\{X_t: t\geq 0\} $. It is well known that this random walk is ...
- 59
1
vote
0
answers
122
views
On the derivation of some asymptotic expressions involving combinatorics
My questions come from the supplementary material in a recent preprint Nonequilibrium statistical mechanics of money/energy exchange models. My first question comes from page 35. Specifically, suppose ...
- 730
2
votes
2
answers
286
views
Finding an easy example applying the general Lovász local lemma
Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.
General Lovász local lemma: Consider a set $...
- 1,190