All Questions
Tagged with co.combinatorics pr.probability
802 questions
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
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
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$...
- 1,677
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\...
- 128k
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 ...
- 128k
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 ...
- 1,851
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 ...
- 1,677
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_{...
- 345
3
votes
1
answer
206
views
Fast sampling of matroids
In his classic paper, Donald E. Knuth described how random matroids of fixed rank can be generated.
What is the currently the fastest (in terms of mixing behaviour) known way to sample matroids of ...
- 268
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
2
votes
1
answer
118
views
Calculate the discrete probability of x number of good outcomes occurring before y number of bad outcomes
I have a grid of 16 tiles face down. Half are good outcomes and half are bad outcomes. How would I calculate the probability of picking x number of Good outcomes before y number of bad outcomes are ...
- 23
1
vote
0
answers
85
views
Winning criterion for a combinatorial game
Given $n$,
let $\mathcal{R}$ be a set of pairs $(\rho,A)$
where $A\subseteq n, \rho\in 2^A$.
Consider the following game between A and B.
At each round $t$, A enumerates an $m\in n$ (that has not been ...
- 909
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 $(...
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
23
votes
4
answers
978
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
5
votes
0
answers
130
views
Random process on a sequence of rolls of an $n$-sided die
Let $\ X:=X_{k\,n}\ $ be a random variable of a $n$-sided die where $\Pr(X=i)=\frac{1}{n}$ for each $i\in\{1,2,\ldots,n\},\ $ where $\ k\in\{1, 2, \ldots,n\}\ $ and $\ n\ $ are fixed. Let $t$ be a ...
- 83
1
vote
2
answers
163
views
Coupling a binomial - parity conditioning
If I have a binomial $X \sim B(n,p)$, and another binomial $X' \sim B(n,p)$ conditioned on $X'$ being of even parity. Is it true that there always exists a coupling for $(X,X')$ with $|X-X'| \le 1$? (...
- 435
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 ...
- 129
2
votes
0
answers
164
views
Finding an optimal strategy for a combinatorial sequential game
We are given a set $\{p_1, p_2, \ldots, p_n\}$ of players and a set of $\{\ell_1, \ell_2, \ldots, \ell_n\}$ of locations, where $n\in\mathbb{N}$. Each location can be either free or occupied, and each ...
- 83
1
vote
3
answers
339
views
Coupon collector targeting a collection among many
I am interested in the following problem:
We are given a universe $U$ of $n$ coupons, partitioned into $k$ collections, $C_1,\dots C_k$.
At each time step $t$, a coupon $X_t$ is selected uniformly at ...
- 111
12
votes
1
answer
525
views
An inequality about unit vector orthogonal to $(1,1,...,1)$
Does there exist a constant $\alpha>0$ such that the following holds?
$$\liminf_{n\to\infty}\inf_{x\in\mathbb{R}^n, \sum_{i=1}^nx_i^2=1, \sum_{i=1}^nx_i=0}\frac{\sum_{i<j, |i-j|\leq\frac{n}{4}}(...
- 1,495
2
votes
1
answer
404
views
Euclidean distance bound with geometric constraints
Let $S_n$ be a set of $n$ points belonging to $\mathcal{B}_d:=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{x}\|_2\le 1\}$, where $d\ll \log(n)$.
Let $s_n$ and $\ell_n$ be respectively defined as follows:
$$...
- 1,677
1
vote
1
answer
338
views
Polynomial form/Fourier transform of rational function over finite affine space
I am certainly going to make a mess of any serious algebraic terminology, so bear with me as I present my problem arising from a probability problem.
Consider the space of sequences of $n$ zero-one ...
- 526
5
votes
0
answers
287
views
Infinite tridiagonal matrices and a special class of totally positive sequences
Let $\Bbb{y} = \big(y_1, y_2, y_3, \dots \big)$ be an infinite sequence of positive real numbers such that following $\Bbb{N} \times \Bbb{N}$ tridiagonal matrix
\begin{equation}
T(\Bbb{y}) := \,
\...
- 2,137
2
votes
2
answers
379
views
Probabilistic combinatorial optimization problem on the distances between pairs of points in $[0,1]$
Let $S$ be a set of $n \gg 1$ points lying on the interval $[0,1]$. Given a point $p\in[0,1]$, let $S_p\subseteq S\times S$ be the set formed by all pairs of points $(x,y)$ with $x,y\in S$, such that ...
- 1,677
0
votes
1
answer
340
views
Expectation of the ratio of two discrete random variables with combinatorial constraints
We are given a set $S=\{1, 2, \ldots, n\}$ where $n\gg 1$, and for all indices $1\le i \le n$, $i$ is associated with a real value $\alpha_i\!\cdot\! v_i$, where $\alpha_i\in[0,1]$ and $v_i\in(0,1]$.
...
- 1,677
8
votes
0
answers
181
views
Self-avoiding walks on strips
A strip is a locally finite graph which admits a quasi-transitive (i.e. finitley many orbits on vertices) action of $\mathbb Z$. A self avoiding walk is a walk which visits no vertex more than once.
...
- 2,671
2
votes
2
answers
279
views
Combinatorial optimization problem with interdependent constraints on points in $[0,1]$
We are given a set $S$ of $n$ real numbers in $[0,1]$, with $0,1\in S$, and a value $\alpha\in(0,1/2)$. For each ordered triplet $(i,j,k)$ of values contained in $S$ (with $i\le j \le k$), we define ...
- 1,677
0
votes
1
answer
201
views
What is the most likely sequence? [closed]
I have a jar containing n numbered marbles, where 1...x marbles are red and marbles x+1...n ...
- 117
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
3
votes
2
answers
488
views
Question about a new pseudo-random number generator
While investigating non-periodic RNG's (random number generators) for irrational numbers, I came up with a version that actually produces pseudo-random words consisting of $N$ bits, where $N$ is ...
- 3,098
2
votes
0
answers
65
views
Are stable matchings (noise-)stable?
Suppose a group of computer scientists have entrusted their dating lives to a computer. Specifically, there are $n$ men and $n$ women, all of whom are cis-het. Being educated people, they of course ...
- 526
2
votes
0
answers
90
views
Motivation for proof of local lemma/construction version
I am interested in finding intuition to the bounds and proof of the asymmetric local lemma.
I think the $k$-SAT is fairly intuitive, but I would like to understand the general version.
One good ...
- 515
9
votes
0
answers
467
views
Measuring the randomness of texts
The question concerns statistic properties of random words in a finite alphabet $A$.
By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$.
...
- 41.8k
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
3
votes
1
answer
395
views
Symmetric distribution optimization problem of distances between points in $[0,1]$
Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $x, y, z$ the outcomes of three i.i.d. random variables $X, Y, Z$ with distribution $\mathcal{D}$, sorted in increasing order, ...
- 1,677
2
votes
1
answer
218
views
Probability distribution optimization problem of distances between points in $[0,1]$
Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $X, Y, Z$ three i.i.d. random variables with distribution $\mathcal{D}$, and $T$ a random variable uniformly distributed in $[...
- 1,677
1
vote
0
answers
177
views
Probability of satisfying the congruent mod equation
I'm wondering about the probability of picking three different numbers $x,y,z$ out of the set $[50]=\left\{ 1,2,3,...,50\right\}$ satisfying the equation: $$xyz\equiv \gcd(x,y,z)\mod 7$$ I started out ...
- 139
1
vote
1
answer
264
views
Probability a near universal hash function $ax \bmod p \bmod m$ produces an output from inputs equal modulo $m$
For one of the near universal hash functions $f(x) = ax \bmod p \bmod m$ where $p$ is prime and $m < p, m>1$ and $x$ ranges over $1 \dots p-1$ , what is the probability that given $x_r \in \{ x |...
- 23
0
votes
1
answer
305
views
Number of duplicate pairs in multiple samplings
My universe has M different items. I run m=10 independent samplings over M. In each sampling, n elements are picked without replacement (n<<M). What is the expected number of pair duplicates we ...
- 67
3
votes
1
answer
145
views
The size of monochromatic submatrix
We say a matrix $(a_{ij})$ is 0-1 matrix if $a_{ij}\in \{0,1\}$ for all $i,j$. We say a matrix $(a_{ij})$ is monochromatic if for some $a$, $a_{ij} = a$ for all $i,j$.
Question: Let $c\geq 1/2$ be a ...
- 909
3
votes
3
answers
2k
views
Probability of a given string being a substring of another string
I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$ over $...
- 41
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
2
votes
0
answers
165
views
Ask for some reference about isoperimetric constant on Voronoi diagrams?
Given a Poisson point process $\mathcal{P}$ in $\mathbb{R}^2$, the $\textbf{Voronoi cells}$ of a point $p\in \mathcal{P}$ is defined by
$$V(x):=\{y\in \mathbb{R}^2: \|x-y\|=\min_{x'\in \mathcal{P}}\|x'...
- 288
2
votes
3
answers
290
views
Geometric probabilistic problem on triangles on a plane
We are given a triangle $T$ on a plane $P$, with sidelengths $a$, $b$ and $c$, where $c \ge b \ge a > 0$. A straight line $L$ on $P$ is selected uniformly at random from the set of all the ...
- 1,677
0
votes
1
answer
57
views
Expected size of binomial coefficient with Poisson arrivals?
I have a Poisson process where new elements arrive to a set with Poisson intensity $\lambda$. Initially, there are $N_0$ elements in the set. The probability that there are $N_0 + M$ elements in the ...
- 371
1
vote
1
answer
158
views
Bound for multinomial expansion involving Poisson random variables
Let $x_i, i=1, \ldots n$ be Poisson random variables with parameters $\lambda_i$ correspondingly with condition that $\sum_{i=1}^nx_i=T$. Due to linearity of the expectation one can write:
$$
E\left(\...
- 343
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{...
- 41