# Questions tagged [balls-in-bins]

For problems on the distribution of $m$ distinct or identical balls into $n$ distinct or identical bins, optionally with restrictions.

317 questions
35 views

### Simple Urn problem doesn't fit with experiment

Given an urn with $n$ numbered balls $[n] = \{1,...,n \}$, one chooses with repetitions $m$ balls. What is the probability that the set of chosen balls $M$ contains a fixed set $S \subset [n]$ of size ...
18 views

### expected time for all balls to be put in urn 2 Ehrenfest model

I am trying to calculate the maximal hitting time of the Lazy Random Walk on the $n$-dimensional hypercube(I know it is $2^n$). I'm using the Ehrenfest urn model. Let $X_t$ be the number of balls in ...
20 views

### How do I solve this combinatoric/probability question regarding constrained allocation of asset.

I have $N$ bank account and $B$ USD savings. For $i$ in $1, 2, 3, ..., N$, the balance of bank account $i$, denoted as $b_i$, is subject to the constraint of $l_i\leq b_i \leq u_i$. The 1-year ...
36 views

### Probability of third ball drawn

Having a box containing 15 red and 7 blue balls. We want to draw 3 balls at random by these conditions on each draw: If the ball is red you set it aside If the ball is blue put it back in What is ...
84 views

### How many ways can n identical balls be distributed into k distinct boxes, such that at least one box is empty?

This is a problem in my combinatorics book that uses the principle of inclusion-exclusion. I can follow almost all of what is said, except the book says that if we consider $A_{i}$ to be the set of ...
25 views

### Infinite process balls in bins problem

Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the ...
29 views

41 views

### Expected Number and Size of Contiguously Filled Bins

I'm pondering on this problem which I made up, so am not sure what the right answer is. Suppose we throw $n$ balls uniformly at random into $N$ bins. Let's call a sequence of contiguous non-empty ...
57 views

### Power of 2 choices balls and bins - Expected number of empty bins

I am looking at the standard balls and bins example and more precisely to the expected number of empty bins. Given $n$ balls and $n$ bins, we throw balls into bins sequentially uniformly at random. So ...
22 views

### Number of empty bins in multinomial distribution

Suppose I have a discrete probability distribution over $N$ bins $\bigl (p_i > 0; \; \sum_{i=1}^N p_i = 1 \bigr)$, and I have drawn $M$ samples from it. Question 1: What is the expected value of ...
29 views

### 8-element permutations of a multiset {3:0,1:1,1:3,1:5,1:8,1:9} with the restriction 0 is not allowed in left or rightmost position

I am lost in how to approach this problem due to the wording: Count the number of distinct 8-digit numbers that may be made by permuting the multi-set: $$MS:=\{0:3,1:1,3:1,5:1,8:1,9:1\}$$ ...
130 views

### What is the probability that the second blue ball is drawn on the eleventh draw?

An urn contains $10$ white, $9$ black, $8$ red and $3$ blue balls. Balls are drawn one by one at random from the urn until $2$ blue balls are obtained. Find the probability of drawing the second blue ...
40 views

### Probability in permutation of balls

There are $n$ balls, of which $r$ balls are red and $(n-r)$ balls are blue. If we select $d$ balls at random (without replacement), what is the probability we select $rd/n$ red balls? In the ...
66 views

### To find the maximum load on a N bin problem.

Consider a scenario, where we have $n$ different colored balls ($C_1, C_2 ... C_n$). Each colored ball ($C_{i}$) contains at least one or more instances of it ($1 \leq |C_i| \leq N$). Where $N$ is ...
55 views

25 views

### Expectation over sets of bins with unequal capacities

Take two sets of bins; Set $A$ contains $M$ bins, each of unequal capacities $a_i$, $i \in \{1,..,M\}$. Set $B$ contains $N$ bins, each of unequal capacities $b_j$, $j \in \{1,..,N\}$. Constrain equal ...
61 views

### Distribute red and blue balls into bins. P(No two red balls in a bin)

Let $n, k, m \in \mathbb{N}$ with $k < n$, $m \leq n$ and $n$ mod $m$ = 0. $n$ is a number of balls where $k$ are red, the rest is blue. $m$ is a number of bins. Now the balls will be randomly ...
35 views

### Balls and boxes - probability

I consider the following sceneriou. Three balls enter the box, $B_1, B_2, B_3$, the balls are independent and identical. Next, we draw the balls from the box, one after another, waiting an exponential ...
71 views

### $2 n$ balls are randomly thrown into $k$ bins. What is the probability that they land in at most $n$ bins?

Consider randomly throwing $2 n$ balls into $k$ bins. I'm looking to upper bound the probability that at most $n$ bins are not empty. How big does $k$ have to be for the probability of the event to ...
123 views

### I throw 750 red and 250 blue balls into 10 bins. What is the probability no bin is over 1/3 blue?

We have $1000$ balls, $750$ red and $250$ blue. We distribute them uniformly at random into $10$ bins. What is the probability none of these bins is at least $1/3$ blue? More generally I'd like to ...
44 views

### Basic combinatorics: In how many ways can we arrange $4$ different balls in $4$ identical boxes?

I stumbled upon a question I can not manage to answer. In how many ways can we arrange $4$ different balls in $4$ identical boxes? I do know there is no importance to the order they're set up so its ...
23 views

145 views

### Balls-into-bins problem: Lower bound for the bins which exactly have one ball

Here is my problem: If $n$ balls are thrown into $m$ bins (uniformly at random and independently) and $n < m$, can we prove: With high probability (w.h.p) there are $\Theta(n)$ bins which ...
Three boys and nine girls are seated randomly in a row of $12$ chairs. What is the probability that there are at least $2$ girls between every pair of boys? My attempt: To find the numerator, we ...
### What is the probability that throwing $m$ balls at random in $n$ urns at least one urn contains $c$ elements?
Let us fix a number of urns $n$ and a fixed capacity $c$. I would like to know which is the probability that $m$ balls, thrown at random in $n$ urns, "overflow", in the sense that at least one urn has ...