All Questions
Tagged with pr.probability co.combinatorics
802 questions
2
votes
0
answers
86
views
Bounds on number of distinct substrings
I have a table with $r$ rows of length $\ell$, with each cell containing a letter from an alphabet $A$ of length $a$. I'm trying to determine the expected number of distinct strings of length $k$ ...
- 21
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 ...
- 2,288
2
votes
0
answers
83
views
Asymptotic results in unbalanced left $d$-regular expander graphs
Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, ...
- 409
2
votes
0
answers
143
views
Arctic Circle Theorems and the Wave Equation
I've seen the following remark in a number of papers but don't know what to make of it. In this paper by Cohn, Elkies and Propp, it is mentioned that the normalized average Height function $\mathcal{H}...
- 4,952
2
votes
0
answers
186
views
Finding the number of leaf nodes at specific level of a random tree
Given a uniform recursive tree (URT) of size $N$ rooted at one node whereby the tree is generated as follows:
Starting with a root node, at each iteration, a new node is connected to one of the ...
- 355
2
votes
0
answers
979
views
How to calculate/approximate expectation of function of a binomial random variable?
Hi,
I am stuck at following problem in my research.
Suppose that $M=m$ is a random variable with binomial distribution with parameters $n,p$. The constants $r$ and $\gamma$ are greater than zero. $\...
- 21
2
votes
0
answers
351
views
Distribution of transformed multinomial variable?
Suppose we have a uniform multinomial distribution over $2^d$ outcomes. Multinomial coefficients give distribution of vector valued variable $v$ where $v$ is the vector of observed counts.
Is there a ...
- 2,252
2
votes
0
answers
530
views
About generalization of stirling numbers of the second kind
Hello,
The Stirling numbers of the second kind count how many ways can a set of $k$ elements be partitioned into $n$ non-empty classes, with $k=n,n+1,\dots$.
My question is: Is there a ...
1
vote
2
answers
203
views
Moments of a combinatorial ensemble of random variables
Suppose $X_1,\dots,X_n$ are jointly distributed random variables such that the random $n$-tuple $(X_1,\dots,X_n)$ is uniformly distributed on the set of $n$-tuples of nonnegative integers summing to $...
- 19.7k
1
vote
2
answers
306
views
Joint moments like $\tau(XYXYXY)$ in terms of individual moments of free variables $X,Y$
Terry Tao RMT book has the following formula for joint moment of freely independent random variables $X,Y$ in Section 2.5
$$\tau(XYXY)=\tau(X)^2\tau(Y^2)+\tau(X^2)\tau(Y)^2-\tau(X)^2\tau(Y)^2$$
...
- 2,252
1
vote
2
answers
163
views
Coupling a binomial - parity conditioning
If I have a binomial $X \sim B(n,p)$, and another binomial $X' \sim B(n,p)$ conditioned on $X'$ being of even parity. Is it true that there always exists a coupling for $(X,X')$ with $|X-X'| \le 1$? (...
- 435
1
vote
2
answers
535
views
Randomized algorithm?
The problem is as follows. Given a set $S$ of natural numbers of size $n$ where each $x_i \in S$ is from the set $[n^2]$. Elements of $S$ are not necessarily pairwise different, i.e., there can be ...
- 113
1
vote
2
answers
242
views
Number of required trials to sample all possible states of a 'd'-sided loaded die
Let's say that I have a loaded $d$-sided die where the relative probabilities for the die landing on a particular side, $(p_1, ..., p_d)$, are known. How many times must I roll the die to, on average,...
- 309
1
vote
1
answer
170
views
Mean of probability distribution
I have a probability distribution defined by the following density function:
$f(k,j,n,m)=\frac{(m n)! \mathcal{S}_k^{(j)}}{(m n)^k (m n-j)!}$ (With $\mathcal{S}_k^{(j)}$ being the Stirling number of ...
- 47
1
vote
2
answers
2k
views
Proving a random bipartite graph contains a perfect matching
I have the following problem
consider a random bipartite with vertex classes $A$ and $B$ of size $|A|=|B|=\mathrm{log}^{2}(n)$ graph in which every possible edge is chosen independently with ...
- 903
1
vote
1
answer
783
views
Probability of n k-sided dice showing exactly m different faces
I found the following closed form solution for the abovementioned problem:
$${1\over k^n}\cdot{k!\over (k-m)!}\cdot{\{{n\over m}\}}$$ with ${\{{n\over m}\}}$ being the Stirling Number of the second ...
- 5,935
1
vote
1
answer
318
views
How to calculate this limit (if exist)?
I have just asked the calculation of the following summation see here $$S(a,b,m,n_1,n_2)=\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k}, $$
which is motivated by the calculation of the ...
- 57
1
vote
2
answers
302
views
Counting permutations defined by a simple process
Consider $n$ labeled balls, $k$ of which are red and $(n-k)$ blue. Given a permutation of these balls, we tick $n-1$ times. For the $i$-th tick, if the $i$-th ball in the permutation is red, then it ...
- 155
1
vote
1
answer
141
views
Expectation of maximum of all period lengths of functions $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$
This is based on an older question.
For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ and ''starting value'' $...
- 48.9k
1
vote
1
answer
154
views
Is the Krawtchouk ensemble a determinantal process?
The Krawtchouk ensemble is defined by a weight: $w(x) = \binom{K}{x}p^x q^{K-x} $ and in fact it comes from a conditioned random walk on $\mathbb{Z}^N$. It is a probability measure on the set $\{ 0, ...
- 22.8k
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 ...
- 1,769
1
vote
1
answer
363
views
limit and combinatorics
Given $x \in (0,\frac{1}{2})$ and $y \in (0,\frac{1}{2}]$, what is the value of the following limit:
$\lim_{n\rightarrow \infty}\sum_{k=0}^{n}{n \choose k}|x^{n-k}(1-x)^{k}-y^{n-k}(1-y)^{k}|?$
When $...
1
vote
1
answer
1k
views
Hamming distance distribution induced by binary hypercube
The following problem arises in a particular machine learning problem:
Assume that we have $n$ independent Bernoulli random variables with parameters $p_i$, e.g. $n=5$ and the $p$ vector is $(0.2, 0....
- 13
1
vote
1
answer
1k
views
Average Hamming distance between strings after some number of random substitutions in a population of initially identical elements
Let's say I have a set $S$, $(s_1, ..., s_i, ..., s_P) \in S$, of $P$ identical strings over a $k$-letter alphabet, each of length $|s_i| = L$. With uniform random probability across all strings in $...
- 309
1
vote
1
answer
187
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 ...
- 11
1
vote
1
answer
268
views
Entropy upper bound for the union of uniform distributions over union-closed families
The following question is motivated by the recent breakthrough result by Justin Gilmer on the union-closed sets (aka Frankl) conjecture.
Let $\mathcal{F}\subseteq\mathcal{P}(\mathbb{N})$ be a finite, ...
- 282
1
vote
1
answer
173
views
Could you provide some TSP examples from real world to test a new algorithm?
It's well known that to find a hamilton cycle is NPC, while TSP is NPH.
But it seems that for majority of graphs (density of edge > 0.1, order > 100) there is a fast algorithm to find different ...
- 175
1
vote
1
answer
519
views
How typical are integer isometries on a hypercube? Littlewood-Offord problem for Bernoulli Gram matrices
Let $m\geq 3$ be fixed and $n\to\infty$. Consider $v=(v_j)_{j\leq m}$ with $v_1,\ldots,v_m\in \{-1,+1\}^n$. Let:
$N_I(v)$ be the number of sequences $u_1,\ldots,u_m\in \{-1,+1\}^n$ isometric to $v$ ...
- 175
1
vote
1
answer
638
views
Threshold for perfect Matchings in Bipartite graph
Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$.
I know one way to prove the threshold of a perfect matching is ...
- 903
1
vote
1
answer
269
views
A problem in symbolic dynamics
I got a fun problem.
Define the alphabet $\mathcal{A}=\{0,1,2\}$ and the set $\mathcal{A}^{\leq n}=\{ x_1x_2\ldots x_n: x_i\in \mathcal{A}\}$ of words of length $n,$ for each $n\in\mathbb{N}.$
...
- 1,805
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 ...
- 313
1
vote
2
answers
276
views
What is the probability for sequence of lenght L in subset of [n]
I am trying to calculate the probability that i'll have L length sequence in a random subset of [n] when the subset size is k. for example, if n=5, k=4 and L=2 I'll have the below subsets: {2,3,4,5}, {...
- 11
1
vote
3
answers
501
views
Operator probability in a RPN string
Consider the set $S_n$ of all strings of length $n$ ($n$ integer, $n \geq 3$)
representing an expression in RPN
( http://en.wikipedia.org/wiki/Reverse_Polish_notation. )
Assumptions (to simplify):
...
- 31
1
vote
3
answers
312
views
Chance of something being fixed [closed]
I'm fixing a software defect that occurs 1 in n test runs. If I want to know that the probability of it being fixed is >= p for some 0 <= p < 1, how many times, m, do I need to run the test ...
- 43
1
vote
1
answer
107
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
1
vote
1
answer
75
views
Probability of correctly guessing the maximum event probability of a multinomial distribution
I have a sample from multinomial distribution with $n$ trials, and $k=3$ options. I know that one of the event probabilities $p_i$ is larger than the two others (who are equal). I'm trying to guess ...
- 267
1
vote
1
answer
119
views
Does exponential degree distribution entail Log-normal distance distribution in large complex graphs?
We've been exploring the graph structure of a large genealogical data base (WikiTree) of which main connected component contains about 23 million nodes. The graph edges are defined by any direct ...
1
vote
1
answer
207
views
Expectation of the sum of the squares of the cardinal of an inverse function
I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as:
$$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$
where $\oplus$ is the bitwise XOR.
...
- 167
1
vote
1
answer
106
views
Almost-parallel corners of the hypercube in high dimensions
Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...
- 435
1
vote
3
answers
339
views
Coupon collector targeting a collection among many
I am interested in the following problem:
We are given a universe $U$ of $n$ coupons, partitioned into $k$ collections, $C_1,\dots C_k$.
At each time step $t$, a coupon $X_t$ is selected uniformly at ...
- 111
1
vote
1
answer
338
views
Polynomial form/Fourier transform of rational function over finite affine space
I am certainly going to make a mess of any serious algebraic terminology, so bear with me as I present my problem arising from a probability problem.
Consider the space of sequences of $n$ zero-one ...
- 526
1
vote
1
answer
265
views
Probability a near universal hash function $ax \bmod p \bmod m$ produces an output from inputs equal modulo $m$
For one of the near universal hash functions $f(x) = ax \bmod p \bmod m$ where $p$ is prime and $m < p, m>1$ and $x$ ranges over $1 \dots p-1$ , what is the probability that given $x_r \in \{ x |...
- 23
1
vote
1
answer
107
views
Concentration of maxima of a random polynomial with Rademacher coefficients
Let $X_1,\ldots, X_n$ be independent Rademacher random variables (i.e. $\mathbb{P}(X_i=\pm 1)=1/2$). Consider the random polynomial $$P_{n}(t)=c+X_{1}t+X_2t^2+\cdots+X_{n}t^n.$$
Is it well known how ...
- 2,288
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 ...
- 57
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 ...
- 1,677
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, \...
- 553
1
vote
1
answer
976
views
Concentration of the load of the maximally loaded bin ($m$ balls $n$ bins) with nonuniform bin probabilities
There is a common argument used when investigating the concentration of the maximally loaded bin (say $X$ is the maximum load) when $m$ balls are thrown into $n$ bins under the uniform distribution. I ...
- 10.4k
1
vote
1
answer
114
views
Probability for a group of stones to live on an infinite Go board
Suppose on an infinite two dimensional Go board the tengen is occupied by a black stone, and every other grid point is occupied by a black stone, or a white stone, or nothing, with probability 1/3 ...
- 5,169
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
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