All Questions
Tagged with pr.probability co.combinatorics
802 questions
7
votes
2
answers
3k
views
Maximum distance between two consecutive points of N random points on a unit length line
I have encountered a seemingly simple question on distances of random points.
Place N points randomly and uniformly on the line segment [0..1].
How to derive the expectation (or the distribution) of ...
- 79
7
votes
1
answer
342
views
Upper Bound for the Difference of Even Probability and Odd Probability in Hypergeometric Distribution
Let $X$ be a random variable following the hypergeometric distribution with parameters $N,K,n$, where
\begin{equation}
Pr(X=k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}.
\end{equation}
To ...
- 183
7
votes
2
answers
186
views
Do successive maximum permutations pick latin squares uniformly?
Suppose we start with a $n\times n$ matrix with entries sampled independently and uniformly at random from $[0,1]$. The weight of a set of entries will simply be the sum of those entries. A ...
- 85.6k
7
votes
3
answers
896
views
A balls and urns model for a hashing problem
Fix $N \in \mathbb{N}$. Suppose we throw $N$ numbered balls into $N$ numbered urns, so that for each $b \in \{1,\ldots,N\}$, ball $b$ lands in urn $j$ with equal probability $1/N$. Choose a number $c \...
- 11.2k
7
votes
1
answer
463
views
Boundedness of total current in electrical network
Consider the following symmetric matrix (adjacency matrix):
$$A=(a_{ij})_{1\leq i,j\leq n}$$
such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{...
- 1,495
7
votes
1
answer
191
views
Is there a Degenerate Dependency Local Lemma?
The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded.
Here I ask whether another possible generalization (for which I could not yet ...
- 19k
7
votes
2
answers
417
views
Dynamics of a random "quadratic" directed graph
Let G be a directed graph on N vertices chosen at random, conditional on the requirement that the out-degree of each vertex is 1 and the in-degree of each vertex is either 0 or 2. The "periodic" ...
- 19.2k
7
votes
1
answer
186
views
$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary
Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...
- 1,677
7
votes
2
answers
3k
views
The largest Wasserstein distance to uniform distribution among all probability distributions with uniform marginals
I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals.
More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$...
- 422
7
votes
1
answer
222
views
Algorithm to generate random commuting permutations
I am seeking to understand the properties of a typical pair of permutations $(\sigma,\tau) \in \mathrm{Sym}(n)^2$ chosen uniformly at random from all pairs such that $\sigma$ and $\tau$ commute. In ...
- 1,769
7
votes
1
answer
441
views
Recursive sequence of binomial random variables
Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and
$$X_{k+1} = X_k + \text{Bin}(X_k,p).$$
Thus, $\mathbf E [ X_k ] = (1+p)^k$.
I would like a left tail bound. Perhaps, ...
- 191
7
votes
1
answer
156
views
Nearest neighbors on random complete graph
Consider the complete graph on $2n$ vertices, where the ${2n \choose 2}$ edges have distinct lengths in uniform random
order. So each vertex $v$ has a nearest neighbor $N(v)$, across the shortest ...
- 236
7
votes
1
answer
257
views
Collecting proofs of the birth of the giant component
I want to collect different proofs of Erdös-Rényi result on the double jump of the largest connected component on $G(n,p)$ (or in $G(n,M)$.
I know the original proof of Erdös-Rényi, the proof that ...
- 1,561
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 ...
- 272
7
votes
1
answer
309
views
The time to drift a binary string from one state to another via deterministic selection of two possible random bit mutation procedures
I have some length $L$ binary string consisting of an ordered array of bits: $(b_1, b_2, ..., b_{L})$, where all bit values $b_i$ are originally set to zero. I'd like a particular set of $n$ bits to ...
- 123
7
votes
1
answer
390
views
Combinatorial/probabilistic statements having $F_{\text{un}}$/$F_q$ geometric interpetation
$\newcommand{\Fun}{F_\text{un}}$There was lots of "Fun with $\Fun$" (field with one element) in recent years.
One of the points is that it provides bridge between geometrical and ...
- 24.9k
7
votes
1
answer
876
views
What is the six positive real number for a dice producing a highest chance?
Say there is a dice with six faces, each face has a positive real number different from others. There is a chessman on the origin of the number axis. In each trial, the dice rolls infinite times. ...
- 143
7
votes
0
answers
464
views
Mistakes in Logan and Shepp's famous paper on Young Tableaux?
In their landmark paper from 1977 named "A Variational Problem for Random Young Tableaux" Logan and Shepp obtained a number of results concerning asymptotic properties of Young Diagrams ...
- 116
7
votes
0
answers
162
views
Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets
We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
- 1,677
7
votes
0
answers
297
views
Is there a practically useful or concrete representation theory/Fourier analysis on finite groupoids?
Fourier analysis on finite groups is well known to be useful for probability theory and combinatorics — consider for example the Fourier analysis on $(\mathbb Z/2\mathbb Z)^n$ which can be used to get ...
- 526
7
votes
0
answers
579
views
Guises of the noncrossing partitions (NCPs)
From "Noncrossing partitions in surprising locations" by Jon McCammond:
Certain mathematical structures make a habit of reoccuring in the most diverse list of settings. Some obvious ...
- 10.5k
7
votes
0
answers
122
views
Discrepancy of the finite approximation of the Lebesgue measure
Let $\mu$ be a probabilistic measure on the unit square $Q$ which is the average of $N$ delta-measures in some points in this square; let $\lambda$ denote the Lebesgue measure on $Q$. What is the rate ...
- 109k
7
votes
0
answers
171
views
What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?
Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...
- 1,462
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
6
votes
3
answers
855
views
Series involving power of the index
How to prove the following identity
$$ \sum_{n=1}^{\infty} \frac{n^{n-1} e^{-n}}{n!} = 1$$
analytically (which can be confirmed with $Mathematica$)? The standard trick for geometrical series does not ...
- 77
6
votes
4
answers
1k
views
Number of integer combinations $x_1 < \cdots < x_n$?
I asked this question earlier on math.stackexchange.com but didn't get an answer:
Let $0 < a_1 < \cdots < a_n$ be integers. Is there a closed formula (or some other result) for the number $N(...
- 16.2k
6
votes
4
answers
452
views
Counting card distributions when cards are duplicated
If we have a deck of $48$ different cards and $4$ players each get $12$ cards, it is well known how to calculate the number of possible distributions: $\frac{48!}{12!12!12!12!}$
In a german card came (...
6
votes
2
answers
723
views
Threshold function for a graph not being planar
A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.
It is well-known that every ...
- 557
6
votes
2
answers
274
views
Expectation of period length of functions $f:\{1,\ldots,n\}\to \{1,\ldots,n\}$
For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ associate a sequence $\text{seq}(f))$ defined recursively by
...
- 48.9k
6
votes
2
answers
2k
views
How to understand the combinatorial Laplacian $\Delta$ which is defined on the graph?
I have a question about the combinatorial Laplacian $\Delta$ which is defined by
$$\Delta(u,v)=c(u)1_{u=v}-c(u,v)$$
where $u, v$ are some vertices in the graph $G=(V, E)$, and $c(u,v)$ is a ...
- 288
6
votes
2
answers
2k
views
Distribution of $\max_{n \ge 0} S_n$, random walk
Say we have a random walk that is a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
- 61
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
6
votes
2
answers
729
views
Has the following kind of (minimum degree $d$) random graph been studied?
The following random construction is simple enough that I am guessing it must have been studied. Fix $d \ge 3$, and let $n > d$. For each of the $n$ vertices, pick exactly $d$ other vertices to ...
- 7,857
6
votes
3
answers
563
views
Large deviations for discrete uniform distribution
(Not sure if this belongs on stack-exchange or overflow; let me know if I should switch it).
Given a sum of $n$ IID random variables $\{X_i\}_{i=1}^n$, each uniform on the integers $0,1,...,r$ for ...
- 435
6
votes
1
answer
349
views
Ramsey type theorem
Let $\mathcal{P}(\{0,\dotsc,7\})$ denote the power set of $\{0,\dotsc,7\}$.
Is the following true?
For any function $f: \mathcal{P}(\{0,\dotsc,7\})\rightarrow\{0,1\}$ there exists $0\leq k\leq 3$ ...
- 909
6
votes
1
answer
235
views
A combinatorics problem and the probability interpretation
For a gaussian vector variable $w\sim N(0,I_{n\times n})$, the moments of square norm are $\mathbb{E} \|w\|^{2 r} = \prod_{t=0}^{r-1} (n + 2 t)$.
Based on Isserlis' theorem, $\mathbb{E} \|w\|^{2 r}$ ...
- 75
6
votes
3
answers
814
views
A simple stopping time problem.
This should be rather standard so I hope somebody with a good background in probability theory would give me a quick solution or a reference.
We are given a threshold positive integer $T>0$. Let $...
- 195
6
votes
2
answers
1k
views
diameter of a graph with random edge weights
Given a weighted directed graph $G=(V,E, w)$, suppose we generate a new graph $G'=(V,E,w')$ with the same vertices and edges, but now letting the weight of edge $(i,j)$ be
an exponential random ...
- 976
6
votes
1
answer
361
views
Random walks on infinite directed regular graphs
Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps).
Assume that $\Gamma$ is bi-regular, that is ...
- 26k
6
votes
2
answers
266
views
Lovasz local lemma for the edge model
In order to successfully apply the Lovasz local lemma, one needs the events to be relatively independent. This (sometimes) works well in the $G(n,p)$ model of random graphs, where the presence or ...
- 2,339
6
votes
1
answer
225
views
Restricted independent set of the cycle graph $C_{3n}$
Let $V$ be the vertices of the cycle graph $C_{3n}$. Suppose there is a partition of $V$ into sets of $3$, i.e. $V=\cup_{k=1}^{n}{V_k}$ where $|V_k|=3$ for $k$ in $1..n$.
QUESTION: Is it possible ...
- 9,501
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 (...
- 4,829
6
votes
1
answer
3k
views
Mathematical expectation of minimum of k random variables with fixed sum n
We have $n$ independent identically distributed random variables $X_1$, $X_2$, ..., $X_N$, $X_i=j$ with probability $1/k$ for $j=1, 2, ... k$. Let $Y_j$ be a number of random variables $X_i$, which ...
- 251
6
votes
1
answer
837
views
Average minimum number of random k-sparse vectors in GF(2) to span the whole space?
What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? ...
- 307
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 ...
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 $\...
- 5,590
6
votes
1
answer
356
views
Probabilistic problem on random spanning trees
Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....
- 1,677
6
votes
2
answers
283
views
Nonlinear boolean functions
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements. I wonder if there is any known algorithm/construction that, given any $n\geq 1$, returns a boolean function $f:\mathbb{F}^n_2\rightarrow \...
- 333
6
votes
2
answers
615
views
Optimally directing switches for a random walk
If you are sometimes called upon directing a random walk in a directed graph, how should you direct it so as to maximize the probability it goes where you want?
Formal statement
More specifically, ...
- 4,994
6
votes
1
answer
424
views
Probability of intersecting a rectangle with random straight lines
We are given a rectangle $R$ with sides lengths $r_1$ and $r_2$, contained in a square $S$, with sides lengths $s_1=s_2\ge r_1$ and $s_2=s_1\ge r_2$. $R$ and $S$ are axis-aligned in a cartesian plane $...
- 1,677