All Questions
199
questions
1
vote
0
answers
47
views
Find the number of lattice paths weakly under a slope $y = \mu x$
How many lattice paths are there from an arbitrary point $(a,b)$ to another point $(c,d)$ that stay weakly (i.e. it can touch the line) under a slope of the form $y = \mu x$, with $\mu \in \mathbb{N}$?...
0
votes
0
answers
34
views
Probability involving identical objects. I am not able to understand how the Ncr formula is being applied below for counting identical objects.
Question: A bag contains 5 identical red coins, 6 identical yellow coins and 8 identical blue coins. If 3 coins are picked up randomly from the bag, what is the probability that there is at least one ...
2
votes
2
answers
64
views
binomial distribution but sometimes the last outcome doesn't matter
Here's the motivation for my question: I'm designing an RPG. To simplify as much as possible, lets say my enemy has $h = 4$ HP and I deal $a = 1$ damage with every attack.
However, there's also a $p$ ...
4
votes
3
answers
70
views
$(1-x)^{n+a} \sum_{j=0}^\infty \binom{n+j-1}{j}\binom{n+j}{a} x^j = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j$
Let $n$ and $a$ be natural numbers. How to prove the following for $x \in [0, 1)$?
$$
(1-x)^{n+a} \sum_{j=0}^\infty \binom{n+j-1}{j}\binom{n+j}{a} x^j = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j
$$...
0
votes
2
answers
73
views
Lower Bound on the ratio of binomial coefficients
Let $k,n,m$ be integers such that $k>n>m$. I am interested in providing a tight lowerbound on
$$
A(k,n,m)=\frac{\binom{k-m}{n-m}}{\binom{k}{n}}
$$
This term arises in a probability problem that ...
4
votes
1
answer
78
views
Identity regarding the sum of products of binomial coefficients.
Consider the following toy problem
Person A and Person B have $n$ and $n+1$ fair coins respectively. If they both flip all their coins at the same time, what is the probability person B has more ...
0
votes
1
answer
34
views
How to Derive the Binomial Coefficient Upper Bound and Final Inequality in "Scheduling Multithreaded Computations by Work Stealing"?
In the paper Scheduling Multithreaded Computations by Work Stealing under the section "Atomic accesses and the recycling game", it mentions the binomial coefficient approximation:
$$ \binom{...
0
votes
1
answer
30
views
A probability question over multiple questions test.
I was wondering about this problem: say I have to take a test made of $31$ questions chosen among a database of $140$ questions total.
Those questions are open questions (that is, not multiple choice ...
4
votes
2
answers
187
views
Combinations of indistinguishable marbles
Let's consider this problem:
A bag contains 5 black marbles and 6 white ones. Marbles of the same color are indistinguishable from each other. If I draw two marbles, what is the probability they have ...
1
vote
1
answer
97
views
Why isn't adding the ways to achieve every mutually exclusive outcome giving me the denominator in the birthday problem for four people?
Why isn't adding the ways to achieve every mutually exclusive outcome giving me the denominator in the birthday problem for four people?
$$\binom{4}{2} \cdot 365 \cdot 364 +\binom{4}{3} \cdot 365 \...
4
votes
1
answer
102
views
Gaussian approximation of collision time
In this answer there is a claim that
$$\frac{n!}{(n-k)! n^k} \approx e^{-\frac{k^2}{2n}} \tag{1}$$
which is then used to approximate the sum over $k=1,\ldots, n$ via
$$\sum_{k=1}^n \frac{n!}{(n-k)! n^...
0
votes
1
answer
60
views
Why do Binomial Coefficients work for ordering items?
I'm working on a question from Harvard's Stat 110 course.
The question is the following:
3(a) How many paths are there from the point (0, 0) to the point (110, 111) in
the plane such that each step ...
0
votes
2
answers
143
views
How do I calculate the probability of reaching sum $S$ by adding the results of an arbitrary number of rolls of an $n$-sided die?
Suppose we have a fair $n$-sided die, with faces labeled from 1 to $n$ and an equal probability of rolling any available number. Further suppose that we pick a sum $S$ that we wish to reach by rolling ...
5
votes
3
answers
376
views
Expected Maximum Value of 10 Randomly Selected Balls from an Urn
There are $20$ balls in an urn labeled from $1$ to $20$.
You randomly pick $10$ balls out of this urn. What is the expected maximum value of the $10$ balls you picked out?
I was able to solve the ...
4
votes
2
answers
316
views
Prove $\sum_{k=i}^{n} {k-1 \choose i-1} p^i (1-p)^{k-i} = \sum_{k=i}^{n} {n \choose k} p^k (1-p)^{n-k}$
Prove that the following two summations are equal for any positive integers $i\leq n$, and any real number $p$ between $0$ and $1$:
$$
\sum_{k=i}^{n} {k-1 \choose i-1} p^i (1-p)^{k-i} = \sum_{k=i}^{n} ...