All Questions
Tagged with pr.probability co.combinatorics
802 questions
27
votes
3
answers
2k
views
Expected edit distance
The edit or Levenshtein distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example $$\operatorname{...
user32786
7
votes
0
answers
280
views
Expected minimum Hamming distance with overlaps
Let's say we sample two random binary vectors, one called $A$ of length $n$ and the second called $B$ of infinite length. Now we compute $X_k= \min_{i\in[k]} w(A \oplus B[i,i+n-1])$ where $w$ computes ...
user32786
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
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
4
votes
0
answers
1k
views
Matula-Goebel ordering of rooted trees intrinsic?
I was somewhat recently introduced to the Matula-Goebel bijection between rooted trees and natural numbers. (nicely illustrated here http://keithbriggs.info/matula.html) Looking through them, I ...
- 475
5
votes
1
answer
421
views
Memory of Uniformly Random Dyck Paths
Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have $S(0)...
- 4,952
4
votes
1
answer
275
views
Nontrivial lower bounds on Cheeger inequalities for Markov chains
For a reversible Markov chain $X_{t}$ on $\mathbb{R}^{n}$ with transition kernel $K$ and stationary distribution $\pi$, it is well-known that the `spectral gap' (basically, the size of $K$ when ...
- 51
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
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
6
votes
2
answers
2k
views
Is the Binomial Expectation of Convex Function Convex in p?
Suppose $X$ has a binomial distribution with success probability $p$ and $n$ trials and let $h(\cdot)$ be a positive convex real-valued function.
Is the function $g(p)=\mathbb{E}[h(X)\ |\ p]$ convex ...
- 103
0
votes
0
answers
102
views
Efficient algorithm for computing the mixed moments of sums of random variables
Let $X_1,\dots,X_m$ be dependent random variables. We are interested in efficient algorithms for computing the following quantity:
$$E\Big[\Big(\sum_{i=1}^m X_i\Big)^k\Big],$$
where $k\in\mathbb{N}$ ...
- 1
0
votes
1
answer
89
views
Maximal directed crossing of a box using uniform random variables
Take a 1 by 1 box $D \subset \mathbb{R}^2$ and let $U_1,\dots,U_n$ be i.i.d. uniforms in $D$.
Suppose at the start all of $\mathcal{V}_0=\{U_1,\dots,U_n\}$ are viable. At each step pick one of the ...
- 491
1
vote
2
answers
276
views
What is the probability for sequence of lenght L in subset of [n]
I am trying to calculate the probability that i'll have L length sequence in a random subset of [n] when the subset size is k. for example, if n=5, k=4 and L=2 I'll have the below subsets: {2,3,4,5}, {...
- 11
2
votes
2
answers
1k
views
expected number of cycles in a "random" bipartite directed graph
Consider a "random" bipartite directed graph where (1) on each side, the set of vertices has cardinality n and (2) for each vertex i, we add one (and only one) directed edge i->j at random (drawn ...
- 65
1
vote
0
answers
243
views
Factorization of permutations.
Let $n,k$ be positive integers such that $3n=2k$ and $N = \lfloor \alpha n\rfloor$ for some constant $0<\alpha<1$. Let $S_{3n}$ denote the permutation group of order $3n$. Consider the following ...
- 141
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
2
votes
1
answer
134
views
Completion time of a process on a tree
Given is a constant degree rooted tree of depth $D$. It is also known that the total number of nodes in the tree is at most $D^2$. There is a probabilistic process with discrete time steps on the ...
- 501
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
3
votes
1
answer
443
views
What is the expected value for this
If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...
- 31
2
votes
2
answers
710
views
Runs in coin flips
Let $P(j,k,n)$ be the probability of getting $j$ uniform runs of length $k$ from $n$ fair coin flips. What's the best way to compute $P$? I have no idea how difficult it might be; if it's a very ...
- 1,769
3
votes
0
answers
173
views
Are numbers $h_{r,s} = \sum_{k} P(r;s;k) \frac{1}{n^{2k}} \bigg(1-\frac{1}{n}\bigg)^{n-2k}$ irrational?
I asked this question on MSE and Mike Spivey gave an insightful answer. I decided to put it here nevertheless in case someone else gets interested. If this violates rules on MO, please let me know, I'...
- 151
8
votes
1
answer
452
views
What is the probability that a random subset of a finite group is generic?
Definition 1: Given a group $G$, a subset $X \subseteq G$, and a natural number $k$,
we say that $X$ is (left) $k$-generic in $G$ if there are $k$ many left translates of $X$ that cover $G$.
That is, ...
- 83
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 ...
- 24.7k
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
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
2
votes
1
answer
835
views
An optimization problem, non complete bipartite graph and hungarian algorithm
I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...
- 123
4
votes
2
answers
399
views
Generic words of given weight
Suppose you have an alphabet with countably many letters. Every letter has a particular weight (for instance, as in the game of Scrabble). There are a total of $n^2$ letters that have weight $n$.
...
- 1,329
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
1
vote
1
answer
258
views
Probability distribution for the size of an ordered set of (randomly pruned) integer pairs with intersection constraints on successive elements in the permutation
Update: To write a quick preamble, this question is basically asking that, if you take all possible pairs of some set of characters, call these pairs elements of the set $S$, and if you throw out some ...
- 11
5
votes
1
answer
980
views
"Nice" eigenvectors for (square of) adjacency matrix of a bipartite graph?
Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix.
I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be ...
- 53
3
votes
0
answers
251
views
Permutations & Balanced Distribution
I would like to implement a form of consistent hashing using a set of permutations.
The rules are as follows:
I have Y=~32 buckets and X items. Buckets may be "alive" or "dead". Items are to be ...
- 31
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
0
votes
1
answer
123
views
Enumeration of quadrangulations with a boundary and simple faces.
I wish to enumerate all quadrangulations of a $2p$ gon with $n$ internal vertices. Quadrangles are required to have simple faces. Simple face means all four vertices of each quadrangle are distinct.
...
- 141
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
6
votes
1
answer
658
views
Calculating a specific joint probability involving sums of binomial distributions
The following might look like a simple problem - but the question has been unanswered for more than a week on math.stackexchange.com, and I have asked quite a few of the Ph.d. students at our ...
- 161
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
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
2
votes
2
answers
304
views
Uniformly random planar map
Is there a way to sample a planar map uniformly at random? I am aware of the Cori-Vauquelin-Schaeffer bijection that can be used to sample and study uniformly random quadrangulations. There are other ...
- 1,989
60
votes
4
answers
3k
views
Flipping coins on a budget
A coin is flipped $n$ times and you win if it comes up heads at least $k$ times. The coin is unusual in that you're allowed to pick the probability $p_i$ that it comes up heads on the $i$th flip, ...
- 82.7k
0
votes
1
answer
182
views
How to Rigorize an inequalities argument
Context
I'm working on a problem involving Lovasz Local Lemma, for proving that there exists a graph with a certain property.
What I need to prove:
There exists some constant $c$, and functions $p,...
- 3
2
votes
1
answer
635
views
Azuma's Inequality when the conditions hold with high probability?
In Azuma's Inequality, is the statement true when $|X_k - X_{k-1}| < c_k$ almost surely rather than with probability 1? If not, is there another result which gives strong concentration when the ...
- 201
2
votes
1
answer
2k
views
The expected minimum Hamming distance within a set of randomly selected binary strings
If I randomly sample with replacement $P$ times from a set of all possible binary strings of length $L$, what is a good lowerbound on the expected minimum Hamming distance between any two of my $P$ ...
- 67
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
7
votes
4
answers
1k
views
Recent impressive combinatorial developments in probability theory
In the preface to the second edition of Daniel Stroock's book "Probability Theory: An Analytic View", there is this striking claim (on p. xv)
... I suspect that, for at least a decade, the most ...
- 1,302
3
votes
1
answer
376
views
The degrees in a random subgraph
Fix some positive integers $N$ and $d_k$, $k=1,2,\dots$ with $N=\sum_{k=1}^\infty d_k$.
Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ ...
2
votes
1
answer
267
views
Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice
Imagine I have an $N$ by $M$ rectangular lattice where I randomly assign one of $k$ colors to every vertex in the lattice. I then write down a list of the ${N*M}\choose{2}$ possible unordered pairs ...
- 23
4
votes
0
answers
114
views
Bounds on the size of a set of strings over an arbitrary alphabet within a fixed Hamming distance of one-another
I pick a set of random strings $S$ of length $L$ over an $P$-letter alphabet. These strings are 'random' in the sense that every character is chosen with uniform random probability over the ...
- 41
3
votes
1
answer
253
views
Bounds for duplicate finding with limited independence
(This is a follow up to this previous question on math.stackexchange.com.)
Assume a process that samples uniformly at random from the range $[1,\ldots,n]$. I am interested in the time to find a ...
- 33
4
votes
1
answer
587
views
Combinatorial descriptions of the stationary distribution of a Markov chain
When I say "Markov chain" I think of a directed positively weighted (finite) graph, such that the sum of all edges going out of a vertex equals 1. Also I assume that it is aperiodic and irreducible.
...
- 406
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