All Questions
Tagged with pr.probability co.combinatorics
802 questions
2
votes
0
answers
138
views
Update on Viskov's paper on random processes, Lagrange inversion, and the Heisenberg–Weyl algebra
"A Random Walk with a Skip-Free Component and the Lagrange Inversion Formula" by Viskov presents connections among Lagrange inversion and measures of random Lévy processes. The freely ...
- 12.9k
2
votes
1
answer
165
views
Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?
A uniformly random $r$-regular bipartite graph on $n$ vertices is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular ...
- 9,501
3
votes
0
answers
516
views
The distribution of collision stopping time in 2D random walk
Assume two particles A at $(0, 0)$ and B at $(a, b)$ in 2D discrete grid, both of them have the same possibility of $\frac{1}{4}$ for moving up/down/left/right (i.e. 2D random walk). We define the ...
- 117
1
vote
0
answers
663
views
The distribution of hitting time in 2D-lattice random walk [closed]
Assume a particle at $(0,0)$ with the same possibility of $1/4$ for moving up/down/left/right (i.e. random walk in 2D lattice). We define the stopping time 𝑇𝑐 as it hits $(a,b)$. How can we get the ...
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 ...
- 4,713
4
votes
1
answer
322
views
Approximating binomial coefficient sum
I have the following exact sum for the expectation of an event
$$\sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \binom{(n-j)k}{m} / \binom{nk}{m}$$
which is exactly correct but I want to give an ...
- 109k
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 ...
- 47.3k
4
votes
1
answer
262
views
What is the number of finite Dynkin systems?
(This is a spin-off of Determine the minimal elements of a Dynkin system generated by a finite set of finite sets)
Let $\Omega$ be a finite set. A Dynkin system on $\Omega$ is a subset of the power ...
- 7,226
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 ...
1
vote
1
answer
105
views
What is the distribution of a Cartesian power of a collection of iid uniform points? (renewed)
The following question was asked recently at https://mathoverflow.net/questions/326631/what-is-the-distribution-of-a-cartesian-power-of-a-collection-of-iid-uniform-poi :
Take a rectangle with ...
CommunityBot
- 1
4
votes
3
answers
324
views
Probability that $k$ random subsets of a fixed size covers a set
Let $A=\{1,\ldots,n\}$. Now, we uniformly randomly select $k$ subsets, $A_i$ of size $d$ from $A$. What is the probability that $\bigcup_i A_i=A$? This seems to be natural variant of the set cover ...
- 63.9k
3
votes
3
answers
942
views
implementations of domino shuffling algorithm
Are there many implementations of the "domino shuffling" algorithm as found in William Jockusch, James Propp amd Peter Shor's Random Domino Tilings and the Arctic Circle Theorem math.CO/...
- 35.5k
3
votes
1
answer
271
views
A quantity associated to a probability measure space
Let $(S,P)$ be a (finite) probability space. We associate to $(S,P)$ a quantity $n(S,P)$ as follows:
The probability of two randomly chosen events $A,B\subset S$ being independent is denoted by $n(S,P)...
- 356
4
votes
0
answers
182
views
Determine the minimal elements of a Dynkin system generated by a finite set of finite sets
(This is a refined version of https://cs.stackexchange.com/q/144371)
Let $\Omega$ be a finite set. A Dynkin system on $\Omega$ is a subset of the power set of $\Omega$ containing $\Omega$, which is ...
- 5,822
2
votes
1
answer
158
views
"Shape"/"norm" of a uniformly random set partition
Let $\mathcal{A}=\{A_1, A_2, \ldots, A_m\}$ be a uniformly random set partition of $[n]$.
What can we say about $||\mathcal{A}||_2 = \sqrt{\sum_{i=1}^m |A_i|^2}$? It is clearly upper bounded by $n$, ...
1
vote
1
answer
125
views
Empirical degree distribution of random $n$ vertices labeled rooted tree converges to Poisson distribution
I am reading Louigi's lecture note on random trees and graphs here. I get stuck on part (b), Exercise 1.2.3 on page 19, which says the following:
Let $T_n$ be uniformly drawn from $\mathcal{T}_n$, ...
- 715
5
votes
2
answers
707
views
Distribution of some sums modulo p
Fix a finite set of integers $S$ and a prime number $p$. Let $(a_1, a_2, \dotsc, a_n)$, $(b_1, b_2, b_3, \dotsc, b_n)$ be two sequences of integers where the numbers $a_i$ and $b_i$ are chosen ...
- 114k
8
votes
1
answer
380
views
Question about estimating random symmetric sums modulo p
Let $n > 0$ be a positive integer (large) and $p > 2$ a fixed prime number. What is the probability that $$\sum_{ 1 \leq i < j \leq n} a_ia_j = 0 \mod p$$ where $a_1, a_2, \dots a_n$ are ...
- 1,101
2
votes
1
answer
199
views
Do enough permutations of an initial set probably cover most permutations?
Fix $\alpha, \epsilon \in(0,1)$. Take $(S_n)_n$ to be any sequence of sets with each $S_n$ containing $ \lceil (n!)^\alpha\rceil$ permutations of $n$ elements. Also build another sequence of sets $(...
3
votes
1
answer
118
views
Using singularity analysis for probability at a threshold?
In some urn model with parameter $p$, the generating function
$$
f_p(z) \;=\; \frac{1+p\,z}{1-(1-p)\,z\,(1+p\,z)}
$$
is such that $[z^n]f_p(z)$ is the probability that an $n$-urn configuration has a ...
- 1,043
3
votes
1
answer
241
views
Probability that k randomly drawn permutations can be arranged to compose to the identity
Consider the symmetric group $S_n$ under the uniform distribution. For integer $k > 1$, suppose we draw $k$ elements $s_1, \dots, s_k$ independently at random. What is the probability that there ...
- 1,907
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 ...
- 13k
0
votes
1
answer
217
views
On independence of multiples of $\mathbb Z_p$
This is a rewording in combinatorial language of a question posed on another forum. The original was posed as a probabilistic problem.
Problem set up:
Consider for a fixed prime $p$, the ...
- 4,991
3
votes
1
answer
161
views
Probability permutation in turned to cycle
Let $M$ be a $0/1$ square matrix having one $1$ per row and column (permutation matrix).
If you permute the columns and rows independently what is the probability resulting permutation matrix is a ...
- 128k
1
vote
0
answers
47
views
Probability that a modified $c$-bounded lattice walk is also $c$-bounded
Let $\mathcal{B}_n^{(c)}$ be the set of $n$ step lattice bridges (starts at $(0,0)$ ends at $(n,0)$), taking steps $\{(1,1), (-1,1)\}$ bounded between $y = c$ and $y = -c$ for a constant $c \geq 0$. ...
- 111
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 ...
1
vote
1
answer
119
views
Does exponential degree distribution entail Log-normal distance distribution in large complex graphs?
We've been exploring the graph structure of a large genealogical data base (WikiTree) of which main connected component contains about 23 million nodes. The graph edges are defined by any direct ...
- 184
4
votes
1
answer
264
views
Information for discovering an item-colour assignment in a combinatorial game
We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all ...
CommunityBot
- 1
1
vote
0
answers
176
views
Gaussian order statistics
Setup. Let $\alpha\in(0,1)$ fixed; and $\tau\in[0,1]$ (think of it very close to one).
Suppose $X_1,\dots,X_n$ are i.i.d. standard normal.
Let $Y_1,\dots,Y_n$ be another sequence of standard normals ...
- 63.9k
5
votes
1
answer
325
views
Bounding the max-loaded bin using${m \choose k} \|A\|_k^k$
Throw $m$ balls into $n$ bins independently, each ball selecting a bin from the distribution $A \in \Delta_n$. This question is about lower-bounding the max-loaded bin.
Background. In this MO answer I ...
- 3,255
4
votes
0
answers
187
views
Dyadic distribution of $0/1$ permanents
Fix reals $a,b\in(1,2)$ satisfying $1<b<a<ab<2$.
What fraction of $0/1$ matrices of dimensions $n\times n$ have permanents
in $[b2^m,a2^m]$ at some $m\in\{0,1,2,\dots,\lfloor\log_2n!\...
- 13.9k
2
votes
1
answer
843
views
Interpretation of probability statements in Nina Zubrilina's paper
I asked this question on Math.stackexchange but got no answer.
In the paper Zubrilina - Asymptotic behavior of the edge metric dimension of the random graph (MR, the main result is
$$\operatorname{...
CommunityBot
- 1
1
vote
1
answer
173
views
Could you provide some TSP examples from real world to test a new algorithm?
It's well known that to find a hamilton cycle is NPC, while TSP is NPH.
But it seems that for majority of graphs (density of edge > 0.1, order > 100) there is a fast algorithm to find different ...
- 5,429
1
vote
1
answer
207
views
Expectation of the sum of the squares of the cardinal of an inverse function
I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as:
$$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$
where $\oplus$ is the bitwise XOR.
...
- 128k
3
votes
1
answer
128
views
A ratio of two probabilities
I am concerned about the monotonicity of the following ratio
$
f(\eta)=\frac{\sum_{x=K}^{N}\left(\begin{array}{c}
N\\
x
\end{array}\right)\left(q_{G}\eta\right)^{x}\left(1-q_{G}\eta\right)^{N-x}}{\...
- 128k
1
vote
1
answer
141
views
Expectation of maximum of all period lengths of functions $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$
This is based on an older question.
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)$ and ''starting value'' $...
- 10.4k
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
...
- 24.2k
5
votes
3
answers
601
views
Convergence speed of a random dyadic rational generator
We are given a multiset $M$ of real numbers which initially is equal to $\{0,1\}$. In a sequential fashion, at each round $r\in\mathbb{N}$
two distinct instances $x_r$ and $y_r$ of $M$'s numbers are ...
- 3,979
1
vote
1
answer
106
views
Almost-parallel corners of the hypercube in high dimensions
Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...
- 30.1k
6
votes
0
answers
156
views
Distribution of iid hypergeometric random variables conditioned on the sum
Let $X_1,X_2,\ldots,X_n$ be iid random variables with hypergeometric distribution. To be specific,
$$ \mathrm{Prob}(X_1=i) = \frac{\binom{N}{i}\binom{M-N}{m-i}}{\binom{M}{m}}.$$
Let $S=X_1+\cdots+X_n$....
- 37.7k
3
votes
1
answer
206
views
Random planes separating points in $\mathbb{R}^3$
We are given a unit origin-centered sphere $S$ in $\mathbb{R}^3$, and three points $\mathbf{x},\mathbf{y},\mathbf{z}\in S$. Let $\mathbf{h}$ be a point selected uniformly at random from $S$ and let $H$...
- 128k
1
vote
0
answers
127
views
Delocalization of eigenvectors of graph Laplacians
Let $(V,E)$ be an undirected, connected graph with $n$ nodes. The graph Laplacian is defined as $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_1 < \...
- 41
3
votes
1
answer
153
views
Randomized version of Turán's theorem II
$\newcommand{\om}{\omega}$Let $\om(G)$ denote the number of vertices in a largest clique of an (undirected) graph $G$ with the set $[n]:=\{1,\dots,n\}$ of vertices. Then
\begin{equation}
\om(G)\ge\...
- 1,042
5
votes
1
answer
209
views
Randomized version of Turán's theorem
Turán's theorem says the following.
Take any natural $n$ and $r$. Suppose that
\begin{equation*}
|G|>\Big(1-\frac1r\Big)\frac{n^2}2, \tag{0}
\end{equation*}
where $|G|$ is the number of edges of ...
- 1,042
0
votes
0
answers
133
views
is there an example in planar graph that using probabilistic methods
The probabilistic method is a technique for proving the
existence of an object with certain properties by showing that
a random object chosen from an appropriate probability
distribution has the ...
- 4,713
8
votes
2
answers
475
views
Random permutations without double rises (avoiding consecutive pattern $\underline{123}$)
A permutation avoiding a consecutive pattern $\underline{123}$ is permutation
$\pi = \pi_1 \pi_2 \ldots \pi_n$ with the property that there does not exists $i \in [1, n-2]$
such that $\pi_i < \pi_{...
- 46
2
votes
1
answer
426
views
Random subgraph properties
Consider a graph $G$ of $N$ vertices and $M$ edges, and assume $G$ has typical complex network properties: it is not necessarily connected, but it has a high clustering coefficient and a giant ...
CommunityBot
- 1
2
votes
1
answer
151
views
Given an input point in $\mathbb{R}^n$, select (one of) the closest point(s) from a fixed large set of points given in advance
We are given a set $S$ of $m\gg 1$ points in $\mathbb{R}^n$.
In the problem I am trying to solve, in a sequential fashion, we obtain a new point $p_r\not\in S$ at each round $r\ge 1$ and the goal is ...
- 151k
6
votes
0
answers
321
views
extensions of the Nekrasov-Okounkov formula
This post is related to the issues addressed in
A q,t-extension of Plancherel Measure thru Yang-Mills Theory ?
however the generalization/interpolation which John Mangual asks for looks different ...
- 2,137
3
votes
1
answer
315
views
Distribution of the first occurrence of a maximum (record) run of zeros in the digits of a normal number (say $\pi$)
If the question was stated to appeal to the general public, it would be something like this. For a number such as $\pi$ or $\sqrt{2}$, the digits in base $b$ appear to be randomly distributed. We are ...
- 3,098