All Questions
Tagged with binomial-coefficients pr.probability
17 questions
0
votes
2
answers
115
views
Upper bounds on quotients of binomial coefficients
Let $\gamma>1$ be a real number and let $n\in \mathbb{N}$.
Define $f\colon\mathbb{N}\to[0,1]$
$$
f(n_0) = \frac{\binom{n-n_0}{m}}{\binom{n}{m}},
$$
where
$$
m = \Big\lfloor{\frac{n}{\lceil\gamma ...
16
votes
0
answers
309
views
Randomized Pascal's triangle: What is the average of all the numbers?
This question was posted on MSE. It received some interesting responses, but no definite answer.
Let's build a variation of Pascal's triangle. We write $1$'s going down the sides, as usual. Then for ...
- 3,527
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
2
votes
1
answer
383
views
Lower bound and limit of a sum with binomial coefficients
Let
$$A_k = \sum_{i=1}^k i {3k-2i-1 \choose i-1} {2i-2 \choose k-i}$$
$$B_k = \sum_{i=1}^k i {3k-2i-2 \choose i-1} {2i-1 \choose k-i}$$
$$C_k = \sum_{i=1}^k (3k-2i-2) {3k-2i-3 \choose i-1} {2i\...
- 155
5
votes
4
answers
917
views
Limit of a sum with binomial coefficients
Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$
$$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$
$$C_k = \frac{\sum_{i=1}^k(...
- 155
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
1
vote
1
answer
237
views
Poisson-like random walk expressed as Bernoulli-like random walks (splitting scheme)
In our problem we have the transition density for $x,y\in \mathbb{Z}$ and $t\in \mathbb{N}$
$$R_{t}(x,y):=e^{-t}\frac{t^{x-y}}{(x-y)!}1_{x\geq y},$$
which is the Poisson distribution pdf. (This is ...
- 5,474
9
votes
1
answer
1k
views
Bounding the probability that two binomials are equal
Note: This question was migrated from this earlier post, where it initially appeared. Following suggestions, I moved this into its own question.
Let $B_{n,p}$ denote the usual binomial random ...
- 2,720
0
votes
1
answer
208
views
Local behavior of the Vandermonde convolution
An interesting combinatorial identity is the Vandermonde convolution identity:
$$ \sum_k {n\choose k}{m\choose s-k} = {n+m \choose s},$$
which can be proved by considering the coefficients in $(x+1)^{...
- 5,230
2
votes
1
answer
235
views
Sum of squares of middle binomial sums or 'Truncated mean' of binomial coefficients under binomial distribution
$\mu=1+\epsilon$ where $\epsilon>0$ holds.
1.Is there a good bound for $$T=\frac{\sum_{i=-\sqrt{\mu n\ln n}}^{\sqrt{\mu n\ln n}}\binom{n}{\frac n2 +i}^2}{2^n}?$$
This quantity can be ...
- 1,826
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
5
votes
3
answers
475
views
Closed form $\int_{0}^{\frac{r}{2}} {\binom{n}{p} \binom{n-p}{r-2p} 2^{r-2p}}{\binom{2n}{r}^{-1}} \ \text{d}p$
Note: This is exact copy of my Math.SE question, which I am reposting here, as despite bounty it did not receive any answers.
Let there be $n$ pairs of shoes in a box.
The the probability that from ...
- 67
3
votes
3
answers
477
views
A clean upper bound for the expectation of a function of a binomial random variable
I wonder if there is a closed-form, or clean upper bound of this quantity: $\mathbb{E}[|X/n-p|]$, where $X\sim B(n,p)$.
- 101
1
vote
1
answer
276
views
What is the expected number of missing random integers?
Consider $n$ numbers randomly generated by independent generators that can produce integers from $0$ to $n$. How many of these integers will be missing on average for large $n$? If $p_{k,n}$ is the ...
- 1,731
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
0
answers
255
views
An extrasensory perception strategy :-)
I asked this question at MSE some months ago
but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...
- 5,409
18
votes
1
answer
2k
views
How big is the sum of smallest multinomial coefficients?
Given positive integers $n$ and $d$, let $S$ indicate the list of all $d$-tuples of non-negative integers $(c_1,\ldots,c_d)$ such that $c_1+\cdots+c_d=n$. Let $v_i$ be the value of the multinomial ...
- 2,442