All Questions
Tagged with pr.probability co.combinatorics
802 questions
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 ...
- 674
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}}{\...
- 207
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
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
3
votes
1
answer
181
views
Infimum of weakly dependent Gaussian process?
Consider some collection of weakly dependent Gaussians $\{w_i\}$ with a uniform bound of $r$ on the magnitude of their covariances. Are there any bounds or techniques towards:
$$E[\inf_i|w_i|] \le f(r)...
- 435
3
votes
1
answer
307
views
Concentration of monochromatic edges in a graph
Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of ...
3
votes
1
answer
190
views
Solution for Moment problem
I want to invert a sequence of moments and find a function f(x) satisfying:
$$m_r=\int x^{r}f(x) dx=\int x^{r} dF(x)$$
The sequence of moments is given by:
$m_{2s+1}=0$
$m_{2s}=\sum_{k=1}^{s}\binom{...
- 333
3
votes
1
answer
1k
views
Gradient of probability distribution
Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...
- 153
3
votes
1
answer
647
views
Regarding left-to-right minima
Let $\rho$ be a permutation on $[1,n]$ and $l_i$ be the number of left-to-right minima in $\rho_{i\ldots n}$, I know that for a random permutation $E[l_1] = H_n$ (the $n$-th Harmonic number) but is ...
- 31
3
votes
2
answers
256
views
Picking codewords that are close
I posted this question in https://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back.
Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...
- 13.9k
3
votes
1
answer
333
views
Ratio of expected diameter and height of a conditioned Galton-Watson tree
A Galton-Watson tree is the family tree of a Galton-Watson process. Let $T_n$ denote a Galton-Watson tree conditioned on total population size $n$. The time of extinction is its height $H(T_n)$ and ...
- 43
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
3
votes
1
answer
515
views
A probability question about removing stones from piles
I have run across a question that seems like it should have a well known answer, but I can't find one, so I thought I would ask this hive mind:
Suppose we start with t piles of s rocks each. In a ...
- 205
3
votes
1
answer
242
views
Bounding the success time of a coupon collector like problem
Consider the complete graph on $n$ vertices. Each step, one chooses one of the $\binom{n}{2}$ edges iid uniformly at random. Say a sequence of choice is successful if there is some permutation of the ...
- 4,466
3
votes
1
answer
693
views
Sequence of p draws without replacement with biased probabilities
Hi
I have a problem which i find hard to modelize.
Suppose i have an urn with $N$ marbles. Among these marbles, one is white and all the other ones are black. I draw $P$ marbles without replacement. ...
- 133
3
votes
1
answer
134
views
The pseudo-randomness/jumbledness of $G(n, p)$
In his original paper on pseudo-randomness, Thomason defines a graph to be $(p, \alpha)$-jumbled if, for every set of vertices $U$, $|e(U) - p\binom{|U|}{2}| \leqslant \alpha |U|$. The paper states ...
- 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
3
votes
1
answer
155
views
Expected size of the smallest preimage set
Let $f$ a function from $\{0, 1 \}^{2n}$ to $\{0, 1 \}^{n}$ uniformly picked at random. I would like to have an estimation of the expected size of the smallest premiage set of $f$, more formally $\...
- 215
3
votes
1
answer
206
views
Component properties in Euclidean graphs with distance threshold
In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...
- 649
3
votes
1
answer
150
views
Convex lower bound for probability that a random subset of [n] has cardinality at most k
For $n\in\mathbb{N}$, the probability that a random subset of $[n]=\{1,\cdots n\}$ has cardinality at most $k$ is $f_k(n)=2^{-n}\sum\limits_{i=0}^k{n\choose i}$. I'm looking for a lower bound $g_k(x)\...
- 31
3
votes
1
answer
198
views
Generalized Shared Birthday
Suppose a year has $d$ days. How many people should be in a room so that there are at least $2k$ people in the room with birthdays shared with each other (all could be same day or there could be $k$ ...
user94040
3
votes
0
answers
81
views
Combinatorial/probabilistic interpretation of a quantity of union closed family
Let $\mathcal{F}\subseteq2^{[n]}$ be a union-closed family of sets. For a set $S\in[n]$ (not necessary belong to $\mathcal{F}$), define $w_{\mathcal{F}}(S)$ to be the number of subset of $S$ which ...
- 1,462
3
votes
0
answers
81
views
Can we remove the restriction on a parameter in Talagrand concentration inequality?
Recently I am trying to use Talagrand concentration inequality to do something on graphs. I find a version from the book of Molloy and Reed ''Graph Colouring and Probabilistics Method''. I attached a ...
- 1,190
3
votes
0
answers
54
views
Multi-type Galton-Watson-like process where only majority-type is allowed to reproduce
Are you aware of any research papers that have explored a multi-type Galton-Watson process in which only particles of the majority type are permitted to reproduce in each generation?
I've been unable ...
- 56
3
votes
0
answers
187
views
Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets
Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
- 1,677
3
votes
0
answers
190
views
Probabilistic optimization problem on tree vertex selection without replacement proportional to the degree
We are given a tree $T(V,E)$ with $|V|=n$ vertices, where $V=\{v_1,v_2,\ldots, v_n\}$. We denote by $d_i$ the degree of vertex $v_i$ for all $i\in\{1,2,\ldots,n\}$.
In a sequential fashion, we select ...
- 1,677
3
votes
0
answers
151
views
Permutahedra Euler characteristic polynomials from cumulant-moment relation, a combinatorial proof?
Given the formal Taylor series, or e.g.f.,
$f(x) = 1 + \sum_{n \geq 1} m_n \; \frac{x^n}{n!}$,
the classical formal cumulants $c_n$ are generated from the formal moments $m_n$ via
$ \sum_{n \geq 1} ...
- 10.5k
3
votes
0
answers
517
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 ...
3
votes
0
answers
342
views
Sum of products of irreducible characters of the symmetric group over a subgroup
When trying to build a dual formulation for lattice gauge theories using Weingarten integration I am getting sums of the kind
$$I^{m, n}_{\mu, \nu} (\sigma, \tau) = \sum_{\pi \in S_n} \chi_\mu (\pi \...
3
votes
0
answers
94
views
Probability of a random collection of subsets being a cover
Consider the set $[n]=\{1,2,\ldots,n\}$. Suppose for each set $A\subseteq [n]$ I have a $p_A \in [0,1]$. I now create a random collection $\mathcal{W}\subseteq\mathcal{P}([n])$ of subsets of $[n]$ by ...
- 526
3
votes
0
answers
330
views
Random walk on $\mathbb{R}$ with "sticky" origin
Let $P_i$, $N_i$, and $Z_i$, $i\in\mathbb{N}$ be r.v.'s with the $P_i$, $N_i$, and $Z_i$ being identically distributed with known pdf's $f_P$, $f_N$, and $f_Z$, respectively; and with no dependence ...
- 313
3
votes
1
answer
184
views
Why is number of single cell clusters always greatest in a random matrix?
Consider a large $N\times N$ square lattice, where each cell has a probability $p$ of being "occupied" (let's call denote them as "black") and a probability $1-p$ of being empty (let's denote them as "...
user125648
3
votes
0
answers
116
views
Trace of Symmetric matrices in fixed rank
I am solving some problem related to symmetric matrices over a finite field $\mathbb{F}_q$ and I am stuck at the following problem:
For every $a\in\mathbb{F}_q $, let $S_a(t,m)$ be the set of all $m\...
- 179
3
votes
0
answers
178
views
Partitioning the coupons collected in the classical coupon collector's problem
Suppose that there is an urn containing $n$ different coupons, from which $m$ coupons are being collected, equally likely, with replacement.
Let $C(m)$ be the whole set of the $m$ collected coupons. ...
- 1,677
3
votes
0
answers
89
views
Two game-set inequalities
Here are a couple of curious related results about a generalized 2-player 1-set tennis game: the winner of the set is the first player to win $n$ games, and the winner of each game is the first player ...
- 1,190
3
votes
0
answers
115
views
Approximating the *conditional* probability of 1D discrete random walk not having revisited the origin given last position
I'm looking for a good closed form approximation to the following conditional probability, with provable approximation guarantees.
Consider a 1D random walk on the integers, starting at the origin, ...
- 101
3
votes
0
answers
142
views
Probability of hitting two vectors
Call an element of $ \{-m,\dots,0,\dots,m\}^{2^n}$ a vector. Assume $m = O(2^{2^n})$.
Let $u_1,u_2$ be vectors.
Let $\{v_1,\dots,v_{2^n}\}$ and $\{w_1,\dots,w_{2^n}\}$ be linearly independent ...
- 13.9k
3
votes
0
answers
303
views
Exchangeable or iid random variables and linear conditioning
Let $X_1,\ldots ,X_N$ be independent identically distributed random variables (or, more generally, exchangeable random variables,
but let's assume independence for simplicity). Then
$$
E(X_i\mid X_1+\...
- 1,765
3
votes
0
answers
202
views
Difficult Gaussian-sum inequality for large random Bernoulli-Toeplitz matrices
I have come across the following problem in an attempt to prove an entropy bound for large random Bernoulli-Toeplitz matrices (Conjecture 1 on p. 16 of this preprint by Clifford et al. 2015), which is ...
- 686
3
votes
0
answers
157
views
Growth of inner products between two random vectors on the sparse hypercube
We define the $s$-sparse hypercube in $\mathbb{R}^d$ as
\begin{align}
\mathbb{H}_s = \bigl \{ {\bf{v}} \in \{ -1, 0 , 1\}^d \colon \| {\bf{v}} \|_0 = s \bigr\},
\end{align}
where $ \| {\bf v} \|_0 $ ...
- 1,127
3
votes
0
answers
133
views
Batched coupon collector with quota
Assume that you draw coupons uniformly at random from a collection of $n$ coupons and you want to collect $m_i$ coupons of type $i$. This is referred to as the coupon collector with quota (http://www....
- 562
3
votes
0
answers
268
views
A generalization of coupon collector problem - $\geq1$ pick per experiment
Mix $T\geq1$ coupons numbered $1$ to $T$ with a set of $S\geq0$ number of dummy coupons with no numbers. Select $N\geq1$ coupons at each trial at random and put them back.
$N=1$ is standard coupon ...
user76479
3
votes
1
answer
339
views
Probability of Hamming weight
Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick ${n^t}$ random vectors $\{v_i\}_{i=1}^{{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$.
Denote $v_j\cap v_j$ to be ...
- 13.9k
3
votes
0
answers
183
views
Ticket lottery -- distributing $n$ tickets among $N$ people fairly
Suppose that I have $n$ tickets for an event that I want to distribute fairly among $N > n$ people. In this simple case, a lottery suffices. But suppose certain groups of people want to attend ...
- 429
3
votes
0
answers
231
views
On a problem of sphere-packing for Reed-Solomon codes
Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ...
- 307
3
votes
0
answers
238
views
The balls and bins model: bounding the marginal contributions in the m>>n regime
Consider the standard balls and bins process, where $m$ balls are thrown into $n$ bins, and consider the case where $m >> n$. Denote the load on bin $i$ by the RV $L_i$.
Given a set $S \...
- 31
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
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
3
votes
0
answers
143
views
finding rank-3 tensors compatible with a rank-2 tensor projection
I am interested in the following problem: Consider a rank-3 symmetric tensor $\boldsymbol{\sigma}$ with $\sigma_{ijk}$ where $\sigma_{ijk}$ can be 0 or 1, and the symmetry is with respect to any ...
- 41