It's about distribution or arrangement of $m$ distinct or identical balls into $n$ distinct or identical bins with all possible combinations.

learn more… | top users | synonyms

35
votes
3answers
6k views

Making 400k random choices from 400k samples seems to always end up with 63% distinct choices, why?

I have a very simple simulation program, the sequence is: Create an array of 400k elements Use a PRNG to pick an index, and mark the element (repeat 400k times) Count number of marked elements. An ...
11
votes
3answers
915 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 ...
11
votes
1answer
403 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 ...
10
votes
4answers
232 views

Expected value of size of subset

Given a set $S$ such that $|S|=n$, A random item is chosen randomly from $S$, and being appended to a new set $T$. This process is being repeated $n$ times (with repetition), what is the expected ...
9
votes
1answer
292 views

How many expected people needed until 3 share a birthday?

I asked a somewhat related question recently and then became interested in this one: how many people are required, on average, until 3 share a birthday? More generally, if we have $M$ bins, what is ...
9
votes
4answers
1k 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 ...
8
votes
3answers
2k views

Expected max load with $n$ balls in $n$ bins?

If you throw $n$ balls into $n$ bins uniformly and independently at random, let $X$ be the number of balls in the bin with the largest number of balls in it. Is there an elementary way to ...
8
votes
2answers
817 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 ...
8
votes
1answer
376 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 ...
7
votes
4answers
6k 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 ...
6
votes
2answers
306 views

Are “Balls in Bins” and “Stars and bars” the same?

I want to know that if Balls in Bins and Stars n Bars problems in combinatorics are similar? Can we reduce one into other? How? How can they be mapped to each other?
6
votes
1answer
651 views

$m$ balls into $n$ urns

Assume that there are $m$ balls and $n$ urns with $m\gt n$. Each ball is thrown randomly and uniformly into urns. That is, each ball goes into each urn with probability $\dfrac1n$. What is the ...
6
votes
3answers
443 views

Second pair of matching birthdays

The "birthday problem" is well-known and well-studied. There are many versions of it and many questions one might ask. For example, "how many people do we need in a room to obtain at least a 50% ...
6
votes
1answer
276 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 ...
5
votes
3answers
6k 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 ...
5
votes
1answer
1k views

$n$ balls are thrown randomly into $k$ bins - how many are empty?

A large number of variants of this question were already asked here, including these - one, two, which are close, but none seem to answer my question. Assume that $n$ balls are thrown randomly and ...
5
votes
1answer
298 views

How many ways can you put 8 red, 6 green and 7 blue balls in 4 indistinguishable bins?

Assume all balls with the same color are indistinguishable. The order in which balls are put in a bin does not matter. No bins are allowed to have the same distribution of balls! For example, this ...
5
votes
1answer
348 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 ...
5
votes
1answer
184 views

Probability of drawing a run of a specific color from an urn with two colors of balls

I was sent a puzzle involving an urn with 128 white balls and 288 black. If the balls are drawn without replacement until the urn is exhausted, what is the probability that a sequence of 10 or more ...
5
votes
4answers
295 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
0answers
34 views

More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
4
votes
2answers
269 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 ...
4
votes
1answer
325 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 ...
4
votes
0answers
82 views

Probability of having at least $j$ collisions when tossing $m$ balls into $n$ bins

Suppose that we throw $m$ balls into $n$ bins uniformly and independantly at random. We consider collisions as distinct unordered pairs, e.g., if 3 balls are tossed in one bin, we count 3 collisions. ...
3
votes
3answers
212 views

Use the inclusion-exclusion principle to determine

Use the inclusion-exclusion principle to determine : (a) the number of ways there are to choose nineteen balls (identical apart from their colour) from a pile of red, blue, yellow and green balls if ...
3
votes
1answer
792 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. ...
3
votes
4answers
195 views

Application of Pigeon-Hole Principle to balls in bins.

Given $n$ balls placed in $m$ boxes, prove that if $n < \frac{m(m-1)}{2}$ then at least two boxes have same number of balls in them.
3
votes
1answer
113 views

Expected value for the number of tries to draw the black ball from the bag

We have a bag with $4$ white balls and $1$ black ball. We are drawing balls without replacement. Find expected value for the number of tries to draw the black ball from the bag. Progress. The ...
3
votes
1answer
66 views

Expected value of trials to obtain a red ball in a box of white balls.

I have a problem that involves a box containg N balls, one of which is red and the rest of which (N-1) are white. The question involves finding the expected value and variance for the number of trials ...
3
votes
1answer
200 views

Number of ways to place $n$ balls in $k$ bins where just the first $r$ bins have less than $m$ balls

How many ways are there to distribute $n$ balls into $k$ bins where the first $r$ bins have less than $m$ balls (each) and the rest of the bins have more than $m$ (each)? Given this solution for ...
3
votes
1answer
187 views

In how many ways I can put $2$ red balls and $3$ green balls in $5$ boxes?

I have $5(N)$ boxes and some balls. Here's the description: Red Balls $= 2 (k1 = 2)$ Green Balls $= 3 (k2 = 3)$ ...
3
votes
1answer
376 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 ...
3
votes
1answer
66 views

Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
3
votes
1answer
162 views

Ways to distribute $25$ distinct balls to $40$ bins with constraints

How many ways there are to distribute $25$ distinct balls to $40$ bins such that: At least one bin will have more than one ball. One and only one bin (not predetermined) will hold exactly ...
3
votes
1answer
112 views

Expected total number of balls in all bins after throwing balls uniformly randomly to bins that have limited capacity

Consider throwing $n$ balls uniformly randomly to $L$ bins. Each bin has capacity $G$, meaning that if a ball is threw to a bin that already has $G$ balls in it, the ball is discarded. Is that ...
3
votes
0answers
88 views

Maximum bin load for $\alpha n$ balls into $n$ bins

In a paper I am reading the author writes: A standard result concerning balls and bins shows that if we throw at least $\alpha n$ balls into at most $n$ bins, then the maximum bin load is ...
3
votes
0answers
118 views

$m$ balls into $n$ already occupied urns

Assume that there are n urns, $k\in\{1,...,n-1\}$ of which have already at least one ball. $m$ new balls will be thrown into urns. Each of the $m$ balls is thrown randomly and uniformly into $n$ urns. ...
2
votes
3answers
694 views

We throwing $m$ balls to $n$ cells…

We throwing $m$ balls to $n$ cells randomly... At each cell can be more then one ball, or (of course) it can still empty. What is the expectation of the empty cells? I'd like to get any help! Thank ...
2
votes
3answers
223 views

Find the probability that the $4$th ball removed from the box is white

A box has $10$ balls, $6$ of which are black and $4$ of which are white. $3$ balls are removed from the box, their color unnoted. Find the probability that a fourth ball removed from the box is ...
2
votes
1answer
642 views

Balls and bins conditioned on the number of non-empty bins

The expected number of occupied bins in the standard balls and bins problem (with $m$ balls into $N$ bins) is $N\left( {1 - {{\left( {1 - \frac{1}{N}} \right)}^m}} \right)$. How do I compute this ...
2
votes
3answers
252 views

Number of ways of distributing balls into boxes

I know that the formula for counting the number of ways in which $n$ indistinguishable balls can be distributed into $k$ distinguishable boxes is $$\binom{n + k -1}{n}$$ but I am having a hard time ...
2
votes
1answer
106 views

Is there a fast, reasonably accurate estimator for multinomial PDF?

I am working on a balls in boxes kind of problem, where the probability of a ball ending up in a certain box varies by box, that is, each box has some probability P of getting any ball, all together ...
2
votes
2answers
139 views

A Question on distribution numbers

This is a question from the book Combinatorics -a problem oriented approach which states: Q.1 Find the no. of distributions of a set of distinct balls into a set of distinct boxes, if no boxes can ...
2
votes
2answers
164 views

Dividing $n+2$ balls to $n$ bins such that no bin is empty

We have $n+2$ balls and $n$ bins, in how many ways we can divide the balls between the bins such that there's no empty bin? (Bins are different and numbered) My attempt: for the first bin we have ...
2
votes
2answers
139 views

probability that given n balls and 60 urns no urn has more than 1 ball

A carnival game is set up so that a ball put into play has an equal chance of landing in any of 60 different slots. The operator of the game allows you to choose any number of balls and put them all ...
2
votes
2answers
423 views

Probability of number of unique numbers in $37$ Roulette Wheel spins.

I was wondering if someone could help me answer the following question: Calculate the probability that in $37 $ consecutive spins of a roulette wheel (using an European Roulette wheel) you will have ...
2
votes
2answers
1k 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 ...
2
votes
2answers
234 views

If I randomly throw 10,000 balls to 4,000 buckets, what is the probability that at least one bucket contains more than 10 balls?

If I randomly throw 10,000 balls to 4,000 buckets, what is the probability that at least one bucket contains more than 10 balls? I don't know how to even approach this. A rough number is also ...
2
votes
1answer
126 views

Expectation time for at least 2 balls in each bin

Given $N$ bins and an unlimited number of balls, to be assigned one ball per time unit to a uniformly random bin. What is the expected time to achieve at least 2 balls in every bin? From a previous ...
2
votes
1answer
295 views

Average number of bins occupied when throwing $n$ balls into $N$ bins

There are $n$ balls and $N$ bins. At each time, a ball is thrown in one bin of $N$ bins at random. This repeats n times. So that in total $n$ balls are thrown into bins. The question is, on average, ...