All Questions
Tagged with pr.probability co.combinatorics
802 questions
2
votes
1
answer
177
views
Representations of zero as the sum of integers
Considering certain random walks I came up with the following question: Given a finite set $A$ containing positive and negative integers, how many representations of zero as the sum of $n$ integers ...
- 1,305
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 ...
CommunityBot
- 1
3
votes
1
answer
282
views
Longest runs and concentration of measure
Consider the longest runs $\ell_\sigma(x)$ of the pattern $\sigma$ for $\sigma\in \{0, 1, 01, 10, 001,\dots\}$ etc. in a binary sequence $x=x_1\dots x_n$.
For example, $\ell_{001}(0001110010011001)=2$...
- 23.2k
1
vote
1
answer
357
views
Analysis of a partition algorithm
EDIT:
I realized that if $J$ is not a solution so is $J^c$. I updated the algorithm because of this.
Given some positive integers $x_1,\cdots, x_n$.
The following algorithm is for solving the ...
CommunityBot
- 1
1
vote
0
answers
157
views
Probability that a sum is less that a given value [closed]
I don't have many skills in probability theory, so I need a little help. My problem is the following:
Let $n_1,n_2,...,n_k\in[0,1,...,n]$ such as $n_1+n_2+...+n_k=n$. Which is the probability that $$...
- 11
12
votes
3
answers
1k
views
How to sample a uniform random polyomino?
A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, ...
CommunityBot
- 1
2
votes
0
answers
227
views
Average minimum number of random k-sparse vectors in $\mathbb{F}_2^n$ to span a specific base vector?
A while back I posted a question in MO about the average minimum number of independent random k-sparse (having at most $k$ non-zero elements) vectors belonging to $\mathbb{F}_2^n$ to span the whole ...
CommunityBot
- 1
4
votes
0
answers
107
views
Random polyominoes containing $2\times2$ squares
The construction quoted in the question "How to sample a uniform random polyomino?" claims to produce a "uniform random polyomino". But apart from the mentioned possibility of getting stuck, it also ...
CommunityBot
- 1
0
votes
0
answers
87
views
Variation on stones in buckets
This is a spinoff, see Collecting stones in n buckets. Frankly speaking my only motivation is that I became curious: what happens if one redistributes the stones into the same buckets?
More ...
CommunityBot
- 1
4
votes
1
answer
299
views
Collecting stones in n buckets
There are $n$ stones distributed in $n$ buckets (initially one stone in each bucket). At each step the content of each bucket is put in a random bucket, chosen independently out of a set of $n$ new ...
CommunityBot
- 1
2
votes
1
answer
150
views
Probability of collision of some family of hash functions
Given $x$ and $y$ in $\mathbb{R}$, and let $\mathcal{H} = \{ h \mid \mathbb{R} \to \mathbb{N} \}$ be a family of hash functions where $ h(x) = \left\lfloor x + \sum^C_{i=1} U_i \right\rfloor$ for some ...
- 128k
1
vote
1
answer
1k
views
A generalized urn-ball matching problem; Complicated combinatoric/probabilistic limit
I'm looking for a generalization to the urn-ball matching problem. As a reminder of what I've got in mind, here's the simple version:
Randomly assign (with replacement) $N$ balls to $M$ urns. ...
CommunityBot
- 1
2
votes
0
answers
386
views
A two variable recurrence relation with conditionals
I have arrived at the combinatorial problem of enumerating certain types of ballot paths. This has led to analyzing the sequence defined by the following recurrence
$$
f(n,m) = \begin{cases} f(n, \...
- 305
10
votes
0
answers
222
views
Asymptotics of subgraph densities in graphons
In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
- 986
2
votes
1
answer
300
views
Number of subsets that sum to $0$
Suppose you choose $n$ distinct random numbers from a contiguous subset of cardinality $f({\beta, n})$ with at least $f({\alpha_+, n})$ positive and at least $f({\alpha_-, n})$ negative values from a ...
- 32.1k
0
votes
0
answers
86
views
Derandomizing AP existence in $A\subseteq \{1,\ldots,N\}$ for $\delta(A) \geq 1/k$
In the answer to the mathoverflow question here, it was established that if we let $p$ be the probability of including point $v$ in $A\subseteq \{1,\ldots,N\}$ and this is done independently for all ...
CommunityBot
- 1
1
vote
0
answers
135
views
A probability question related to combinatoric problem
I am trying to solve a combinatoric problem. The problem is the following:
There are A,B,C three types of people. There are totally N people arriving sequentially and make a choice between two boxes X ...
- 191
3
votes
2
answers
254
views
Probability of no $k$ 1's in arithmetic progression in binary sequence of length $n$
It is well known [it's on Wolfram Mathworld, for example] that the probability of no runs of $k$ consecutive $1$'s will occur in a $\{0,1\}$-valued sequence of length $n$ is exactly equal to $$\frac{F^...
- 10.4k
4
votes
1
answer
149
views
Probability of existence of a base in the span of sparse vectors in GF(2)
For $i=1,2,\dots,l$, let $\mathbf{v}_i =(v_{i1},v_{i2},\dots,v_{in}) \in \mathbb{F}_2^n$ be a sparse vector in GF(2) such that all $v_{ij}$'s are independent for all $1 \le i \le l, 1 \le j \le n$ and ...
- 54.2k
6
votes
1
answer
837
views
Average minimum number of random k-sparse vectors in GF(2) to span the whole space?
What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? ...
CommunityBot
- 1
7
votes
1
answer
342
views
Upper Bound for the Difference of Even Probability and Odd Probability in Hypergeometric Distribution
Let $X$ be a random variable following the hypergeometric distribution with parameters $N,K,n$, where
\begin{equation}
Pr(X=k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}.
\end{equation}
To ...
- 3,574
1
vote
1
answer
95
views
Reference for a local density theorem for binary vectors
I have the following theorem written on my whiteboard, but have misplaced the reference. I believe the probabilistic method may be involved in the proof. Any pointers appreciated.
Theorem Let $v\in\{...
- 10.4k
5
votes
3
answers
1k
views
A conjecture about the entropy of matrix vector products
Consider a random $m$ by $n$ partial circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$ and let $m < n$. Now consider a random $n$ dimensional vector $v$ ...
CommunityBot
- 1
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
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
6
votes
0
answers
113
views
Probabilistic distribution of sandpile model type
Let $G=(V,E)$ be a connected graph. Assume that $m\leqslant |V|$ hedgehogs sit in the vertices of $G$. If there are $r\geqslant 2$ hedgehogs in the same vertex $v\in V$, one of them goes to a randomly ...
- 109k
1
vote
0
answers
87
views
How to estimate the size of balanced biclique in random bipartite graph?
We have a random bipartite graph $G=(V,U,E)$ and $|V|=|U|=n$, in which any vertex pair $<v,u>$ ($v\in V$,$u\in U$) exists an edge with probability $p$. A balanced bipartite complete graph is a ...
- 11
9
votes
1
answer
564
views
combinatorics on cyclic sequences
Given $m\geq 1$, let $I=(a_1,\ldots,a_{3m})$ be a sequence such that $I$ contains exactly $m$ zeros, $m$ ones, and $m$ twos.
Given $i=1,2$ and $j\leq 3m,k\leq m$ we can define $$U_{i,j}(k)=\text{...
- 10.7k
2
votes
1
answer
186
views
Probability of covering a set
Suppose we have a set of $N$ numbers. At any given trial we can randomly choose $N^{1-a}$ of the numbers where $a\in(0,1)$. We replace the numbers back.
How many trials does it take in average case ...
- 13.9k
6
votes
0
answers
277
views
universality for large deviations?
This is a question about universality in probability theory, with combinatorics in mind.
Consider a sequence of polynomials $P_n$ in one variable, with positive coefficients. Combinatorics is a large ...
- 3,587
18
votes
4
answers
1k
views
Pennies on a carpet problem
I recently read the following "open problem" titled "Pennies on a carpet" in "An Introduction To Probability and Random Processes" by Baclawski and Rota (page viii of book, page 10 of following pdf),...
CommunityBot
- 1
8
votes
1
answer
723
views
Does $|A+A|$ concentrate near its mean?
Fix $N$ to be a large prime. Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a random subset defined by $\mathbb{P}(a \in A) = p$, where $p = N^{-2/3 + \epsilon}$ for some fixed $\epsilon > 0$. My ...
- 14.2k
3
votes
1
answer
1k
views
How many times does a simple symmetric random walk of length n return to the origin?
Consider the simple symmetric random walk on the integers starting from
the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as
$$ w:= \omega_0 \omega_1 \ldots \...
- 5,721
2
votes
0
answers
72
views
Sampling efficiently conditioned on linear constraints modulo both $\mathbb{F}_p$ and $\mathbb{F}_2$
Given a prime $p$ and positive integer $t \ll \log p$ (say $t = \sqrt{\log p}$), is there an algorithm that is polynomial time in $\log p$ to sample uniform $X, Y \in \mathbb{F}_p$ conditioned on the ...
- 305
18
votes
1
answer
890
views
Two conjectures about zero inner products and dissociated sets
The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
CommunityBot
- 1
39
votes
2
answers
2k
views
Random sequence of integers in $\{1, 2, \dots, n \}$ which is "everywhere probably increasing" - how long can it be?
Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$.
Fix $r \...
- 148k
1
vote
1
answer
123
views
$q$-connectedness of random digraphs obtained from a fixed graph
Let $G = (E,V)$ be an undirected graph (which can have multiple edges or loops).
Let $k,l,m\colon E\to \mathbb{R}_{\geq 0}$ be three edge-weight functions that satisfy $2k(e) + l(e) + m(e) = 1$ for ...
- 28k
7
votes
1
answer
441
views
Recursive sequence of binomial random variables
Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and
$$X_{k+1} = X_k + \text{Bin}(X_k,p).$$
Thus, $\mathbf E [ X_k ] = (1+p)^k$.
I would like a left tail bound. Perhaps, ...
- 457
11
votes
2
answers
714
views
Pursuit-Evasion type game on graph ("Flyswatter game")
An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...
- 14.2k
8
votes
1
answer
174
views
Equalizing Geometric means of Graph Cycles
Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...
CommunityBot
- 1
13
votes
7
answers
2k
views
Finite-space dynamical systems
This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ ...
CommunityBot
- 1
12
votes
1
answer
460
views
No limit shape for random Young diagrams under z-measure?
In their paper Random partitions and the Gamma kernel (Advances in Mathematics 194 (2005) 141–202), Borodin and Olshanski state that:
An important difference between the Plancherel measures and the ...
CommunityBot
- 1
6
votes
2
answers
2k
views
Distribution of $\max_{n \ge 0} S_n$, random walk
Say we have a random walk that is a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
- 406
0
votes
1
answer
81
views
An asymptotic set containment problem [closed]
Given a set of $n\in\Bbb N$ integers $\mathcal S$, suppose we choose two sets:
$$\mathcal S_{\mathsf{small}}\subseteq\mathcal S$$
$$\mathcal S_{\mathsf{big}}\subseteq\mathcal S$$ with cardinalities
...
- 4,529
30
votes
1
answer
942
views
partition of infinite word onto permitted words
Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, $0<c&...
- 61.9k
1
vote
1
answer
173
views
Probability of paths to the boundary of a tree
Let $G_n$ be the $4$-regular tree of depth $n$, that is to say the finite graph given by the ball of radius $n$ in the Cayley graph of the free group on two generators. By the root I mean the vertex ...
- 3,937
1
vote
0
answers
70
views
Bounds on product of CDF or Beta function
I have functions of the form
\begin{align}
I_i = \int_0^\infty F_0(x)^aF_1(x)^b(1-F_0(x))^c(1-F_1(x))^ddF_i(x),~~~~i = 0,1.
\end{align}
$F_0(x)$ and $F_1(x)$ are CDFs corresponding to the random ...
- 19.6k
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
1
vote
0
answers
46
views
Is there an effective algorithm for finding "minimal discovery times" for large graphs?
Consider a large, probably sparse graph with Markovian random walkers on it.
Define the discovery time as the expected time to first reach a vertex by
random walk from a uniform start. Are there ...
- 19.6k
4
votes
3
answers
570
views
Maximum difference between heads and tails in absolute value
I toss a fair coin $n$ times. Some notation:
$S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$.
$M_n=\max(S_1,S_2,\dots,S_n)$,
$m_n=\min(S_1,S_2,\...
- 406