All Questions
Tagged with pr.probability co.combinatorics
802 questions
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 ...
- 2,137
5
votes
1
answer
194
views
Integers in Boxes Problem
Given positive integers $k$, $m$, $n$, with $m,n >> k$, suppose we have
$n$ boxes each containing $k$ randomly (uniformly) selected positive integers $x$ satisfying $1 \leq x \leq m$ (duplicates ...
- 123
5
votes
1
answer
421
views
Memory of Uniformly Random Dyck Paths
Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have $S(0)...
- 4,952
5
votes
0
answers
190
views
Number of discrete Lipschitz functions with given Lipschitz constant
Fix $T, K, N \in \mathbb Z_+$. How many distinct Lipschitz functions $f: \{0, \dots, T\} \to \mathbb Z$ are there with Lipschitz constant $K$, and supremum norm at most $N$ satisfying $f(0) = 0$?
In ...
- 6,215
5
votes
0
answers
130
views
Random process on a sequence of rolls of an $n$-sided die
Let $\ X:=X_{k\,n}\ $ be a random variable of a $n$-sided die where $\Pr(X=i)=\frac{1}{n}$ for each $i\in\{1,2,\ldots,n\},\ $ where $\ k\in\{1, 2, \ldots,n\}\ $ and $\ n\ $ are fixed. Let $t$ be a ...
- 83
5
votes
0
answers
287
views
Infinite tridiagonal matrices and a special class of totally positive sequences
Let $\Bbb{y} = \big(y_1, y_2, y_3, \dots \big)$ be an infinite sequence of positive real numbers such that following $\Bbb{N} \times \Bbb{N}$ tridiagonal matrix
\begin{equation}
T(\Bbb{y}) := \,
\...
- 2,137
5
votes
0
answers
244
views
Distribution of point knowing target in optimal matching
I am a young PhD student in statistics.
Recently, papers (Ambrosio, Stra and Trevisan; Talagrand; Ledoux to cite but a few) tackled the problem of finding the expected cost in an optimal matching, ...
- 555
5
votes
0
answers
352
views
0-1 matrix combinatorial problem
Let $M \in \{0,1\}^{n \times n}$ and let $r_i$ be its $i$-th row. Given constant $p \in (0,1/2]$, let the number of $1$s in each row be at least $p\,n$. Given constant $c \in (0,1)$, what is the ...
- 1,677
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
5
votes
0
answers
240
views
Paths in Pascal's triangle; or balanced $0-1$ initial segments
Here is a problem arising (via a tortuous path) from trying to determine the spectrum of Vershik's adic map on Pascal's triangle (a moderately well-known question: is the spectrum trivial, that is, is ...
- 4,679
5
votes
0
answers
295
views
inequality in a shape of inclusion exclusion formula
I have two inequalities to show, both of which describe some probabilities. First I know how to handle, and it follows from applying arithmetic-harmonic mean inequality:
consider 9 numbers $a_1,a_2,...
- 341
5
votes
0
answers
220
views
Operator connected with Hermite polynomials
For $n \geq 1$, define the following operator $M_n$ on the ring of all polynomials with real coefficients.
$$M_n P(x) = nP(x)^2 - x \int_0^x (P'(t))^2 \, \mathrm{d}t$$
Monomials $x^k$ are mapped to $n ...
- 617
5
votes
0
answers
215
views
Asymptotics of a Splitting Process
Consider $p(n)$ defined recursively by $p(1)=1$ and
$\displaystyle p(n)=\frac{1}{(n-1)^n}\sum_{i=1}^{n-1}\left\{\sum_{j=i}^{n-1}(-1)^{j-i}{n \choose j}{j\choose i}(n-j)^j(n-j-1)^{n-j}\right\}p(i)$.
...
- 667
5
votes
0
answers
273
views
root system generalizations of Sekiguchi-Debiard (aka Laplace-Beltrami) operators
For the root system $A_n$, taking the limit $q = t^\alpha$ and $t \to 1$, and letting $Y = (t-1) X -1$ one obtains from the Macdonald operator the so-called Sekiguchi-Debiard operator:
$$D_\alpha(X) =...
- 4,466
5
votes
0
answers
227
views
Number of times lead changes in a multi-candidate election (reference-request)
In a two candidate election where votes are distributed uniformly at random between the candidates, the probability that the lead changes when tallying the $i$-th vote is the same as the probability ...
- 51
4
votes
5
answers
492
views
Some questions concerning a random number process
Consider the following Markov process: Start with an integer $N = N_0$. Now repeatedly choose an $N_i$ uniformly at random in the range $[1...N_{i-1}]$ until $N_i = 1$ at which point one terminates ...
- 5,191
4
votes
3
answers
579
views
Average distance between numbers of the form $2^{a}3^{b}$
I want to order all numbers of the form $2^a3^b$. I need to find the average distance between a random consecutive pair.
For example, in case of a random consecutive pair $2^{n'}$ and $2^{n'+1}$, the ...
- 431
4
votes
2
answers
432
views
How to prove the sum of n squared binomial probabilities does not increase as n increases
Let $F\left( n \right) = \sum\limits_{k = 0}^n {{{\left( {C_n^k{p^k}{{\left( {1 - p} \right)}^{n - k}}} \right)}^2}} $, prove $F\left( n \right) \ge F\left( {n + 1} \right)$.
UPDATE: More general, ...
- 43
4
votes
2
answers
399
views
Generic words of given weight
Suppose you have an alphabet with countably many letters. Every letter has a particular weight (for instance, as in the game of Scrabble). There are a total of $n^2$ letters that have weight $n$.
...
- 1,329
4
votes
2
answers
307
views
Lower bounding a partition-related sum
We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\...
- 715
4
votes
2
answers
853
views
Can you explain the description of the Lovasz Local Lemma by Moser+Tardos?
The Lovász Local Lemma (or LLL) concerns itself with the probability of avoiding a collection of "bad" events A, given that the set of events is "nearly independent" (each bad event A &...
- 1,444
4
votes
1
answer
587
views
Combinatorial descriptions of the stationary distribution of a Markov chain
When I say "Markov chain" I think of a directed positively weighted (finite) graph, such that the sum of all edges going out of a vertex equals 1. Also I assume that it is aperiodic and irreducible.
...
- 406
4
votes
2
answers
1k
views
Balls-and-bins type problem
Suppose I have an n-by-n array of bins, and I want to choose k (k >= n) bins from these n^2 bins such that each row of the array has at least one bin chosen. How many ways are there of doing this?
...
- 57
4
votes
1
answer
938
views
Random projection and finite fields
Suppose we have, say, $n$ $2n$-dimensional linearly independent vectors over $\mathbb{F}_2$. We do a projection on a random $d$-dimensional subspace. We are interested in probability that images of ...
- 1,791
4
votes
6
answers
751
views
Reconstructing an ordering of a multiset from its consecutive submultisets
We have a multiset $S$ of size $t$ with $r$ distinct elements, where $t$ is much larger than $r$. We want to reconstruct an ordering $s_1, s_2, ... s_t$ of the elements of $S$ given the values of $t$ ...
- 599
4
votes
1
answer
581
views
"the" random permutation
I recently looked at Permutations on the random permutation which seems to talk about the notion of random permutuation as a notion from logic rather than probability.
The random permutation is the ...
- 22.8k
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 ...
- 471
4
votes
1
answer
322
views
Approximating binomial coefficient sum
I have the following exact sum for the expectation of an event
$$\sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \binom{(n-j)k}{m} / \binom{nk}{m}$$
which is exactly correct but I want to give an ...
- 51
4
votes
1
answer
272
views
How far do I have to go for the tail of a binomial distribution with small $p$ to be $O(1/n)$?
Let $n$ be a large integer, $p$ be a small number (say, $p=C/n$ for some constant $C \ll n$), and consider the tail of the binomial distribution $B(n,p)$, after $T$:
$$
\delta = \sum_{s=T}^{n} p^s (1-...
- 267
4
votes
3
answers
439
views
Probability estimates for "beans & boxes"
From a discussion with some friends, this apparently easy problem has come out; I decided to post it here, because I believe that the answer is non-trivial and the maths beneath interesting. Partial ...
- 418
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} \...
- 359
4
votes
3
answers
269
views
Existence of (near) equidistant codewords
My question is originally related to coding theory, but fairly easy to state in pure combinatorial way.
Fix $k\in\mathbb{N}$, $\beta\in(0,1)$ and consider the binary cube $\Sigma_n = \{0,1\}^n$ ...
- 1,096
4
votes
2
answers
261
views
Probability question about random shuffling of piles of rocks
I have $k$ piles of rocks placed on a circle so that every pile has exactly two neighboring piles. We know that initially the piles have $x_1,\dots,x_k$ rocks in each respectively. A monkey plays the ...
- 41
4
votes
1
answer
669
views
Number of independent sets of a random tree
Let $T_n$ be a random tree on $n$ labelled vertices chosen equiprobably among all $n^{n - 2}$ trees, and $I(T)$ be the number of distinct independent sets of a tree $T$. I'm interested in the average ...
- 5,590
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,\...
- 736
4
votes
1
answer
1k
views
Probabilty of two permutations having common elements?
What is the probability of two permutations on set X of size m (i.e. |X|=m) having at least n points of intersection? By this I mean that if two permutations, which I'll call g(x) and h(x), map a ...
- 55
4
votes
2
answers
882
views
Distribution of a maximum
I am reposting a question on math.stackexchange which did not recieve good questions.
The orginal questio is at https://math.stackexchange.com/questions/73091/distribution-of-a-maximum.
Randomly ...
- 177
4
votes
2
answers
1k
views
expected values over binomial distributions
In some works of economics/risk analysis etc., I have seen situations where people take the expected value of a function (such as a utility function/cost function) over a binomial distribution:
$$F(n)...
- 7,320
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)/...
- 128k
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 $...
- 253
4
votes
1
answer
275
views
Probability of a subset of Bernoulli's being all 1's
Suppose we have $n$ iid Bernoulli's $X_1,\ldots,X_n$ with mean $p$, and a family $\mathcal{F}$ of subsets of $[n]$. The question is how to lower bound the probability that there is a set in the family ...
- 408
4
votes
1
answer
249
views
Colored arrangements of circles on the two sphere
Let me define a degree $n$ colored arrangement of circles on $S^2$ to be a collection $\mathcal{C}$ of $n$ disjoint, smoothly embedded circles $C_1,\dotsc, C_n\subset S^2$ together with a ...
- 34.7k
4
votes
1
answer
2k
views
Square of Binomial Coefficient
Background
I'm modeling Genetic Algorithm(GA) with Markov chains and deriving the expression for the expectation of the first hittig time in the MC with 1 absorbing state and $l-1$ transient states. ...
- 355
4
votes
1
answer
262
views
What is the number of finite Dynkin systems?
(This is a spin-off of Determine the minimal elements of a Dynkin system generated by a finite set of finite sets)
Let $\Omega$ be a finite set. A Dynkin system on $\Omega$ is a subset of the power ...
- 5,822
4
votes
1
answer
115
views
What is the probability of an empty convex $k$-gon among many given points?
Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points.
For a big number $n$ of randomly distributed ...
- 13.4k
4
votes
1
answer
239
views
$Pr(A>B)$, where $A$ and $B$ are sum of Bernoullies
Let $X= x_1 + x_2 + \ldots + x_m$, $Y=y_1 + y_2 + y_3 + \ldots + y_n$, and $Y' = y'_1 + y'_2 + \ldots + y'_n$, where
Each $x_i$ is a Bernoulli variable which takes value $1$ with probability $p_i>...
- 169
4
votes
3
answers
504
views
Expected number of crossings of the diagonal of a lattice path?
If we uniformly choose a lattice path from $(0,0)$ to $(n, n)$ (i.e. at each step we can move from $(x,y)$ to $(x+1,y)$ or $(x,y+1)$), what is the expected number of times that the path crosses the ...
- 41
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
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
4
votes
2
answers
356
views
Ruin time for a two-input "risk only" slot machine
Imagine a "risk only" slot machine that takes 'coins' corresponding to some real number fraction of a dollar $p$, returns the coin with probability $p$, and eats the coin with probability $(1-p)$. ...
- 41