All Questions
Tagged with pr.probability co.combinatorics
802 questions
20
votes
2
answers
819
views
A probability question related to extremal combinatorics
$k$ people play the following game: person $i$ independently picks a subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution $p$ on the $2^n$ subsets; each person uses the same ...
CommunityBot
- 1
6
votes
1
answer
224
views
A Markov consensus
Consider the following process. You start with $n$ nodes in different colors $c=c1,c2,...$ (representing an opinion). Say, $n=5, c=1,2,3,4,5$. Now each node checks which colors have weak majority (...
- 17.2k
7
votes
1
answer
880
views
Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s
Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding ...
- 7,514
4
votes
0
answers
355
views
Distribution of min/max row sum of matrix with i.i.d. uniform random variables
Given a $n\times n$ symmetric random matrix such that
all diagonal elements are all fixed as $1$.
all elements in upper triangle (excluding the diagonal) are i.i.d. uniform random variables ...
- 272
2
votes
0
answers
59
views
Min/max row-sum distribution of a symmetric matrix of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s
Given a $n\times n$ symmetric random matrix such that
all diagonal elements are all fixed as $0$.
randomly select $k$ distinct cells in the upper triangle (excluding the diagonal), and then ...
- 272
1
vote
1
answer
155
views
Is the Krawtchouk ensemble a determinantal process?
The Krawtchouk ensemble is defined by a weight: $w(x) = \binom{K}{x}p^x q^{K-x} $ and in fact it comes from a conditioned random walk on $\mathbb{Z}^N$. It is a probability measure on the set $\{ 0, ...
- 7,514
1
vote
1
answer
357
views
Does CLT hold for joint distribution of two dependent binomial variables?
Let $S_n$ and $T_m$ be two binomial variables satisfying $S_n\sim B(n,\frac12)$ and $T_m\sim B(m,\frac12)$. Define $\tilde{S}_n=\frac{2S_n-n}{\sqrt{n}}$ and define $\tilde{T}_m$ similarly. For any ...
CommunityBot
- 1
8
votes
1
answer
198
views
Tail bound of a distribution
Let $X_1, X_2, \ldots, X_n, Y_1, Y_2, \ldots, Y_n$ be independent binary random variables each being $1$ with probability $\frac{1}{k}$.
Let $Z = X_1(Y_1 + \cdots + Y_k) + X_2(Y_2 + \cdots + Y_{k+1})...
CommunityBot
- 1
14
votes
1
answer
2k
views
Combinatorial proof for the number of lattice paths that return to the axis only at times that are a multiple of 4
Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of $...
- 2,896
5
votes
0
answers
352
views
0-1 matrix combinatorial problem
Let $M \in \{0,1\}^{n \times n}$ and let $r_i$ be its $i$-th row. Given constant $p \in (0,1/2]$, let the number of $1$s in each row be at least $p\,n$. Given constant $c \in (0,1)$, what is the ...
- 1,677
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{...
- 1,228
2
votes
1
answer
266
views
A question about finite free convolution
For any square matrix $Y$ let $\chi_x(Y) = det(xI -Y)$ denote its characteristic polynomial.
Say $A$ and $B$ are two $n-$dimensional symmetric matrices with constant row sums $a$ and $b$. Lets ...
- 128k
3
votes
2
answers
1k
views
Proof of identity involving Stirling numbers of the second kind
While computing conditional expectations of certain functionals of a Poisson white noise field (details are long and probably irrelevant), I've stumbled upon the need to use the following identity ...
- 85.6k
6
votes
0
answers
105
views
Long loops in critical random graphs
A simple calculation seems to show that the expected number $X_k$ of loops of length $k$ in a critical Erdös-Renyi random graph $G(n,n^{-1})$ is approximately given by
$$ \mathbb{E} X_k=\frac1{2k}{e^...
- 2,175
26
votes
3
answers
2k
views
A game of plates and olives
This question has its origin in Morse theory (see this paper) but it can be given an entirely elementary and amusing formulation.
The game of plates and olives starts with an empty table and ...
- 155
2
votes
1
answer
112
views
Uniform bound for rare events
Consider a family $F$ of subsets of a probability space $\Omega$. Assume that $F$ has bounded VC dimension and that the measure of each subset in $F$ is at least $\epsilon$.
Drawing $n$ iid points ...
CommunityBot
- 1
18
votes
1
answer
2k
views
How big is the sum of smallest multinomial coefficients?
Given positive integers $n$ and $d$, let $S$ indicate the list of all $d$-tuples of non-negative integers $(c_1,\ldots,c_d)$ such that $c_1+\cdots+c_d=n$. Let $v_i$ be the value of the multinomial ...
- 1,228
3
votes
2
answers
228
views
Percolation on finite irregular trees
Consider a rooted tree of height $h$, such that all the leaves are at last layer. We perform the following random process: each edge is deleted with probability $0.5$, and otherwise it is retained. We ...
- 3,587
3
votes
0
answers
89
views
Two game-set inequalities
Here are a couple of curious related results about a generalized 2-player 1-set tennis game: the winner of the set is the first player to win $n$ games, and the winner of each game is the first player ...
- 1,190
9
votes
3
answers
749
views
Random RSK and Plancherel Measure
Let $(X_1,X_2,\ldots)$ be a sequence of i.i.d. random variables. It is known that if these random variables are distributed uniformly on the unit interval, then applying the RSK algorithm to this ...
- 1,228
6
votes
1
answer
370
views
Mean minimum distance for M and N uniformly random points on reals between 0 and 1
Similar to Mean minimum distance for N random points on a one-dimensional line, but instead of only N random points, choose N and M random points and find the mean minimum distance between points of N ...
- 5,590
4
votes
1
answer
669
views
Number of independent sets of a random tree
Let $T_n$ be a random tree on $n$ labelled vertices chosen equiprobably among all $n^{n - 2}$ trees, and $I(T)$ be the number of distinct independent sets of a tree $T$. I'm interested in the average ...
- 37.7k
21
votes
2
answers
548
views
Do these polynomials have alternating coefficients?
In answering another MathOverflow question, I stumbled across the sequence of polynomials $Q_n(p)$ defined by the recurrence
$$Q_n(p) = 1-\sum_{k=2}^{n-1} \binom{n-2}{k-2}(1-p)^{k(n-k)}Q_k(p).$$
Thus:
...
- 18.4k
21
votes
0
answers
2k
views
The Fourier Transform of taking Eigenvalues
The purpose of this question is to ask about the Fourier transform of the map which associate to an $n$ by $n$ matrix its $n$ eigenvalues, or some function of the $n$ eigenvalues. The main motivation ...
- 52.3k
4
votes
0
answers
150
views
Dividing a finite arithmetic progression into two sets of same sum: always the same asymptotics?
This is inspired by the recent question How many solutions $\pm1\pm2\pm3…\pm n=0$.
The oeis entries A063865 linked to this question and A292476/A156700 for the related one "How many solutions $\pm1\...
- 13.4k
6
votes
1
answer
216
views
How close $k$-sums of a random set of numbers are on average?
Consider a set of random iid variables $x_1, \ldots x_n$ uniformly distributed on $[0, 1]$. For each $S \subset [n]$ with $1 \leq |S| = k < n$ take $\sigma_S = \sum_{i \in S}x_i$. Obviously $\...
- 128k
2
votes
0
answers
91
views
Semigroups of nondecreasing functions
Consider some partially ordered set $(E,\leq)$. Assume either that it is countable with the discrete topology, or that it has some topology compatible with the order, preferably one that makes it into ...
0
votes
1
answer
99
views
expected number of populated blocks
Let $p$ be a positive integer. For each positive integer $N$, let: $$F: \{1, \ldots , pN\} \rightarrow \{1, \ldots, N\} $$
$$ F(n) = \lceil n/p \rceil$$
Let $r \in [0,1]$. I'm curious about the limit ...
- 23.2k
18
votes
1
answer
656
views
Does erosion mix faster than a riffle shuffle?
It is a famous result of Aldous and Diaconis1 that
seven shuffles are necessary and suffice to approximately
randomize 52 cards.2
Here the shuffles are the standard riffle shuffle, where the ...
- 4,713
8
votes
3
answers
675
views
What are the odds of a tie in a random election with k candidates?
Consider an election with $N$ voters and $k$ candidates, where each voter votes randomly for one of the candidates. What are the odds of a tie?
Here "tie" means that multiple candidates get the ...
- 947
5
votes
1
answer
241
views
Height growth for randomly falling Tetris like blocks ? What if Young diagrams are falling down?
Question: How the maximal height grows for random Tetris like blocks falling down ? Numeric simulation (see below)
shows leading term is linear with some constant
depending on shapes of blocks ...
- 17k
3
votes
0
answers
115
views
Approximating the *conditional* probability of 1D discrete random walk not having revisited the origin given last position
I'm looking for a good closed form approximation to the following conditional probability, with provable approximation guarantees.
Consider a 1D random walk on the integers, starting at the origin, ...
- 101
2
votes
0
answers
59
views
Totally distance non-preserving transformations
JL lemma (https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)
guarantees if you have a set of $K$ points in $\Bbb R^N$ a random transformation guarantees that the set can be projected ...
- 13.9k
13
votes
4
answers
535
views
Alignment of random points
Whenever I draw randomly about ten points, I see that there will be always 3 points that are "almost" collinear. This observation leads me to considering the following questions:
Question 1: Suppose $...
- 44.4k
8
votes
1
answer
461
views
Probability of good colorings in randomly-colored graphs
Each vertex in a graph is randomly and independently colored either red or blue with equal probability.
A coloring is called $r$-good, for some fraction $r\in[0,1]$, if at least a fraction $r$ of the ...
- 3,549
17
votes
1
answer
910
views
Randomly switching street lights, in a square city
This is a combinatorics-probability question, best stated however in "recreational" terms. Imagine a $N\times N$ city, meaning that we have $N$ horizontal streets, and $N$ vertical streets. At each ...
- 151k
46
votes
7
answers
10k
views
Conway's game of life for random initial position
What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...
- 13.6k
15
votes
2
answers
547
views
Random graphs in $\mathbb R^2$ (or random rays from $\mathbb Z^2$)
The model:
Suppose that for each lattice point in $\mathbb Z^2$ we pick a random direction uniformly and independently. At time $t=0$ we start drawing rays starting from each lattice point in the ...
- 13.6k
3
votes
1
answer
150
views
Convex lower bound for probability that a random subset of [n] has cardinality at most k
For $n\in\mathbb{N}$, the probability that a random subset of $[n]=\{1,\cdots n\}$ has cardinality at most $k$ is $f_k(n)=2^{-n}\sum\limits_{i=0}^k{n\choose i}$. I'm looking for a lower bound $g_k(x)\...
- 30.1k
4
votes
0
answers
188
views
Distributions over permutation groups $\mathcal{S}_n$
Partly inspired by recent developments in enumeration of pattern avoiding permutations, which is known to be connected with Brownian excursions [Hoffman&Rizzolo]. The exciting milestone is the ...
- 8,071
5
votes
0
answers
273
views
root system generalizations of Sekiguchi-Debiard (aka Laplace-Beltrami) operators
For the root system $A_n$, taking the limit $q = t^\alpha$ and $t \to 1$, and letting $Y = (t-1) X -1$ one obtains from the Macdonald operator the so-called Sekiguchi-Debiard operator:
$$D_\alpha(X) =...
- 13.4k
26
votes
4
answers
2k
views
$\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$ is a convex function on $[0,+\infty)$?
Let $f(x)=\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$, where $u\in\mathbb{Z}^+$ and $\binom{x}{l}=\frac{x(x-1)\dots(x-l+1)}{l!}$ for all $l\in\mathbb{Z}^+$.
Then can we prove $f(x)$ is a convex ...
- 3,255
2
votes
0
answers
93
views
Erdös-Renyi Model with prescribed subgraph
In the Erdös-Rényi model for random graphs there is a lot of results stating sharp phase transitions for the probability of a random graph to contain a fixed prescribed ...
- 2,630
10
votes
5
answers
2k
views
fixed points of permutation groups
As is well-known (see, for example, a nice exposition by our own Qiaochu: https://qchu.wordpress.com/2012/11/07/fixed-points-of-random-permutations/) that the distribution of the number of fixed ...
- 9,720
8
votes
0
answers
240
views
Stepanov phase transition in random graph
Consider the classical random graph model G(n,p), with p=c/n, as proposed by Erd\"os and R\'enyi.
At this scaling, the most prominent feature is arguably the abrupt change of the topology that the ...
- 468
6
votes
1
answer
985
views
A variant of bin-and-ball problem
We have $n$ balls, each belonging to a group (e.g, color). There are $g$ groups ($g$ may be large but $g=o(n)$). We sequentially put the balls into $m$ bins in the following way: for each ball, we ...
CommunityBot
- 1
10
votes
2
answers
387
views
Distribution of the area statistic for Catalan paths
A Catalan path of semilength $n$ is a path from $(0,0)$ to $(2n,0)$ that proceeds by taking northeast (1,1) or southeast (1,-1) steps, and never goes below the $x$-axis. The area of a path $P$ is the ...
- 3,587
14
votes
3
answers
9k
views
Solving a Rubik's cube via a series of randomly selected (quarter-turn) Singmaster moves
In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a $3\times3\times3$ Rubik's cube, starting in an arbitrary configuration, can ...
- 308
4
votes
1
answer
421
views
Order statistic of Markov chain sample path and related probabilities
Consider a one dimensional sample path, denoted as $\{X(1), ..., X(t), ..., X(n)\}$, generated from a discrete time finite state (time homogeneous) Markov chain over states $\{1,...,m\}$, with ...
- 8,071
4
votes
3
answers
504
views
Expected number of crossings of the diagonal of a lattice path?
If we uniformly choose a lattice path from $(0,0)$ to $(n, n)$ (i.e. at each step we can move from $(x,y)$ to $(x+1,y)$ or $(x,y+1)$), what is the expected number of times that the path crosses the ...
- 43.2k