All Questions
Tagged with pr.probability co.combinatorics
802 questions
12
votes
2
answers
947
views
How rare are unholey permutations?
For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...
- 20.2k
12
votes
1
answer
1k
views
Entropy of edit distance
The edit or Levenshtein distance between two strings is the minimum number of single character insertions, deletions and substitutions to transform one string into another. If we take random binary ...
user32786
12
votes
1
answer
460
views
No limit shape for random Young diagrams under z-measure?
In their paper Random partitions and the Gamma kernel (Advances in Mathematics 194 (2005) 141–202), Borodin and Olshanski state that:
An important difference between the Plancherel measures and the ...
- 1,038
11
votes
5
answers
2k
views
Coin flipping and a recurrence relation
How can one solve the following recurrence relation?
$f(n) = 1 + \frac{1}{2^n} \sum_{k = 0}^n {{n}\choose{k}} f(k)$
$f(0) = 0$
As it happens, I can show $f(n) = \Theta(\log n)$ through other means (...
- 501
11
votes
4
answers
1k
views
A trick or a general technique? (Probabilistic Method)
Suppose we have some positive quantites $P$ and $Q$ which depend on some choices that we make, and we want to show that some choice makes the quotient $P/Q$ fall below some cool bound.
One idea is to ...
- 9,720
11
votes
2
answers
2k
views
Balls and bins variation
How many balls have to be thrown uniformly at random into $m$ bins, such that with high probability $n_1, n_2, \dots, n_m$ are distinct numbers, where $n_i$ is the number of balls in bin $i$ ?
Is ...
- 711
11
votes
2
answers
1k
views
Heuristic lower bounds on small sums of roots of unity
Let $f(k,n)$ be the smallest non-zero absolute value of a sum of $k$ complex $n$th roots of unity. Asking for bounds in either direction, Tao suggested that a polynomial lower bound seemed plausible ...
- 4,589
11
votes
1
answer
996
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
11
votes
2
answers
714
views
Pursuit-Evasion type game on graph ("Flyswatter game")
An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...
- 113
11
votes
2
answers
880
views
Covering a random graph with spanning trees.
Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is ...
- 4,922
11
votes
3
answers
243
views
How many operad structures are there on the symmetric sequence of simplices / finitely-supported probability measures?
Consider the symmetric sequence $P_n = \Delta^{n-1}$ of probability measures on finite sets, with coordinatewise $\Sigma_n$-action. There is a natural topological operad structure on $P$ given by ...
- 63.9k
11
votes
1
answer
636
views
A simple proof for a theorem of Szekeres and Turán
Szekeres and Turán found in 1937 a formula for the sum of the squares and the sum of the fourth powers of determinants of all $n$ by $n$ matrices with $\pm 1$ entries. (The sum of squares case follows ...
- 24.7k
11
votes
1
answer
1k
views
Integration over the orthogonal group
Let $O(N)$ be the orthogonal group, and $a,b,c\in\mathbb N$. The question is:
$$\int_{O(N)}U_{11}^aU_{22}^bU_{33}^cdU=?$$
This is quite a tricky question:
(1) The first thought would go to ...
- 1,363
11
votes
1
answer
284
views
Asymptotic distribution of $\lambda_1$ under the $z$-measure for partitions
The following question about $z$-measures on Young diagrams came up in some ongoing work with Ofir Gorodetsky. I recall the background and then state our question below in the box.
For parameters $z$ ...
- 2,151
11
votes
1
answer
919
views
Average over Random Permutations
Consider $S_{n}$ the symmetric group and for each $\sigma\in S_{n}$ let $U_{\sigma}$ be its $n\times n$ permutation matrix. Let $A$ be an Hermitian $n\times n$ matrix. I'm interested in computing the ...
- 3,626
11
votes
3
answers
2k
views
Probability of unique elements in each of 'S' multisets sampled with uniform probability
Assume I have some set $P$ with $||P|| = N$ unique elements. I also have $S$ multisets, $(m_1, ..., m_S)$, of cardinality $L$, consisting of elements in $P$ chosen with uniform probability. We call ...
11
votes
1
answer
370
views
Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?
Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
- 6,937
11
votes
1
answer
867
views
Simulate coin tossing by die tossing
On the one hand we toss $n$ times a fair coin, and we sum the outcomes (+1 for heads, -1 for tails). Let $f:\mathbb{N}\to\mathbb{R}$ describe the probability distribution of the outcome.
On the other ...
- 338
11
votes
2
answers
608
views
Covariance of INID order statistics [closed]
In the IID case, it is known that all order statistics are positively correlated.* Thus, we know that $$\text{Cov}(X_{(i)},X_{(j)}) \geq 0.$$ Is this known in the INID (independent, non-identically ...
- 111
11
votes
0
answers
282
views
Reference request: a combinatoric result [closed]
When I tried to construct a counterexample in my research, I encountered the following result, which should be true.
Let $m=m(n)$ be a function that grows faster than $\sqrt n$, so $m(n) = \omega(\...
- 211
11
votes
0
answers
426
views
Maximizing the volume in a family of subsets of a cube
Starting from a question in probability, I arrived to the following optimization problem.
Let $I:=[0, 1],$ and let $A$ be a Lebesgue measurable subset of the $n$-dimensional cube, $A\subset I^n.$ ...
- 60.5k
11
votes
1
answer
2k
views
Bounding the entropy of a convolution
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
user17253
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 ...
- 96.4k
10
votes
2
answers
3k
views
Random Unfoldings of the Cube
Motivated by unfoldings of the dodecahedron in How To Fold It --
How many (labeled or unlabeled) unfoldings of the 1 x 1 x n stack of unit cubes are there?
JORourke (4Nov16): John's original image is ...
- 22.8k
10
votes
4
answers
9k
views
Mean minimum distance for N random points on a unit square (plane)
A previously posted question "mean minimum distance for N random points on a one-dimensional line" produced an elegant answer: for a line of length L, the expected minimum distance (between random ...
- 111
10
votes
2
answers
1k
views
Random Voronoi Diagrams
I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm ...
- 903
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
10
votes
3
answers
2k
views
Mean maximum distance for N random points on a unit square
Following up on Mean minimum distance for N random points on a one-dimensional line and Mean minimum distance for N random points on a unit square (plane), I have the following questions.
Given N ...
- 193
10
votes
2
answers
602
views
What is the probability that every pair of students is at some point in the same classroom?
A cohort in a school consists of 75 students who study for 6 years. Each year, the students are randomly distributed into 3 classrooms of 25 students each. What is the probability that, after 6 years, ...
- 226
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 ...
- 455
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 ...
- 1,112
10
votes
2
answers
270
views
Maximal in-degree in directed voting graph
Real-life motivation. Our team has $n$ members. For the next in-team presentation session, everyone had 1 talk prepared that he or she would be able to present. Now everyone could cast $1$ vote about ...
- 48.9k
10
votes
1
answer
462
views
For what range of edge probability does the following property hold for random graphs?
Let $G(n,p)$ denote the Erdős–Rényi model of random graph. For a given function $p = p(n)$ we say that $G \in G(n,p)$ asymptotically almost surely has property $\mathcal{P}$ if
$$\mbox{Pr}[G \mbox{ ...
- 7,857
10
votes
1
answer
263
views
q-versions of the geometric distribution and their names
I'm trying to set straight various $q$-deformations of the standard geometric distribution.
The geometric distribution on $\left\{ 0,1,\ldots \right\}$ is well-known, it has
$$
\mu_1(X=j)=(1-p)p^j,\...
- 1,765
10
votes
1
answer
846
views
A Johnson-Lindenstrauss lemma for finite fields?
Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwise distances between ...
- 7,633
10
votes
0
answers
222
views
Asymptotics of subgraph densities in graphons
In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
- 986
10
votes
0
answers
779
views
Faa di Bruno and Free Probability?
It is possible to glean many combinatorial identities using Faa di Bruno’s formula for the coefficients of higher derivatives of a composite function. For many examples, see David Vella’s paper. The ...
- 7,067
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 ...
- 4,952
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
9
votes
1
answer
860
views
Random walk on a simple finite network
Consider a graph $\Delta_N = \lgroup (x,y)\in\mathbb{Z}^2| x+y\leq N-1, x\geq 0,\ y\geq 0 \rgroup$ (set of edges is defined in a natural way): see here ).
Take a random walker that wonders around ...
- 965
9
votes
1
answer
640
views
Inner product over finite fields
Let $F$ be a finite field,
For every $c \in F$, let $X_1, X_2,..., X_9, Y_1,..., Y_9$ be independent non-zero random variables over $F$.
Denote $X=(X_1,...,X_9)$, $Y=(Y_1,...,Y_9)$, also let $\...
- 93
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
9
votes
1
answer
564
views
combinatorics on cyclic sequences
Given $m\geq 1$, let $I=(a_1,\ldots,a_{3m})$ be a sequence such that $I$ contains exactly $m$ zeros, $m$ ones, and $m$ twos.
Given $i=1,2$ and $j\leq 3m,k\leq m$ we can define $$U_{i,j}(k)=\text{...
- 167
9
votes
1
answer
395
views
computing average height-functions for lozenge tilings
Can anyone suggest a simple and efficient way (preferably embodied in computer code) to compute the average height function for lozenge tilings of an $a,b,c,a,b,c$ semiregular hexagon? I prefer to ...
- 19.7k
9
votes
1
answer
1k
views
A Game of Knights and Queens
Let $m,n,u,v \in \mathbb{N}$ be parameters with $m,n \geq 3$. Suppose two players play a game on a $m \times n$ chess board and we denote the squares of the board by the set of points $ (i,j) $ such ...
- 26.9k
9
votes
1
answer
1k
views
Vertex connectivity of random graphs?
Consider simple, undirected Erdős–Rényi graphs $G(n,p)$, where $n$ is the number of vertices and $p$ is the probability for each pair of vertices to form an edge. Many properties of these graphs are ...
- 383
9
votes
2
answers
878
views
Is there a combinatorial/topological treatment of statistical independence?
Is there any reference which studies sets of random variables as independence systems, a type of combinatorial object (see below)?
Motivation:
In particular, since independence systems are abstract ...
- 2,680
9
votes
2
answers
441
views
From very many sets of fixed measure in a probability space, can we select many that have a positive intersection?
I assume the following Lemma is either well known or, more probably, a
Corollary of a much stronger well known Theorem, and I would be grateful for a
reference:
For all $\delta\in (0,1)$ and all $\...
- 894
9
votes
1
answer
229
views
shape of random q-weighted lattice path
Where can I find a detailed write-up of the asymptotic shape of a $q$-weighted Young diagram inside an $a$-by-$b$ box, especially one that uses a variational approach?
Equivalently, we can look at ...
- 19.7k
9
votes
1
answer
695
views
Probability of return vs. probability of return in minimal number of steps
Consider a random walk on a connected graph $G=(V,E)$. That is, associate to each neighbouring nodes $a,b\in V\ $ transition probabilities $\mathbb{P}(a\rightarrow b), \mathbb{P}(b\rightarrow a) $ ...
- 965