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

23
votes
3answers
3k 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 ...
10
votes
1answer
323 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 ...
9
votes
3answers
402 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 ...
8
votes
1answer
161 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 ...
8
votes
5answers
635 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
1answer
276 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
2answers
2k 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 ...
7
votes
2answers
291 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 ...
6
votes
1answer
203 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
255 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% ...
5
votes
4answers
214 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, ...
4
votes
3answers
665 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 ...
4
votes
3answers
4k 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
234 views

$m$ balls into $n$ urns

Assume that there are $m$ balls and $n$ urns with $m>n$. Each ball is thrown randomly and uniformly into urns. That is, each ball goes into each urn with probability 1/n. What is the probability ...
4
votes
1answer
264 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 ...
4
votes
2answers
135 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
223 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
535 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
3answers
53 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
304 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
2answers
237 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
464 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
1answer
200 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, ...
2
votes
1answer
281 views

What is the expected number of days in a 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, ...
2
votes
1answer
129 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 ...
2
votes
1answer
405 views

Distribution of distinct balls in identical boxes

how can I derive a formula for the number of distributions of $n$ different balls in $k$ identical boxes. Where $\mathbf{empty\ box}$ is allowed. I know this is equivalent to finding the number of ...
2
votes
1answer
82 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. ...
2
votes
1answer
131 views

Bins and balls model - filling first bins [close]

We have $n$ bins and $m$ balls. I want to compute the probability that in the first $k$ bins, $q$ of them will be non-empty. I can throw $m$ balls into $n$ bins in $n^m$ ways. Using Stirling ...
2
votes
1answer
117 views

Bounds for 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 a nice elementary way to ...
2
votes
1answer
104 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)$ ...
2
votes
0answers
65 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 ...
2
votes
0answers
126 views

Modified balls and bins

Assume that we have $n$ balls and $k$ bins. The $n$ balls are are divided into $M$ sets, $\left\{ {{m_i}} \right\}_{i = 1}^M$, where $\sum\limits_{i = 1}^M {\left| {{m_i}} \right|} = n$, $|m_i| \le ...
2
votes
0answers
91 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
111 views

Constrained combinations of balls in jars

Not sure how to solve the following problem. Imagine we have balls of $n$ different colors. There are $m$ balls of each color, so in total we have $nm$ number of balls. The question is how many ...
1
vote
1answer
54 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 ...
1
vote
3answers
91 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
137 views

Probability that $\frac{n}{2}$ bins are empty [close]

A Bloom filter of length $n$ was built. I have only the first $\frac{n}{2}$ bits of this filter. How will the false positive probability change? For the whole Bloom filter, the false positive ...
1
vote
1answer
228 views

Expectation of throwing $n$ balls into $n$ bins

Suppose we throw $n$ indistinguishable balls in $n$ bins at random. The throws are independent. What is the expected number of empty bins? What is the expected number of bins with one ball. Using ...
1
vote
2answers
175 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
446 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
43 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 ...
1
vote
1answer
44 views

What is the probability of picking $4$ balls out from the two bins?

Assume there are $2$ bins (bin $a$ and bin $b$ ), and each bin contains $n$ indistinguishable balls with $n>10$. The probability of picking $k$ ball from each bin is $p_k$, ($k\ge 0$). Then what is ...
1
vote
1answer
75 views

Combinatorics with balls and bins with constraint

I have $90$ identical balls to distribute among $64$ distinguishable bins. Each must get at least 1 ball, after that the distribution over the remaining $26$ does not matter. I know I first have to ...
1
vote
2answers
61 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 ...
1
vote
2answers
46 views

Inclusion/Exclusion Principle for indistinguishable balls into two different types of boxes

The problem asks me how to distribute n balls into h boxes where each must get at least 1 n and t boxes where each can be left empty What I have, and where I seem to have stalled is how to ...
1
vote
2answers
109 views

How many ways to $22$ balls in $5$ boxes problem

How many ways are there to put $22$ identical balls into $5$ boxes, with each box has at least $2$ balls? The answer is $16$ choose $4$, i.e., $_{16}C_4$, but can someone explain it to me?
1
vote
1answer
140 views

$n$ balls into $k$ baskets, $n \geq k$, no empty baskets

I have $n$ balls and throw them into $k$ baskets. None of $k$ baskets should be empty. Which means each basket has at least one ball. Balls and baskets are not distinguishable. What is the number ...
1
vote
2answers
105 views

Urn problem: replacing white balls with black once selected

I'm trying to find the probability of an outcome where, using the traditional example, white balls are replaced by black balls once selected. Initially I have $n$ white balls and $\mu$ samples. I ...
1
vote
1answer
160 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
0answers
61 views

Balls and bins question with nlogn balls and n bins.

The question: Suppose we randomly drop nlogn balls into n bins. Give an upper bound on the expectation of the maximum number of balls in any bin. How would this be done? I believe the answer is well ...