If $m$ balls are thrown at random into $n$ bins, what is the chance that two balls will be in the same bin?
9
votes
0answers
223 views
Hyper Birthday Paradox?
There are $N$ buckets.
Each second we add one new ball to a random bucket - so at $t=k$, there are a total of $k$ balls collectively in the buckets.
At $t=1$, we expect that at least one bucket ...
7
votes
2answers
68 views
Find: The expected number of urns that are empty
A total of $n$ balls, numbered $1$ through $n$, are put into $n$ urns, also numbered $1$ through $n$ in such a way that ball $i$ is equally likely to go into any of the
urns $1, 2, . . . , i$. Find ...
7
votes
5answers
195 views
Probability that all bins contain strictly more than one ball?
Here's the problem I'm working on:
Given that I'm distributing $N$ balls into $K$ bins, what is the probability that all bins contain at least two (strictly more than 1) balls? This seems like a very ...
7
votes
1answer
153 views
Repeatedly Toss Balls into Bins
$n$ balls are randomly tossed into $m$ bins, each bin can hold $k$ balls. If a ball is tossed into a full bin (already has $k$ balls in it), it can be tossed repeatedly and randomly into the $m$ bins ...
5
votes
1answer
763 views
If n balls are thrown into k bins, what is the probability that every bin gets at least one ball?
If $n$ balls are thrown into $k$ bins (uniformly at random and independently), what is the probability that every bin gets at least one ball? i.e. If we write $X$ for the number of empty bins, what ...
5
votes
4answers
74 views
$n$ balls into $n+1$ urns (with one special urn)
Assume that there are $n$ balls numbered from $1,2,\ldots,n$ and $n+1$ urns, numbered as $0,1,\ldots,n$
Throw each ball randomly into one of $n$ urns: urn 1, ...
5
votes
1answer
151 views
Yet another balls and bins problem
If $p_n$ denote the probability that when $n$ balls are randomly put in $n$ bins then there is at least one bin with exactly one ball. Is there a simple (involving only little computation) reason for ...
4
votes
3answers
2k views
How can I solve bins-and-balls problems?
Below is the problem that I wanted to solve
When there are $m$ balls and $n$ bins, balls are thrown into bins where each ball is thrown into a bin uniformly at random. What is the expected number ...
4
votes
1answer
149 views
Probability - Balls and Buckets; variance question
I've been working on this problem for a while and its giving me no end of trouble! The question is this: Suppose we have 2k buckets, numbered 1 through 2k. We throw x black balls and y white balls, at ...
3
votes
1answer
77 views
what is the expected number of days in year in which exactly k people in a group of n people have been born?
there is a group of n people and we must find the average number of days that in each of them exactly k people are born (k and n are given).
This question assumes that a year has 365 days, and each ...
3
votes
2answers
68 views
How many boxes will be empty?
$150$ balls randomly put into $100$ boxes, each ball could be put into any of these 100 boxes with same probability, after that, on average, how many boxes will be empty?
No calculator. Choose one of ...
3
votes
1answer
126 views
Maximum load of a bin in the $n$ balls with weights into $m$ bins problem
$n$ balls, each with a weight $p_i$, are thrown into $m$ bins. Each bin is chosen with uniform probability.
Prove or disprove that the expected value of the maximum load among the loads of bins is ...
3
votes
1answer
27 views
Probability $k$ bins are non-empty
The following problem arises in the analysis of Bloom filters.
Consider $m$ bins and $N=nk$ balls placed uniformly and independently at random into the bins. A query chooses $k$ bins uniformly and ...
2
votes
1answer
273 views
In how many ways can 2 balls be arranged in 5 boxes so that one box does not contain more than one ball?
What is the number of ways 2 balls can be arranged in 5 boxes? The boxes may not contain more than 1 ball. The balls are of different colors.
I forgot to mention the order of the boxes are important. ...
2
votes
1answer
106 views
Amount of distinct numbers in a sequence of $k$ random numbers in range $[1,\ldots,n]$
Let $D$ be the amount of distinct numbers in a sequence of $k$ random numbers in range $[1,\ldots,n]$ (n>k).
I want to show that:
$D=\Omega(k)$ with exponential high probability. I'm interested in the ...
1
vote
2answers
140 views
Probability of having $k$ empty urns after putting $n$ balls into $n$ urns
Assume that there are $n$ balls (numbered from $1$ to $n$) and $n$ urns (numbered from $1$ to $n$). At the beginning no ball is placed in any urn. Balls are randomly thrown into urns: Each ball is ...
1
vote
3answers
58 views
n+1 balls put into n bins. Double count?
Question:
n+1 balls are put into n bins. What is the probability that all of the bins are not empty (contain 1 ball at least)?
What I did:
Choose n balls from the n+1 ${n+1 \choose n}$, order them ...
1
vote
2answers
70 views
Probability of red ball i before any black ball
Assume we have $r$ red balls and $b$ black balls in a box and we remove one ball at a time without replacement. Red balls are labeled from $1$ to $r$. We want to calculate the probability a particular ...
1
vote
1answer
104 views
Arrangements with No Two Vowels Consecutive
In general we state that there are ${r-wn - (n-1) \choose (n-1)}$ ways to distribute r identical balls in n distinct boxes with at least w balls in each box. Considering this, how many ways are there ...
1
vote
1answer
61 views
$k$ balls into $n$ bins — Number of occupied bins
Suppose we throw $k$ balls into $n$ bins. Assume that $\log^2n\le k\le n$.
Is there a high probability bound (preferably exponential) on the number of occupied (i.e., non-empty) bins?
Something ...
1
vote
1answer
57 views
How does this Markov process involving balls and bins behave?
I have some set $S_1,\ldots,S_k$ ($k \geq 3$) of bins, each initially with $N_0(S_i)$ balls ($N_t(S_i)$ denotes the number of balls in $S_i$ at time $t$). A bin can contain a negative number of balls. ...
0
votes
1answer
109 views
Bins in balls where bin size grows exponentially
I have $k$ bins. The first bin can fit $1$ ball. Each subsequent bin can fit two times more balls than the previous one. In other words, the $i$th bin can fit $2^i$ balls.
We randomly assign $U = ...
0
votes
2answers
147 views
Throwing $k$ balls into $n$ bins.
I have the following question:
Throwing $k$ balls into $n$ bins. What is the probability that exactly $z$ bins are not empty?
I thought about something like:
$$\Pr(z)=\frac{n! z^{k-z}}{n^k ...
0
votes
1answer
102 views
Expected value for a function concerning a balls and bins problem
I'm optimizing a hash function mapping $M$ items into $N$ bins and I need a criterion for evaluating the quality of the mapping. Denoting the number of items put into bin $i$ by $x_i$, an ideal ...
0
votes
0answers
18 views
The distribution of balls in bins as a function of the number of balls [duplicate]
If I toss $m$ balls into $N$ bins, as a function of $m$, what distribution of balls and bins should I expect as a function of $m$? What would be the mean largest number of balls in a particular bin?
0
votes
0answers
110 views
Balls and Bins problem with constraint
Assume we have $B$ black balls and $R$ red balls, where $R+B$ is a multiple of 4. We want to distribute the balls in $\frac{R+B}{4}$ bins such that each bin has at least 1 red ball and at least 1 ...
0
votes
0answers
36 views
Poisson Distribution?
There exists 1000 boxes. These boxes are randomly filled with balls. How many balls are required in order that only 1 in 100 boxes are left empty?
This sounds like a Poisson distribution problem to ...
0
votes
0answers
48 views
balls and bins: the first time when max-loaded is less than twice min-loaded
We have $n$ bins, in each step we throw a ball in a bin chosen uniformly and independently from the $n$ bins we have.
We repeat the process $k$ times. Let $B_k$ be the number of balls in ...
0
votes
0answers
52 views
Simulating the balls and bins problem in Mathematica (or similar)?
The 'balls and bins' problem
Distribute $n$ balls into $d$ bins in a way which minimises the difference between the highest and lowest loaded bins.
Reasoning for performing simulation
I have some ...
0
votes
0answers
56 views
What is the chance that a box is empty after randomly filling it with balls? [duplicate]
Possible Duplicate:
If n balls are thrown into k bins, what is the probability that every bin gets at least one ball?
Suppose that I randomly distribute $n$ balls into $m$ boxes. What is ...
