Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
4
votes
0answers
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 ...
5
votes
2answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
29 views

An urn contains $4$ red balls, $6$ green balls and $8$ blue balls. Probability with versus without putting the balls back

If we had to determine the probability of getting $3$ red balls $2$ green balls and $4$ blue balls after picking a ball, noting its color and putting it back it would be ${9\choose 3,2,4}\cdot({4\...
0
votes
3answers
48 views

placing 15 balls into 6 urns

There are $6$ urns indexed from $1$ to $6$. We place $15$ balls one by one randomly into the urns. What is the probability that the first urn stays empty? I found $\frac{19\choose4}{20\choose5}$ ...
0
votes
1answer
39 views

If 6 balls are randomly placed in 3 bins, what is the probability that each bin will have 2 balls?

I was working on probability problems and came across this. Can someone explain each step in detail how to get to the solution? Thanks so much.
-1
votes
1answer
104 views

which one is worse in terms of probability

There are 2N white balls and N red balls (all balls are same except for the color), to put into K different boxes, such that every box contains 3N/k balls. We say event A happens, if any box has more ...
1
vote
0answers
52 views

Balls and Bins - high probability bounds on the sum of squared loads

Consider throwing $m$ balls into $n$ bins uniformly at random, and let $X_i$ denote the number of balls that fall in bin $i$. Denote by $S=\sum_{i=1}^n X_i^2$ the sum of square loads on the bins. I ...
1
vote
0answers
54 views

Limited combination problem

Problem: Imagine you have N balls, that you want to put into M boxes. How many ways are there to put N balls into M boxes, if every box can store no more than K balls. For convinience, I named the ...
3
votes
1answer
96 views

Birthday problem variation with balls and bins

Balls are thrown randomly and uniformly into $n$ bins up until one bin has 3 balls. Let there be $T=T(n)$ be the number of throws we made until the occasion occurs. I am to assume $n$ is large ...
1
vote
1answer
46 views

Distributing colored balls into bins such that each bin is distinct.

Suppose I have $n = n_1 + n_2 + \dots + n_k$ balls of $k$ colors, with exactly $n_i \geq 1$ balls of color $i$. Balls that are the same color are indistinguishable. Additionally, we have $m$ ...
3
votes
2answers
71 views

Combinatorics - How many ways to partition an integer n into k bins with values 0 - 5 and restrictions

I have been struggling with this brain teaser for some time now. I looked at some combinatorics and partition equations but I can't find the one that captures the solution entirely. Frame I have a ...
0
votes
1answer
20 views

Number of times I will get b balls from the bag

I have 'n' identical balls and 'k' distinct bags. So total number of ways I can put balls with no restriction in bags is ${k+n-1 \choose k-1}$. So I want to know the number of times there were exactly ...
6
votes
5answers
316 views

Arranging $n$ balls in $k$ bins so that $m$ consecutive bins are empty

This question is inspired by the following problem: Randomly place seven balls into ten bins, with no bin containing more than one ball. What is the probability that there will be (at least) two ...
2
votes
0answers
42 views

Coupon Collector's Problem and Balls in Bins Variant

Consider a variant of the traditional coupon collector's problem. There're $n$ kinds of coupons and there's a $1 \times n$ grid. Each grid corresponds to one kind of coupon. Once picking a coupon, we ...
0
votes
0answers
35 views

Occupancy distribution for batched allocations?

I've searched here and in my limited collection of combinatorics books for a solution to this with no luck. Say I have $b$ bins labeled $1$...$b$. A process selects $k$<=$b$ integers from $[1,b]$ ...
5
votes
1answer
71 views

Conditional probability (urns and balls)

From an urn, containing 6 white and 12 black balls, one takes balls randomly one by one until the second white ball appears. What is the probability that: 1) second white ball appears on the second ...
4
votes
2answers
57 views

Number of urns with more than K balls inside

I have a probability problem that I have simplified down to the following: Given M balls that are thrown randomly (uniformly) into N urns, what is the expected number of urns that have more than K ...
0
votes
0answers
45 views

Probability of having k groups of r consecutive empty bins throwing n balls in n bins

Suppose to throw independently n balls in n bins with uniform probability. I'm trying to obtain the probability distribution of having exactly k groups of r consecutive empty bins. I started ...
1
vote
0answers
50 views

Probability of having m groups of at least 2 empty consecutive cells by putting k balls in n bins

Suppose k balls are placed uniformly at random in n cells, each one with probability 1/n. Let's call "r-block" a group of at least r consecutive cells. I would like to know if it's possible to ...
0
votes
1answer
67 views

Balls in bins: Prove that the probability that there is some bins of $k+1$ or more balls is at most $\frac n{k^2}$

(Using Chebyshev's inequality and Union bound) Suppose that we throw $n$ balls into n bins uniformly at random. Let $k≥\sqrt n$ be a positive integer Show that with probability at least $1-\frac n{k^...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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\}$$ ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
55 views

Concentration bound around the mean for balls-in-bins

I have been thinking of the following problem. Suppose I throw $n$ balls into $m$ bins, each bin selected uniformly at random. Let $B _i$ $(i=1,2,\dots,m)$ denote the number of balls that land in bin $...
2
votes
2answers
56 views

Can we model the number of increasing words as ball-and-urn problem?

Let the ball-and-urn problem be defined as follows: How many ways can one distribute $k$ [in]distinguishable balls into $n$ [in]distinguishable urns? Let the problem of increasing words be defined ...
0
votes
1answer
56 views

Probability distribution of X(balls and bins)

There are 3 red, 9 green balls in the box. We pick them randomly without returning. When take out red ball for the first time we stop. X-discrete distributed variable, where we have the number of ...
1
vote
1answer
61 views

Probability of 4 balls in one of 80 bins after 26 throws [closed]

This relates to a stock problem: I have a product with 80 sizes, the stock level of each size is 3, I forecast 26 customers per week so what is the probability I will run out of stock of at least one ...
2
votes
1answer
78 views

Distinguishable groups of balls into distinguishable boxes with constraints

We have $E$ balls of $N$ colors. Let's call $e_i$ the number of balls of color $i$ (of course across group balls are distinguishable while within a color they are not). We can split these balls among $...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
3answers
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 ...
2
votes
1answer
23 views

count of 4 digits number with odd digits with sum 16

Let $abcd$ be a 4 digit number and $a,b,c,d$ are all odd digits (1,3,5,7,9). We want to find count of such numbers that $a+b+c+d =16$. In the book in which I found this question, the answers was: $...
1
vote
1answer
159 views

Balls and Bins (Find no of balls)

How many balls do you need to throw randomly into n bins so that the probability that none of the bins is empty is at least 1/100? I am trying to solve this question by first finding the expected no ...
1
vote
1answer
54 views

Probability that all bins have at least one black ball?

Say I have T balls, B of them black and T-B of them white. I have N bins, each with a maximum capacity of T/N (that is, when the balls are all placed into the bins, all bins have the same number of ...
0
votes
1answer
94 views

Expected Balls in Bins of Unequal Capacities

Question: There are $n$ bins each with different capacities, $c_1, c_2, .., c_n$. There are $m$ balls, where $m = p \sum_i c_i$, for $0<p<1$. Suppose the capacities and number of balls are ...
0
votes
1answer
178 views

$10$ balls are randomly chosen from an urn containing $17$ white and $23$ black balls

So I'm currently a bit stuck on this question (see image below) For part a), since $i = 1,2,\cdots,10$, the Bernoulli variable can correspond with the number of balls drawn. Hence, for each $i$, $P(X=...
1
vote
1answer
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 ...
1
vote
1answer
31 views

Distributing boys and girls in seats with relational restrictions

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 ...
1
vote
3answers
108 views

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 ...