All Questions
Tagged with pr.probability co.combinatorics
802 questions
3
votes
1
answer
109
views
Asymptotic estimate of the cardinality of $H_{2n}=\{\vec{a} \in [-N,N]^{2n}:\sum_{i=1}^{2n} a_i = 0\}$
Let's suppose $a_i \sim \mathcal{U}([-N,N])$ where $[-N,N] \subset \mathbb{Z}$. We may then define:
\begin{equation}
S_n = \sum_{i=1}^n a_i \tag{1}
\end{equation}
Now, in order to estimate $\lvert ...
- 3,871
2
votes
0
answers
83
views
Zero-One law for Hamiltonian path subgraphs of Hamming Distance Graphs?
$(\alpha,\beta,d)$-Hamming Distance Graph $G_d(\alpha,\beta)$ for $\alpha,\beta\in(0,1]$ is a graph on $2^d$ vertices $v_0,\dots,v_{2^d-1}$ with edges $(v_i,v_j)\in\mathcal E(G_d)$ iff $0<\sum_{t=1}...
- 13.9k
1
vote
1
answer
684
views
Probability that random Bernoulli matrix is full rank
This is probably known already, but I could not find a quick argument.
Let $M$ be an $n\times m$ binary matrix with iid Bernoulli$(1/2)$ entries, and $n>m$. Tikhomirov recently settled that the ...
- 1,096
17
votes
3
answers
923
views
Random permutations from Brownian motion
Let $B(t)$ be a Brownian motion. The ordering of $(0, B(1), ..., B(n-1)) $ is a random permutation in $S_n$. This is not uniform for $n>2$ since the probabilities of the identity permutation $[123.....
- 511
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 ...
- 128k
-2
votes
2
answers
280
views
Balls into bins with random number of balls
In the classical balls into bins we throw $m$ balls into $n$ bins. We throw the balls independently of each other and the probability of choosing the bins is uniform. For $n=m$ it is known that the ...
11
votes
1
answer
867
views
Simulate coin tossing by die tossing
On the one hand we toss $n$ times a fair coin, and we sum the outcomes (+1 for heads, -1 for tails). Let $f:\mathbb{N}\to\mathbb{R}$ describe the probability distribution of the outcome.
On the other ...
- 3,486
8
votes
1
answer
598
views
Expected value of biggest distance of adjacent points uniformly picked in $[0,1]$
We pick $n\ge 2$ points in $[0,1]$ with uniform distribution. What is the expected value of the largest distance of $2$ adjacent points?
- 14.2k
5
votes
3
answers
2k
views
Batched Coupon Collector Problem
The batched coupon collector problem is a generalization of the coupon collector problem. In this problem, there is a total of $n$ different coupons. The coupon collector gets a random batch of $b$ ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 2,821
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
2
votes
0
answers
109
views
Average number of pieces of a random piecewise-linear function
Let $I$ be a (nonempty) compact interval in $\mathbb R$ and $a_1,b_1,\ldots,a_L,b_L \in \mathbb R$. Let $\varphi$ be a piecewise function with $T \ge 2$ pieces(for example $T=2$ for the choice $\...
- 6,853
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 ...
- 14.2k
3
votes
1
answer
341
views
Spectral radius of Markov averaging operator on graphs
The definition of Markov operator which I am familiar with:
For a graph $G=(V,E)$, Markov's operator upon a function
$\varphi:V\rightarrow\mathbb{C}$ , $\varphi\in L^2(G,\nu)$ ($\nu(v):=\deg(v)$) ...
- 33
1
vote
2
answers
116
views
How to use probability to find a matching in a family of graphs?
In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...
- 14.2k
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
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 ...
- 23k
4
votes
1
answer
839
views
A balls into bins problem with combinatorial constraints
We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into ...
- 1,677
2
votes
1
answer
142
views
The expectation of partition times needed separate two elements in a set
I met a problem which can be formulated as set partition.
Given a set $S=\{s_1,s_2,...,s_n\}$ having $n$ elements, I want to separate two elements, say $s_1,s_2$, in $S$ by repeatedly using set ...
- 32.5k
1
vote
0
answers
117
views
Entropy of endpoints of a random walk in a dense graph
Let $p\in[0,1]$ be a constant and let $G$ be a graph with $n$ vertices and $\approx p\binom{n}{2}$ edges. If you'd like, consider $p=1/2$.
Let $X$ be a random vertex of $G$ chosen proportional to ...
- 761
1
vote
1
answer
134
views
Random optimization problem
Let $V$ be a set of $n$-dimensional vectors such that, for each ${\bf v}\in V$ and for each index $i\in [n-1]$, we have $0\le v_{i+1}\le v_i$. Let $P(\cdot)$ be a discrete probability distribution ...
- 128k
4
votes
1
answer
398
views
Variance of load in maximally loaded bin, if $m$ balls are thrown into $n$ bins
In the paper "Balls and bins a simple and tight analysis" by Raab and Steger, available here strong upper and lower bounds are proved about the number $M$ of balls in a maximally loaded bin when $m$ ...
CommunityBot
- 1
2
votes
0
answers
58
views
Bounds for $\sum_{t=1}^Tn_t(s_t)^{-\alpha}\mu(s_t)$ where $n_t(s) = \sum_{1 \le t' \le t} 1_{\{s_{t'}=s\}}$ for $s \in [k]$ and $\mu \in \Delta_k$
Disclaimer: I'm not certain this is the right venue for this post, but I'll give it a try...
So trying prove some bounds in my ongoing work in theoretical reinforcement learning, I encountered the ...
- 6,853
1
vote
1
answer
72
views
Independent identical distribution sequence
given a measurable function $\alpha: (\Omega, \mu) \to \mathbb{R}$, and transformation $\sigma : \Omega \to \Omega $.
I found an example such that $\alpha, \alpha\circ \sigma, \alpha\circ \sigma^2, \...
- 23.2k
8
votes
1
answer
576
views
probability theory for combinatorialists
More than one combinator(ial?)ist has asked me to recommend a good book to learn probability from, and I never know what to say; the probability theory that I use in my research up was mostly learned ...
- 41
14
votes
3
answers
694
views
Probability to be the winner in a tournament
In a project in Game Theory we (Ayala Arad and Ariel Rubinstein) are stuck with the following "simple" question. We are sure of the conjecture but we failed to find a (hopefully simple) proof:
Let $...
- 52.3k
7
votes
3
answers
2k
views
Problem about expectation of maximum partial sum
Given a number $m$, a random composition (strong) of this number into $n$ positive parts so that we can get $n$ random variable $X_1, X_2,\dots, X_n$ with $$X_1+X_2+\cdots+X_n=m$$
Note that all ...
- 2,821
3
votes
1
answer
108
views
Expected size of matchings in a cubic graph
Let $G$ be a random cubic graph on $n$ vertices. Let $M$ be the set of (not necessarily maximum) matchings of $G$. What is the expected size (i.e. number of edges) of an element of $M$?
In other ...
- 37.7k
1
vote
0
answers
221
views
Different balls in bins: What is the probability distribution of the sum of the minimum of the two types of balls over all bins?
Assume that there are $N$ different bins and two different kinds of balls, $R$ red balls and $W$ white balls.
The red balls and the white balls are randomly distributed across the bins (that is, for ...
- 63.9k
1
vote
0
answers
46
views
Gilbert-Varshamov with weight condition
For $N$ integer, it is known (Gilbert-Varshamov) that there exists a subset $S$ of $\{0,1\}^N$ such that $|S|$ is still exponential in $N$ and such that two elements $x, x'$ in $S$ are at least ...
- 141
0
votes
0
answers
62
views
Probability of detecting small bias in a die in the low confidence regime
We are given a biased $m$-sided die: one of the sides has probability $\frac{1}{m} + \gamma$ and all the rest have probability $\frac{1}{m} - \frac{\gamma}{m-1}$ each. The goal is to figure out which ...
- 211
2
votes
1
answer
106
views
How to efficiently sample uniformly from the set of $p$-equipartitions of an $n$-set?
I have a question related to this one. For $n,p \in \mathbb{N}_+$ such that $p\mid n$, let $\mathcal{P}^{\rm eq}$ be the set of all equipartitions of $n$ in $p$ sets; i.e., in sets of equal size $\...
- 1,372
2
votes
2
answers
243
views
Birthday problem extension to unequal probabilities and multiple collisions
Let $p_1, ... ,p_k$ denote the probabilities of drawing bin $1, .. ,k$, where $\sum_{i = 1}^{k} p_i= 1$. My question is if we draw $n$ times, how can I show that the probability that all bins are ...
CommunityBot
- 1
5
votes
0
answers
244
views
Distribution of point knowing target in optimal matching
I am a young PhD student in statistics.
Recently, papers (Ambrosio, Stra and Trevisan; Talagrand; Ledoux to cite but a few) tackled the problem of finding the expected cost in an optimal matching, ...
- 555
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
votes
1
answer
607
views
Component size distribution in small Erdos-Renyi networks
I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10.
I would like to know the probability a random node is in a component of size $m$.
It's ...
- 4,713
11
votes
3
answers
2k
views
Probability of unique elements in each of 'S' multisets sampled with uniform probability
Assume I have some set $P$ with $||P|| = N$ unique elements. I also have $S$ multisets, $(m_1, ..., m_S)$, of cardinality $L$, consisting of elements in $P$ chosen with uniform probability. We call ...
- 10.4k
3
votes
1
answer
822
views
Open Problems in Random Graphs [closed]
I am a PhD student in mathematics. I'm interested in probabilistic methods in combinatorics and especially random graphs. I am looking for an open problem in this area for my PhD proposal. I know that ...
- 151k
16
votes
6
answers
3k
views
analog of principle of inclusion-exclusion
When I teach elementary probability to my finite math students, a common error is to mix up the concepts of disjointness and independence. At some point I thought that it might be helpful to some ...
- 2,239
4
votes
0
answers
266
views
Metrics on finite groups and generalizations of central limit theorems for balls volumes (à la Diaconis-Graham)
In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation groups are considered and ...
- 63.9k
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 $\...
- 10.4k
2
votes
1
answer
179
views
How to uniformly sample a square (0,1)-matrix whose trace is 0 and whose row sums and column sums are the same?
Happy New Year!
Suppose I would like to sample a $n \times n$ (0,1)-matrix whose trace is 0, and whose row sums and column sums are all $m$ with $1 \le m \le n-1.$ How can I sample this matrix ...
- 37.7k
8
votes
1
answer
2k
views
Van Den Berg-Kesten-Reimer inequality
Van Den Berg-Kesten-Reimer inequality
Let $n$ be a positive integer. For $i\in[n]$, let $\Omega_i$ be a finite set and $\mu_i$ a probability measure on it. Set $\Omega=\Omega_1\!\times\!\ldots\!\...
- 148
8
votes
1
answer
171
views
On the existence of a particular type of finite measure on $\mathbb N$
Let $\mathbb N$ denote the set of all positive integers. Does there exist a countably additive measure $\mu : \mathcal P(\mathbb N) \to [0,\infty)$ such that $\mu(\mathbb N)<\infty$ and $\mu(\{nk: ...
- 12.8k
10
votes
3
answers
2k
views
Mean maximum distance for N random points on a unit square
Following up on Mean minimum distance for N random points on a one-dimensional line and Mean minimum distance for N random points on a unit square (plane), I have the following questions.
Given N ...
- 4,361
10
votes
4
answers
9k
views
Mean minimum distance for N random points on a unit square (plane)
A previously posted question "mean minimum distance for N random points on a one-dimensional line" produced an elegant answer: for a line of length L, the expected minimum distance (between random ...
- 193
0
votes
1
answer
144
views
A problem related to the comparison of two integer-valued random variables
Consider an urn containing red, blue and green balls (the situation is the same illustrated in this post).
Let $X$ be the non-negative, integer-valued random variable defined as the number of trials (...
- 128k
1
vote
2
answers
399
views
Sums Of Independent Random Variables: Pathological Behaviour
Background:
The result of a chess game between two players is a win ,a loss or a draw which are (usually) scored respectively $1$ point, $0$ point or $0.5$ point for the appropriate player. Team ...
- 63.9k
7
votes
3
answers
1k
views
Sum of inverse of multinomial coefficients
Find an asymptotically tight estimate for the sum
$$
A_n^{k}(\lambda)= \sum_{
\substack{a_i\geq \lambda_i
\\
a_1+a_2+\dots a_k=n
}} \prod_{i=1}^k a_i!
$$
Is the leading term going to be
$$|\textrm{...
- 3,255