All Questions
Tagged with pr.probability co.combinatorics
802 questions
106
votes
5
answers
10k
views
integral of a "sin-omial" coefficients=binomial
I find the following averaged-integral amusing and intriguing, to say the least. Is there any proof?
For any pair of integers $n\geq k\geq0$, we have
$$\frac1{\pi}\int_0^{\pi}\frac{\sin^n(x)}{\...
- 43.2k
98
votes
17
answers
123k
views
Google question: In a country in which people only want boys [closed]
Hi all!
Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is:
...
- 1,107
75
votes
11
answers
28k
views
Does War have infinite expected length?
My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers.
The ...
- 236k
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
57
votes
4
answers
15k
views
Connectivity of the Erdős–Rényi random graph
It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
- 7,857
51
votes
3
answers
4k
views
What is the sandpile torsor?
Let G be a finite undirected connected graph. A divisor on G is an element of the free abelian group Div(G) on the vertices of G (or an integer-valued function on the vertices.) Summing over all ...
- 19.2k
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 ...
- 24.7k
41
votes
4
answers
2k
views
What is the probability two random maps on n symbols commute?
It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
- 38.6k
39
votes
2
answers
2k
views
Random sequence of integers in $\{1, 2, \dots, n \}$ which is "everywhere probably increasing" - how long can it be?
Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$.
Fix $r \...
- 1,927
39
votes
9
answers
3k
views
The shortest path in first passage percolation
Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)
Consider a square planar grid. (The vertices are pair of ...
- 24.7k
36
votes
3
answers
4k
views
the following inequality is true，but I can't prove it
The inequality is
\begin{equation*}
\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)
\end{equation*}
for all integer $d\geq 1$. I use computer to verify ...
- 363
36
votes
2
answers
13k
views
Mean minimum distance for N random points on a one-dimensional line
Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. I was wondering if there was a simple/straightforward method (not involving long ...
- 811
33
votes
7
answers
2k
views
List of proofs where existence through probabilistic method has not been constructivised
The probabilistic method as first pioneered by Erdős (although others have used this before) shows the existence of a certain object. What are some of the most important objects for which we can show ...
33
votes
1
answer
1k
views
Why does McMahon formula look like the inclusion-exclusion principle?
The McMahon formula for the number of tilings of an $a \times b \times c$ hexagon by lozenges:
$$ \Big[H(a)H(b)H(c)\Big] \Big[H(a+b)H(b+c)H(c+a)\Big]^{-1} \Big[H(a+b+c)\Big]$$
looks oddly like the ...
- 22.8k
31
votes
4
answers
2k
views
Probability of zero in a random matrix
Let $M(n,k)$ be the set of $n\times n$ matrices of nonnegative integers such that every row and every column sums to $k$. Let $P(n,k)$ be the fraction of such matrices which have no zero entries, ...
- 37.7k
30
votes
1
answer
942
views
partition of infinite word onto permitted words
Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, $0<c&...
- 109k
29
votes
6
answers
2k
views
Combinatorial Morse functions and random permutations
This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function ...
- 34.7k
28
votes
6
answers
2k
views
Random Alternating Permutations
An alternating permutation of {1, ..., n} is one were π(1) > π(2) < π(3) > π(4) < ... For example: (24153) is an alternating permutation of length 5.
If $E_n$ is the number of alternating ...
- 22.8k
27
votes
5
answers
7k
views
Probability of a Random Walk crossing a straight line
Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the ...
- 733
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
27
votes
2
answers
812
views
What is the right notion of self-dual (two-dimensional) percolation in R^4?
For a lattice in $\mathbb{R}^2$, if we include each edge independently with probability $p$ (i.e. bond percolation), it is well known that there is a critical probability $0 < p_c < 1$ depending ...
- 7,857
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 ...
- 271
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 ...
- 34.7k
25
votes
3
answers
2k
views
Some models for random graphs that I am curious about
G(n,p)
We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...
- 24.7k
24
votes
3
answers
4k
views
What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?
Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay ...
- 4,922
24
votes
1
answer
2k
views
A puzzle about finding three points $(x,y)$, $(x,z)$ and $(y,z)$ in a subset of a square.
I was asked (by myself) to give a proof of the following seemingly simple geometric statement, but after thinking a little I now suspect it could be less elementary than I thought (or am I being silly?...
- 60.5k
24
votes
1
answer
615
views
Permutations, stopping times, Bessel functions, hook formula and Robinson-Schensted
For given counting number $n$, consider all permutations $\pi$ of {$1,\ldots,n$}, generate for every $\pi$ its Robinson-Schensted pair of standard tableaux $(P_\pi,Q_\pi)$ and average together all the ...
- 17.6k
23
votes
3
answers
2k
views
Zeroes of the random Fibonacci sequence
Let $X_n$ be the "random Fibonacci sequence," defined as follows:
$X_0 = 0, X_1 = 1$;
$X_n = \pm X_{n-1} \pm X_{n-2}$, where the signs are chosen by independent 50/50 coinflips.
It is known ...
- 19.2k
23
votes
4
answers
979
views
What nodes of a graph should be vaccinated first?
Consider a graph, choose some "p: 0<p<1" (probability to infect the neighbor node).
Choose some random number "K" of nodes which are "infected" initially.
So we ...
- 24.9k
23
votes
2
answers
910
views
Random permutations of Z_n
In "The maximum number of Hamiltonian paths in tournaments" by Noga Alon, the author states the following without proof (equation 3.1):
"Consider a random permutation $\pi$ of $\mathbb{...
- 375
22
votes
2
answers
1k
views
Laws of Iterated Logarithm for Random Matrices and Random Permutation
The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then
$$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, $...
- 24.7k
21
votes
11
answers
4k
views
What are some good examples of non-monotone graph properties?
It seems that many, if not almost all, of the properties studied in graph theory are monotone. (Property means it is invariant under permutation of vertices, and monotone means that the property is ...
- 7,857
21
votes
7
answers
14k
views
A balls-and-colours problem
A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the ...
- 1,269
21
votes
1
answer
32k
views
How to compute KL-divergence when PMF contains 0s?
From the Wikipedia page on Kullback-Leibler divergence, the way to compute this metric is to utilize the following formula:
The way I understand this is to compute the PMFs of two given sample sets ...
- 439
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:
...
- 44.4k
21
votes
2
answers
1k
views
Generating random finite groups
I would like a method to efficiently generate a random finite group of a given order $n$.
If there are $g(n)$ non-isomorphic groups of order $n$,
ideally each group would occur with probability $1/g(n)...
- 151k
21
votes
3
answers
2k
views
what is the cycle length of the maximum normalized cycle in the directed complete graph?
Consider the complete, directed graph on $n$ vertices. Let the edge lengths $\{X_{ij}: 1 \leq i, j \leq n\}$ be i.i.d standard normal, with the constraint $X_{ij} = -X_{ji}$. The value of a normalized ...
- 1,010
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
20
votes
2
answers
3k
views
Boys and Girls Revisited
Consider a country with $n$ families, each of which continues having children until they have a boy and then stop. In the end, there are $G$ girls and $B=n$ boys.
Douglas Zare's highly upvoted answer ...
- 23k
20
votes
3
answers
1k
views
The Angel and Devil problem with a random angel
In the classic version of Conway's Angel and the Devil problem, an angel starts off at the origin of a 2-D lattice and is able to move up to distance $r$ to another lattice point. The devil is able ...
- 6,969
20
votes
3
answers
1k
views
The probability for a sequence to have small partial sums
The question
Let $a_1,a_2,\dots,a_n$ be a sequence whose entries are +1 or -1. Let t be a parameter. My question is to give an estimate for the number of such sequences so that
$|a_1+a_2+\dots ...
- 24.7k
20
votes
4
answers
870
views
Enumeration and random selection
In Peter J. Cameron's book "Permutation Groups" I found the following quote
It is a slogan of modern enumeration theory that the ability to count a set is closely related to the ability to pick a ...
- 85.6k
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 ...
- 976
19
votes
9
answers
3k
views
How can I generate random permutations of [n] with k cycles, where k is much larger than log n?
I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from Sn are both ...
- 14k
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
19
votes
3
answers
2k
views
Current state of the Komlos conjecture on vector balancing
Komlos Conjecture: the exists an absolute constant $K>0$ such that for all $d$ and any collection of vectors $v_1,\ldots, v_n\in \mathbb{R}^d$ with $\left\lVert v_i\right\rVert _2=1$ we can find ...
- 2,288
19
votes
5
answers
18k
views
Time-inhomogeneous Markov chains
I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
- 191
19
votes
1
answer
1k
views
Horst Knörrer's Permutation Cancellation Problem
The Problem:
The following question of Horst Knörrer is a sort of toy problem coming from mathematical physics.
Let $x_1, x_2, \dots, x_n$ and $y_1,y_2,\dots, y_n$ be two sets of real numbers.
We ...
- 24.7k
18
votes
3
answers
8k
views
Number of invertible {0,1} real matrices?
This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.
My question is: how many such matrices ...
- 32.1k
18
votes
4
answers
1k
views
Pennies on a carpet problem
I recently read the following "open problem" titled "Pennies on a carpet" in "An Introduction To Probability and Random Processes" by Baclawski and Rota (page viii of book, page 10 of following pdf),...
- 4,952