All Questions
Tagged with co.combinatorics pr.probability
802 questions
2
votes
1
answer
62
views
Average number of rows to fit all elements in a multiset of natural numbers
Consider a multiset $S=\{a_1,a_2,...,a_{2n}\}$ of natural numbers. There are $2n$ elements (not necessarily unique since $S$ is a multiset) in $S$. All elements of $S$ belong to a set of natural ...
- 25
5
votes
1
answer
206
views
Probability of finding one sub-object vs a million disjoint ones
Let $W$ be a set of words of length $n$ on the three letters $a$, $b$ and $\ast$. Say that an element $w$ in $W$ ``matches" a word $w'$ of length $n$ on the letters $a$ and $b$ if each $\ast$ in $w$ ...
- 257
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
1
vote
1
answer
121
views
Probability for high mutual coherence on all subsets of a Gaussian vector set
We examine as set of independent normal vectors:
$$ \forall i \in [N]\triangleq \{1,\dots,N\}:\,\mathbf{x}_{i}\sim\mathcal{N}\left(0,\mathbf{I}_{d}\right)$$
For any $\epsilon>0$ and $K\leq N$, we ...
- 968
-1
votes
1
answer
428
views
Bins and colored balls
Consider $n$ color balls. We throw them as follows. For a given ball $i$, randomly choose $k$ bins; create $k$ 'copies' of the ball (i.e., of the same color of the ball $i$); throw a 'copy ball' into ...
- 367
4
votes
1
answer
207
views
Upper bound on the number of binary matrices with small rank
I'm looking for the tightest upper bound on the number of different binary matrices $A \in {\{-1,1\}^{m \times n}}$ for which $\mathrm{rank}(A)\leq r$. I'm interested in the regime $1 \ll r \ll m \...
- 968
1
vote
1
answer
85
views
Distribution of the cover time of a finite path?
The title says it all. I am interested in the discrete time simple random walk on a path of $n$ nodes, with reflecting barriers. It's clear that the expected value for the cover time $C_n$ is $\frac{5}...
- 23
106
votes
5
answers
10k
views
integral of a "sin-omial" coefficients=binomial
I find the following averaged-integral amusing and intriguing, to say the least. Is there any proof?
For any pair of integers $n\geq k\geq0$, we have
$$\frac1{\pi}\int_0^{\pi}\frac{\sin^n(x)}{\...
- 43.2k
0
votes
1
answer
221
views
Non-erasure probability in a loop-erased random walk in three dimensions
Perform a simple random walk $S(0),S(1),S(2)...$ on $\mathbb{Z}^3$, that is $S:\mathbb{N}\to\mathbb{Z}^3$ with $||S(i)-S(i+1)||_1 = 1$ for all $i$. Now let $\Gamma_n$ be the loop-erasure of the first $...
- 191
4
votes
0
answers
83
views
The max of a random sum, SK model
Let $(N_{i,j}, i,j \in \mathbb N)$ be independent (standard) Gaussian random variables.
What is known/ what is conjectured /what can we say about
$$\max \lbrace{\sum_{1 \leq i,j \leq n} \epsilon_i \;...
- 468
1
vote
1
answer
215
views
Random walks cover time in random regular graphs
Let $G=(V,E)$ be a random $r$-regular graph on $n$ nodes. Perform a random walk on $G$, starting from a node chosen according to the walk stationary distribution (i.e. chosen uar from $V$).
Claim. If ...
- 23
9
votes
1
answer
640
views
Inner product over finite fields
Let $F$ be a finite field,
For every $c \in F$, let $X_1, X_2,..., X_9, Y_1,..., Y_9$ be independent non-zero random variables over $F$.
Denote $X=(X_1,...,X_9)$, $Y=(Y_1,...,Y_9)$, also let $\...
- 93
0
votes
0
answers
82
views
The effect of channel error on the determinant of transmitted matrix
Assume the following matrix
$$
E:=\left(
\begin{array}{ccccc}
e_1 & e_2 & \cdots & e_{p-1} & e_{p}\\
e_{p+1} & e_{p+2} & \cdots & e_{2p-1} & e_{2p} \\
\...
- 313
7
votes
1
answer
318
views
Finding a short path using $(0.99n)!$ permutations
Suppose I have $n$ points $x_1,\dots,x_n$ that are all independent uniform samples in the unit square, and I'd like to find a short path (in terms of Euclidean length) that touches all of them (a ...
- 4,049
2
votes
2
answers
698
views
Expected Number of edges for a graph to have a Triangle?
i want to compute the (Approximated) expected number of edges for a graph to have some triangles (loop with length 3)
i just solved a similar simpler problem:
Generate a random graph on $n$ vertices ...
- 550
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,648
4
votes
0
answers
141
views
Level sets of function of inner products of vectors on hypercube
Let $H = \{ 0, 1\}^d$ be the $d$-th Cartesian product of $\{0, 1\}$ in $\mathbb{R}^d$. Suppose $v_1, \ldots, v_k$ are $k$ vectors in $H$ in general position. We define function $F \colon H^{k}\...
- 1,127
5
votes
0
answers
235
views
Riemann theta function inequality for a class of large random matrices
The following is essentially the same question as in this previous post, but since I have completely re-formulated it (hopefully for the better ;-), I decided to post a new question instead of an edit....
- 686
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$...
- 24.8k
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
26
votes
4
answers
2k
views
$\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$ is a convex function on $[0,+\infty)$?
Let $f(x)=\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$, where $u\in\mathbb{Z}^+$ and $\binom{x}{l}=\frac{x(x-1)\dots(x-l+1)}{l!}$ for all $l\in\mathbb{Z}^+$.
Then can we prove $f(x)$ is a convex ...
- 271
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
13
votes
4
answers
535
views
Alignment of random points
Whenever I draw randomly about ten points, I see that there will be always 3 points that are "almost" collinear. This observation leads me to considering the following questions:
Question 1: Suppose $...
- 131
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 ...
user6671
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 ...
- 13.4k
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, ...
- 7,857
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 ...
- 18.4k
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 ...
- 307
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 ...
- 321
0
votes
1
answer
414
views
Exact formula for computing n-step transition probability of random walks with self-transitions
Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...
- 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
6
votes
1
answer
985
views
A variant of bin-and-ball problem
We have $n$ balls, each belonging to a group (e.g, color). There are $g$ groups ($g$ may be large but $g=o(n)$). We sequentially put the balls into $m$ bins in the following way: for each ball, we ...
- 367
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 ...
- 1,269
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 ...
user76479
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 ...
- 10.4k
2
votes
1
answer
272
views
A generalization of negative binomial distribution
Assume we have a set of $n$ balls. For each step, we uniformly pick one ball and label it if it is not labeled. Or otherwise move on to next step. I am wondering what is the distribution of number of ...
- 61
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
4
votes
2
answers
314
views
Convexity of truncated expectation
Let $k, n$ be two positive integers with $k \leq n$, and let $P = \{ (x_1, \dots, x_n) \in [0, 1]^n : \sum_i x_i = k \}$.
Given $x = (x_1, x_2, \dots, x_n) \in P$, let $X_i$ be the random variable ...
- 41
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 ...
- 307
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$? ...
- 307
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 ...
- 183
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
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
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
2
votes
3
answers
498
views
High order central moments of a symmetric binomial variable
Consider a random variable $X\sim B(n,\frac 12)$. I'm trying to estimate the asymptotic behaviour of its central moments $E((X-\frac n2)^r)$, where $r$ is even and in the range $\Omega(1)\leq r\leq O(...
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{...
- 167