All Questions
Tagged with pr.probability co.combinatorics
802 questions
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\}$...
CommunityBot
- 1
14
votes
0
answers
1k
views
The threshold for a perfect matching in a random subgraph of a regular bipartite graph?
The following question seems very natural.
It is a well known consequence of Hall's Theorem that every regular bipartite graph has a perfect matching. Another classical result states that the ...
- 1,643
8
votes
4
answers
1k
views
A Pascal's-triangle -like random process
I was exploring Pascal's triangle on a cylinder when I encountered this puzzle-like problem.
It is surely elementary, but perhaps weekend-entertaining.
Start with a permutation of $(1,2,3, \ldots, n)$...
- 151k
6
votes
0
answers
133
views
Random Balanced Assignment
A balanced assignment from from $N$ objects to $K$ classes is a mapping $\sigma\colon \{ 1, \ldots, N\} \rightarrow \{ 1, \ldots, K\}$ such that
$$
\textrm{Card}( \sigma^{-1} \{j \} ) = \textrm{Card} ...
0
votes
0
answers
72
views
A random variable standing for the size of connected component including a given node in a tree
Suppose we have a tree $T = (V,E)$, in which each nodes $v_i \in V$ has a probability $p_i$ to vanish. Let $v_0\in V$, we define random variable $\boldsymbol{X} = \boldsymbol{X}(T, v_0)$ stands for ...
- 1,551
2
votes
1
answer
267
views
Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice
Imagine I have an $N$ by $M$ rectangular lattice where I randomly assign one of $k$ colors to every vertex in the lattice. I then write down a list of the ${N*M}\choose{2}$ possible unordered pairs ...
- 151k
2
votes
2
answers
1k
views
Generalization on Coupon Collector's Problem
Player extracts card from the deck (which has infinite number of size) to obtain one of $k$ colors of cards. The possibility that the player pick a card with $i$th color is given by $p_i>0$. Of ...
CommunityBot
- 1
5
votes
1
answer
327
views
homomesy and asymptotic behaviour
For simplicity, consider an infinite locally-finite poset $\mathcal{P}$ with a unique bottom element $\perp$ whose finite order ideals obey a hook-length formula --- i.e. the number of
linear ...
CommunityBot
- 1
7
votes
2
answers
186
views
Do successive maximum permutations pick latin squares uniformly?
Suppose we start with a $n\times n$ matrix with entries sampled independently and uniformly at random from $[0,1]$. The weight of a set of entries will simply be the sum of those entries. A ...
CommunityBot
- 1
10
votes
2
answers
3k
views
Random Unfoldings of the Cube
Motivated by unfoldings of the dodecahedron in How To Fold It --
How many (labeled or unlabeled) unfoldings of the 1 x 1 x n stack of unit cubes are there?
JORourke (4Nov16): John's original image is ...
- 151k
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)}{\...
CommunityBot
- 1
14
votes
0
answers
629
views
Probability of many overlapping zero inner products on a circle
[Question edited and changed a little on June 14 2015]
Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...
- 3,377
0
votes
1
answer
463
views
Expected number of connected components as $V(G)$ grows large
Let $E^c_n$ be the expected number of connected components of a simple undirected graph on the vertex set $\{1,\ldots,n\}$. (Every possible edge in $\big\{\{a, b\}: a, b\in \{1,\ldots,n\} \land a \neq ...
- 4,991
8
votes
0
answers
254
views
Quantum coupon collection: positivity of an alternating sum of matrices
It is well-known that in the classic coupon collecting problem (CCP), the expected waiting time is
\begin{equation*}
T_n(x_1,\ldots,x_n) = \sum_{k=1}^n (-1)^{k+1}\sum_{1\le i_1 < \cdots < i_k \...
- 28.6k
8
votes
2
answers
512
views
The average of reciprocal binomials
This question is motivated by the MO problem here. Perhaps it is not that difficult.
Question. Here is an cute formula.
$$\frac1n\sum_{k=0}^{n-1}\frac1{\binom{n-1}k}=\sum_{k=1}^n\frac1{k2^{n-k}}...
CommunityBot
- 1
9
votes
0
answers
1k
views
Balls and bins -- concentration bounds pertaining to the minimal load bin
Consider the standard balls and bins process, where $m$ balls are thrown uniformly at random into $n$ bins. Previous work has been done on estimating the value of the maximum load (i.e., the number of ...
- 618
-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 ...
CommunityBot
- 1
7
votes
3
answers
346
views
Concentration Bound of $0/1$ permanent
If I pick a random $0/1$ $n\times n$ matrix with $0$ occuring with probability $p$ then what does the distribution of the permanent look like?
- 2,720
7
votes
1
answer
222
views
Algorithm to generate random commuting permutations
I am seeking to understand the properties of a typical pair of permutations $(\sigma,\tau) \in \mathrm{Sym}(n)^2$ chosen uniformly at random from all pairs such that $\sigma$ and $\tau$ commute. In ...
- 8,688
2
votes
3
answers
192
views
Asymptotic behaviour of binomial term
Is it true that that ${{n}\choose{k}} p^k (1-p)^{n-k}$ is dominated by $\frac{1}{n}$, at least for $k$ sufficiently big?
EDIT: I saw that the question was absolutely not stated as I intended. The ...
- 6,711
5
votes
1
answer
359
views
implementing Propp-Wilson's Coupling From the Past on Lozenge Tilings of a Hexagon
I'm trying to write a program (with javascript or python) that samples a random lozenge tiling of a hexagon with Propp - Wilson's coupling from the past algorithm. I'm quite clear of the framework of ...
- 8,717
6
votes
1
answer
3k
views
Mathematical expectation of minimum of k random variables with fixed sum n
We have $n$ independent identically distributed random variables $X_1$, $X_2$, ..., $X_N$, $X_i=j$ with probability $1/k$ for $j=1, 2, ... k$. Let $Y_j$ be a number of random variables $X_i$, which ...
- 8,992
1
vote
0
answers
44
views
maximum subsets of a certain type contained in difference set
Explaining my question in words doesn't really make sense. I'll define a few concepts first.
for a set $S \subseteq \mathbb{Z} $, define $||S||=\{|s| : s \in S ,\ |s|>0\}$ i.e. the set ...
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$ ...
- 86
-1
votes
2
answers
217
views
Expected number of balls left out when choosing $n$ times from $n$ balls
I am given $n$ balls. For $n$ times, I pick one of them with uniform probability and put it back after picking it.
Let $U$ be the number of balls I have never picked, so $U\in \{0,\ldots,n-1\}$. We ...
CommunityBot
- 1
2
votes
3
answers
335
views
Choosing $n$ times from $n$ objects
I am given $n$ objects and for $n$ times, I pick one of them with uniform probability and put it back after picking it.
For $k\in\{1,\ldots,n\}$ let $f_k$ denote the number of times that I have ...
CommunityBot
- 1
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$ ...
- 23k
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{...
- 60.5k
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
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....
CommunityBot
- 1
10
votes
1
answer
263
views
q-versions of the geometric distribution and their names
I'm trying to set straight various $q$-deformations of the standard geometric distribution.
The geometric distribution on $\left\{ 0,1,\ldots \right\}$ is well-known, it has
$$
\mu_1(X=j)=(1-p)p^j,\...
- 1,765
1
vote
1
answer
394
views
On rank of random $0/1$ matrices
It is known that a $0/1$ matrix picked from uniform distribution from $\{0,1\}^{n\times n}$ is non-singular with probability $1-o(1)$.
Fix an integer $t$.
Consider a random matrix formed the ...
CommunityBot
- 1
3
votes
2
answers
706
views
Birthday inequality for non-uniform distributions for fixed collision probability (random allocation, collision probability)
Question: Consider a distribution $D$, and $n$ i.i.d. random variables $X_i$, all distributed according to $D$. Let $p^D_2:=\Pr[X_1=X_2]$. What is a lower bound for $p^D_n:=\Pr[\exists i\neq j. X_i=...
CommunityBot
- 1
8
votes
1
answer
1k
views
How to generate Voronoi diagram with polygons of equal area?
I would like to generate some random set of points so that their Voronoi diagram consist of equal-area polygons. Is it possible to impose some constraints on the points in order to have the same areas ...
- 151k
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 ...
- 2,720
11
votes
0
answers
426
views
Maximizing the volume in a family of subsets of a cube
Starting from a question in probability, I arrived to the following optimization problem.
Let $I:=[0, 1],$ and let $A$ be a Lebesgue measurable subset of the $n$-dimensional cube, $A\subset I^n.$ ...
- 60.5k
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
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 \...
- 5,781
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}...
- 1,897
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 $...
- 166
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
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 ...
CommunityBot
- 1
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 ...
- 468
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 $\...
- 82.7k
2
votes
0
answers
419
views
Best possible concentration inequality in high dimensions
Let $X_1,\ldots,X_n$ be independent random variables in $\mathbb{R}^d$ with $EX_i=0$ and $||X_i||_{2}\leq 1$. What is the best known exponential upper bound for
$$P(||X_1+\cdots+X_n||_{2}>x)?$$
In ...
CommunityBot
- 1
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 ...
- 61.9k
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
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