All Questions
Tagged with pr.probability co.combinatorics
802 questions
18
votes
4
answers
3k
views
Markov chain on groups
Let $G$ be a permutation group on the finite set $\Omega$. Consider the Markov chain where you start with an element $\alpha \in \Omega$ chosen from some arbitrary starting probability distribution. ...
- 85.6k
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 ...
- 7,857
18
votes
2
answers
1k
views
Random Walk on $\mathbb{R}$ with Uniformly Distributed Steps and "Reflective" Boundary at Origin
A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, ...
- 313
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 ...
- 151k
18
votes
1
answer
890
views
Two conjectures about zero inner products and dissociated sets
The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
- 3,377
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 ...
- 2,252
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$ ...
- 128k
17
votes
1
answer
622
views
Longest of random worm-like paths in $\mathbb{Z}^2$
Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \bmod 3$,
we place, with equal probability, one of these six patterns:
The result ...
- 151k
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 ...
- 1,363
17
votes
1
answer
732
views
Reference request: a conjecture of Rota on positive functions of a random variable
Rota and Shen's On the Combinatorics of Cumulants ends with a conjecture which I'll restate as follows:
Let $p \in \mathbb{R}[x_1, x_2, ...]$ be a polynomial such that, for any sequence $X_1, X_2, ...
- 118k
17
votes
3
answers
923
views
Random permutations from Brownian motion
Let $B(t)$ be a Brownian motion. The ordering of $(0, B(1), ..., B(n-1)) $ is a random permutation in $S_n$. This is not uniform for $n>2$ since the probabilities of the identity permutation $[123.....
- 28k
16
votes
3
answers
2k
views
Integration of a function over 7-sphere
Suppose we have $x_1^2 + y_1^2 + x_2^2 + y_2^2 + x_3^2 + y_3^2 + x_4^2 + y_4^2 = 1$ and we define $z_j = x_j + iy_j$, where $j = 1,\,2,\,3,\,4$.
The problem is finding or approximating the ...
- 163
16
votes
6
answers
3k
views
analog of principle of inclusion-exclusion
When I teach elementary probability to my finite math students, a common error is to mix up the concepts of disjointness and independence. At some point I thought that it might be helpful to some ...
- 2,150
16
votes
3
answers
918
views
What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$
Every $f\colon\{-1,1\}^n\to \mathbb{R}$ can be repsenented as a multilinean polynomial of the form $$f(x_1,x_2,\ldots ,x_n)=\sum _{S\subseteq [n]} \hat{f}(S)\prod_{i\in S} x_i $$ The degree of the ...
- 311
16
votes
4
answers
597
views
The lattice spanned by $m$ random 0-1 vectors of length $n$
Consider $m$ random 0-1 vectors of length $n$. Let $L$ be the lattice spanned by them. What is the value of $m$ (as a function of $n$) for which it is true with positive probability that $L=Z^n$? More ...
- 24.7k
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 ...
- 24.7k
15
votes
1
answer
1k
views
In how many steps a random walk visits all the elements of a finite group, with a probability 1/2?
This question is a variation of the return to the origin problem.
Let $G$ be the finite group $\mathbb{Z}/n \times \mathbb{Z}/n$ and let the random transformation $T: G \to G$ such that $T(a,b) = (...
15
votes
1
answer
1k
views
Math journal publishing work related to combinatorics, probability, counting problems etc.?
I'm a high school student. My peer and I have done some work on the Ballot Theorem counting problem and Catalan Numbers. We have come up with a new proof to the Ballot Theorem and we demonstrate the ...
15
votes
1
answer
1k
views
Generating Random Young Tableaux: A peculiar probability identity
In the paper by Greene, Nijenhuis and Wilf, an algorithm is proposed for generating uniformly random Young tableaux of shape $\lambda$. The algorithm is to uniformly randomly pick a starting cell, and ...
- 4,952
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 ...
- 85.6k
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 ...
- 4,922
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{...
14
votes
3
answers
8k
views
Analog of Chebyshev's inequality for higher moments
I have a positive random variable $X$ with $E[X] = 1$ and a small number $k$ more moments bounded by constants:
$$E[(X-1)^i] = O(1) \forall i \in \{2, ..., k\}.$$
I'd like to bound the average of $n$...
- 241
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 ...
- 539
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 ...
- 173
14
votes
3
answers
694
views
Probability to be the winner in a tournament
In a project in Game Theory we (Ayala Arad and Ariel Rubinstein) are stuck with the following "simple" question. We are sure of the conjecture but we failed to find a (hopefully simple) proof:
Let $...
- 141
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 $...
- 3,283
14
votes
1
answer
956
views
Partitioning the vertices of an n-cube with random hyperplane cuts
An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry.
It is an old chestnut of a ...
- 19.2k
14
votes
0
answers
1k
views
The threshold for a perfect matching in a random subgraph of a regular bipartite graph?
The following question seems very natural.
It is a well known consequence of Hall's Theorem that every regular bipartite graph has a perfect matching. Another classical result states that the ...
- 1,643
14
votes
0
answers
629
views
Probability of many overlapping zero inner products on a circle
[Question edited and changed a little on June 14 2015]
Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...
- 3,377
13
votes
7
answers
2k
views
Finite-space dynamical systems
This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ ...
- 14.4k
13
votes
4
answers
4k
views
The probability for a streak when tossing a coin
I'm trying to solve the following problem:
Let's say I'm tossing a coin $N$ times. The coin is not fair, such that the probability for heads is $p_0$ and for tails is $1-p_0$.
What is the ...
13
votes
2
answers
669
views
An inequality for expected value of normally distributed variables
Question. Let $X_1,\dots,X_n$ be random variables with normal distribution. Is it true that
$$\mathbb E \prod_{i=1}^nX_i^{2k}\ge\prod_{i=1}^n\mathbb E X_i^{2k}$$for any $k\in\mathbb N$?
(The ...
- 4,535
13
votes
2
answers
383
views
Comparing two measures on trees on $n$ vertices
A standard measure on trees on $n$ vertices is the Uniform Spanning Tree (UST) on the complete graph. This is the measure where every tree has equal probability, $1 / n^{n-2}$ by Cayley's formula.
...
- 7,857
13
votes
2
answers
3k
views
The probabilistic method - reference to less challenging questions
I am teaching a course in combinatorics and large part of it is dedicated to the probabilistic method especially in the case of graphs. The course is an undergraduate level (almost none of the ...
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 $...
- 131
13
votes
3
answers
1k
views
A property of unimodal sequences
It is well-known that $(-1)^j \sum_{i=0}^j (-1)^i\binom{n}{i} \geq 0$. This inequality can be used to prove Bonferroni's inequalities for example. Recently I noticed that a similar inequality applies ...
- 619
13
votes
1
answer
2k
views
Counting subtrees of a random tree ("random Catalan numbers")
Given a rooted tree $T$ and an integer $k \geq 1$, let $N_k(T)$ be the number
of subtrees of $T$ containing the root and having exactly $k$ nodes (take $N_k(T)=0$ if $T$ has less than $k$ nodes).
...
- 4,922
13
votes
1
answer
564
views
Coincidences between average Catalan tableaux
There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices:
$$
P_n \, := \, \frac{1}{C_n} \, \...
- 17k
13
votes
2
answers
518
views
Asymptotics of a randomized Fibonacci sequence
Let $f(1)=f(2)=1$ and recursively define $f(n+1) = f(n) + f(i)$, where $i$ is chosen uniformly at random from $1,\ldots,n-1$. About how big should we expect $f(n)$ to be for $n$ large? We can examine ...
13
votes
1
answer
869
views
Lotteries, Turan's problem, and minimization of risk
Suppose I am a high-volume broker aiming to make some money on a state lottery. In this lottery, six balls are drawn from a population of (let's say) 50, without replacement. A ticket is a choice of ...
- 19.2k
13
votes
0
answers
412
views
Transitivity of balanced mass transport in Z
Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...
- 19.7k
12
votes
3
answers
1k
views
A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?
In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...
- 470
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}$?
- 922
12
votes
3
answers
911
views
Expected number of compositions needed to get constant function
This is somewhat inspired by Factoring a function from a finite set to itself.
Fix natural number $n$ and let $[n] := \{1,2,\ldots,n\}$. Set $g_0 \colon [n]\to [n]$ to be the identity, and for $i \geq ...
- 24.2k
12
votes
3
answers
1k
views
How to sample a uniform random polyomino?
A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, ...
- 7,857
12
votes
1
answer
525
views
An inequality about unit vector orthogonal to $(1,1,...,1)$
Does there exist a constant $\alpha>0$ such that the following holds?
$$\liminf_{n\to\infty}\inf_{x\in\mathbb{R}^n, \sum_{i=1}^nx_i^2=1, \sum_{i=1}^nx_i=0}\frac{\sum_{i<j, |i-j|\leq\frac{n}{4}}(...
- 1,495
12
votes
2
answers
406
views
Does asymmetric fraction of finite groups tend to $0$?
Let’s define asymmetric fraction of a finite group $G$ as the number $$\mathrm{af}(G) = \frac{|\{(g, a) \in G \times \mathrm{Aut}(G)\mid a(g) = g\}|}{|G|\cdot|\mathrm{Aut}(G)|}.$$ Equivalently it can ...
- 2,618
12
votes
1
answer
883
views
The dance marathon problem
In his book, "The Strange Logic of Random Graphs", Joel Spencer describes the "Dance Marathon" problem:
Imagine $n$ couples at a Dance Marathon. Each dance each couple remains ...
- 3,979
12
votes
3
answers
1k
views
Is there a simple inductive procedure for generating labeled trees uniformly at random, without direct recourse to Prüfer sequences?
Suppose you have a labeled tree $T$ on vertices $V=\lbrace 1,\ldots,n\rbrace$ that is drawn uniformly at random from the set of all $n^{n-2}$ such trees. I am seeking an $f$ satisfying the following ...
- 1,068