All Questions
Tagged with pr.probability co.combinatorics
802 questions
0
votes
1
answer
189
views
Constructing a family of $3$-wise independence functions from $\mathbb{Z}_p^n \rightarrow \mathbb{Z}_p$
A family of function hash functions $\mathcal{H}:\{h:N\rightarrow M\}$ is call $k$-wise independent if whenenver $h$ is drawn uniformly from $\mathcal{H}$, let $x_1,\ldots,x_k$ be distinct elements of ...
- 10.4k
0
votes
0
answers
82
views
High probability bound on number of sparse solutions to Gaussian linear system
Suppose we have a random matrix $A \in \mathbb{R}^{m \times n}$ with all entries i.i.d. from the standard Normal distribution $\mathcal{N}(0, 1)$. Suppose $k$ divides $n$, and let $S \subseteq \mathbb{...
- 43
1
vote
0
answers
84
views
How can one build a min-2-wise independent small sample space from min-3-wise permutations?
I have been studying a polynomial-size set of permutations from one of my lectures. The below image, taken from the lecture notes PDF, illustrates how to construct min-3-wise permutations.
My ...
- 43
4
votes
2
answers
427
views
Binomial coefficient asymptotics
What is the probability that the number of heads in $n$ fair coin tosses is exactly $\lfloor n/2 + c\sqrt{n} \rfloor$
for $c \leq O(1)$, $n > \omega(1)$?
Of course the answer is
$$ \frac{1}{2^n} \...
- 1,440
16
votes
4
answers
597
views
The lattice spanned by $m$ random 0-1 vectors of length $n$
Consider $m$ random 0-1 vectors of length $n$. Let $L$ be the lattice spanned by them. What is the value of $m$ (as a function of $n$) for which it is true with positive probability that $L=Z^n$? More ...
- 4,219
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
4
votes
0
answers
1k
views
Number of arrangements that contain at least 1 path from top to bottom of 2D matrix
I have a $n\times n$ matrix of objects. $n'$ objects are black, and the rest $n^2-n'$ are white.
With that information, I can easily calculate the total number of black element arrangements that exist ...
- 47
2
votes
0
answers
71
views
Distance distribution for Cayley graphs of the fintie Heisenberg groups H3(Z/nZ) approaches Gaussian for large "n"?
I wonder several questions about Cayley graphs of finite Heisenberg groups H3(Z/nZ).
Question 1: do we know the diameter dependence on "n", at least for the standard choice of generators ? ...
- 24.9k
6
votes
1
answer
355
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
2
votes
2
answers
286
views
Finding an easy example applying the general Lovász local lemma
Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.
General Lovász local lemma: Consider a set $...
- 10.4k
10
votes
1
answer
477
views
Where does the definition of ($\infty$-)groupoid cardinality come from?
The cardinality of a finite set $X$ is the number of its elements. Once you know that, you would define the groupoid cardinality of a $\infty$-groupoid $X$ as the quantity
$$\lvert X\rvert := \sum_{[x]...
- 12.9k
4
votes
1
answer
225
views
What is the generalization of the formula for Chung and Feller's Theorem 2 to odd numbers of steps?
In their classical paper on fluctuations in coin tossing On Fluctuations in Coin-Tossing, Chung and Feller give a precise formula for the conditional probability of the number of positive “sides” of a ...
- 17k
0
votes
1
answer
231
views
Concentration inequalities for random sampling without replacement
Let a population $C$ consist of $N$ values $c_1, c_2, \cdots, c_N$, with $c_i\in \{0,1\}$. Let $X_1, X_2, \cdots, X_n$ denote a random sample without replacement from $C$ and let $Y_1, Y_2, \cdots, ...
7
votes
2
answers
347
views
Matrices over $\mathbb{F}_p$ that have nonzero determinant under any element permutation
$\DeclareMathOperator\GL{GL}$A few months ago, the following discussion took place on AoPS, concerning matrices that have nonzero determinant under any permutation of their entries: https://...
- 54.2k
1
vote
0
answers
122
views
On the derivation of some asymptotic expressions involving combinatorics
My questions come from the supplementary material in a recent preprint Nonequilibrium statistical mechanics of money/energy exchange models. My first question comes from page 35. Specifically, suppose ...
- 730
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 ...
- 61.9k
0
votes
1
answer
335
views
How far does a random walker travel before returning to the origin?
Consider a (continuous time) simple symmetric random walk on $\mathbb Z$, starting from the origin. Let us denote this random walk by $\{X_t: t\geq 0\} $. It is well known that this random walk is ...
- 188k
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(...
- 15.8k
13
votes
3
answers
1k
views
A property of unimodal sequences
It is well-known that $(-1)^j \sum_{i=0}^j (-1)^i\binom{n}{i} \geq 0$. This inequality can be used to prove Bonferroni's inequalities for example. Recently I noticed that a similar inequality applies ...
- 97
0
votes
0
answers
55
views
Modeling player interactions in multi-dimensional rating systems
In traditional rating systems (such as Elo), a player's strength is represented by a single scalar value, which is assumed to be consistent across different opponents. However, in some games, the ...
- 1
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
0
votes
2
answers
239
views
Computing the expectation of a quadratic matrix form involving Bernoulli and Gaussian distributed matrices
I am working with two random matrices, $Z$ and $H$:
$Z$ is an $n \times K$ matrix with entries sampled i.i.d. from a Bernoulli distribution: $Z_{ij} \sim \mathrm{Bernoulli}(p)$.
$H$ is a $K \times K$ ...
- 37
1
vote
0
answers
62
views
Nonintersecting witnesses of connectivity events in graphs
In my research I stumbled across a following result:
Let $G = (V, E)$ be a multigraph with three chosen vertices $a, b, c \in V$. We color its edges into red and blue colors: $E = R \sqcup S$. Events ...
1
vote
0
answers
91
views
Large deviation inequalities for number of coupon types collected by a coupon collector with fixed budget
In the generalized Coupon Collector's Problem, there are $N$ types of coupon, and for any $i \in [N] := \{1,2,\ldots,N\}$, $p_i \ge 0$ is the probability of obtaining a type-i coupon on any trial. ...
- 6,853
2
votes
0
answers
56
views
Dirichlet series solution to Poisson Point Process question (repost from math.SE)
Reposting here because the bounty on the original math.SE post expired, with no solutions or comments received.
For any discrete subset $S$ of $\mathbb{R}^d$, consider a digraph formed by placing an ...
- 121
1
vote
1
answer
195
views
Concentration of a certain simple / well-structured random multilinear polynomial with growing degree
Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
- 63.9k
3
votes
2
answers
257
views
Grouping lists together in a proportional election: image of a Dirichlet distribution by the D'Hondt method of proportional allotment
A real-world motivation for this question is given below. But first let me recall what the Jefferson-D'Hondt “greatest divisors” method of proportional allotment (often used in electoral systems to ...
- 3,255
11
votes
1
answer
2k
views
Bounding the entropy of a convolution
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
CommunityBot
- 1
2
votes
0
answers
68
views
What is an efficient non-adaptive group testing scheme if the number of defectives, $d$, grows proportionally to the number of items, $n$?
Suppose that for some $p \in \left(0, 1\right)$ and some $n \in \mathbb{N}$, we have $n$ independent Bernoulli random variables, $X_{1}, X_{2}, \dots, X_{n}$, each with mean $p$. We shall call $X_{1}, ...
4
votes
1
answer
197
views
On a double sum involving binomial coefficients
For natural $n$, let
\begin{equation}
p_n:=2^{1-n}\sum_{v=1}^l \binom l{(v+l)/2}1(v\equiv l)
\sum_{u=1-v}^{v-1}\binom k{(u+k)/2}1(u\equiv k), \tag{1}\label{1}
\end{equation}
where $k:=\lfloor(n+1)/...
- 311
1
vote
0
answers
60
views
Correct dependence for "Local Coloring"
In Alon-Spencer's book, Probabilistic Lens #8, it is proven that for each $k$, there exists $\epsilon = \epsilon(k)>0$ such that for all large $n$, there exists an $n$-vertex graph $G$ with ...
- 3,499
-3
votes
1
answer
117
views
Combinatorial meaning of a reduced fraction in a simple probability problem?
A routine exercise for undergraduates says: Given that the number of successes in $20$ independent Bernoulli trials was $8,$ what is the conditional probability that exactly $3$ of those $8$ successes ...
1
vote
0
answers
92
views
Can we prove the following statement for recurrence relation?
For every integer $n$, we have the following recurrence:
$a_{i}= p^i(1-p)^{n-i}\binom{n}{i} -\sum_{j=i+1}^na_j\binom{j}{i}$.
Can we prove that for every $n$ and $p<1/\sqrt{n}$, it holds that $\...
- 11
1
vote
0
answers
77
views
Distribution of colour pairs from a random matching
Given $a$ many red balls and $b$ many blue balls, with $a+b$ even, suppose we chose a random matching between the $a+b$ balls. What is the distribution of the number of red-red and red-blue (and blue-...
- 129
1
vote
1
answer
186
views
Expected cardinal of the intersection between a random subset and a fixed subset
I have a set of size $n$, and a fixed subset $A$ of cardinal $k$. I take a random subset $X$ of cardinal $d$. I need to compute the expected cardinal of the intersection between $A$ and $X$.
I tried ...
- 5,429
2
votes
1
answer
115
views
Randomly chosen walk of fixed length
Let $G=(V, E)$ be the graph on vertices $V = \{0, \cdots, k\}^n$, where vertices $(v_1, \cdots, v_n)$ and $(w_1, \cdots, w_n)$ share an edge iff $\lvert v_i - w_i\rvert \leq 1$ for all $i$.
A walk of ...
- 17k
1
vote
0
answers
216
views
Classical and free cumulants, symmetric functions, and inverses (references), related to associahedra, parking functions, noncrossing partitions
Looking for references for one or more of the following four sets of partition polynomials 1a) through 4a), particularly those which present geometric / topological combinatorial interpretations.
...
- 10.5k
9
votes
1
answer
1k
views
The length of the longest consecutive string of heads or tails that occur asymptotically almost surely when a unbiased coin is flipped repeatedly
Consider an unbiased coin being flipped $n$ times, and suppose we label the outcomes as Heads = 0, and Tails = 1. Then the result of the flipping is a finite binary sequence of length $n$. Let us ...
- 10.4k
98
votes
17
answers
123k
views
Google question: In a country in which people only want boys [closed]
Hi all!
Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is:
...
- 257
4
votes
0
answers
540
views
How should the proof of the XYZ theorem be understood?
The XYZ Theorem of Shepp [1] states the following for a given poset $P$. Consider the probability space of all the linear extensions of $P$, where each possible extension is equally likely. Then for ...
- 4,219
3
votes
1
answer
229
views
Maximum cardinality of separated sets in the Hamming distance
This question is motivated by section 15.1 (Codes) of Alon and Spencer's The probabilistic method.
Fix $\alpha<\frac{1}{2}$ and for each $n\in\mathbb{N}$ let $\{0,1\}^n$ be the length $n$ binary ...
- 10.4k
0
votes
1
answer
119
views
How many samples do you need to get constant dispersion?
Let $C_n$ be the hypercube $[-1,1]^n$. For $a_1,\cdots,a_s \in C_n$, define its dispersion $D(a_1,\cdots,a_s)$ as $\max_{x \in C_n}\min_{i \in [s]} \|x-a_i\|_{2}$. Let $0< \lambda < 1$ be a ...
- 261
2
votes
0
answers
148
views
Union of two copies of uniform spanning forest on $\mathbb{Z}^3$ is transient? [closed]
Let $G$ be the (random) graph which is the union of two independent copies of the uniform spanning forest on $\mathbb{Z}^3$.
Question: Is (the simple random walk on) $G$ transient almost surely?
- 24.2k
2
votes
1
answer
201
views
Dispersion of a "random" subset of $[-1,1]^2$
Let $C$ be the square $[-1,1]^2$. Let $a_1,\dots,a_m$ be points chosen independently and uniformly at random from $C$. Let $d_m$ (dispersion) be the random variable $\max_{x \in C}{\min_{j \in [m]}{\|...
- 1,190
4
votes
0
answers
414
views
Explicit formula for tournament sequence
I am looking for an explicit formula for a sequence. The sequence is generated as follows:
There is a tournament with $10$ teams. In the beginning, all teams have a 0-0 win-loss record. The teams are ...
- 41
4
votes
1
answer
167
views
A probability problem in the conjugacy classes of symmetric group
Assume that $\sigma\in S_n$ has the cycle type $(p,.,p,1,..,1)$ where $p>2$ is a prime and the numbers of $1$ maybe $0$. If $\sigma_1$ and $\sigma_2$ are chosen uniformly in the conjugacy class of $...
- 9,720
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
2
votes
1
answer
224
views
Approximate size of the image of functions $f:[n]\to[n]$ [closed]
The following is inspired from the most recent riddle of the week of the German news magazine Der Spiegel.
For any positive integer $n\in\mathbb{N}$, let $[n]$ denote the set $\{1,\ldots,n\}$. Let $...
- 32.1k
51
votes
3
answers
4k
views
What is the sandpile torsor?
Let G be a finite undirected connected graph. A divisor on G is an element of the free abelian group Div(G) on the vertices of G (or an integer-valued function on the vertices.) Summing over all ...
18
votes
3
answers
8k
views
Number of invertible {0,1} real matrices?
This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.
My question is: how many such matrices ...
- 32.1k