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.
-1
votes
1answer
102 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
47 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
53 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
86 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
42 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
61 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
296 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
41 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
68 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
53 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
43 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
45 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
43 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
41 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
17 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
28 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
104 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
51 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
48 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
52 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
41 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
58 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
77 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
53 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
31 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
65 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
113 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
43 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
129 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
49 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
71 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
121 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
116 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
90 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 ...
2
votes
1answer
53 views
In a town of a population of 1825, what is the probability that each day at least one has birthday?
Attempt
Since this is a success/failure sample, I figured the event X : number of people who have birthday the chosen day follows a binomial distribution, with $ n = 1825$ and $p = 1/365$. Since $n \...
-1
votes
1answer
109 views
Putting $n$ balls in $m$ boxes and in each box is even number of balls
I'm trying to count number of ways to put $n$ identical balls in $m$ identical boxes that in each box is even number of balls. I figure to put balls in pairs so in each box will be even number. Is ...
1
vote
0answers
151 views
In how many ways can $5$ different colored balls be placed into $8$ bins if no bin contains more than one ball?
5 distinct different colored balls into 8 distinct bins and no bin contain more than one ball, how many ways can the balls be placed into the bins?
I got 8*7*6*5*4=6,720. But I am unsure if it is ...
1
vote
0answers
46 views
Probability of all balls being alone at least once in repeated N balls M bins problem
The problem
This is a normal $n$-balls-$m$-bins problem: suppose you have $n$ numbered balls that will be placed at random in $m$ bins. But the twist is: this experiment will be repeated $d$ times.
...
1
vote
0answers
92 views
Formula for unique distribution of colored balls into boxes
I'm trying to figure out how to uniquely distribute 2 red balls and 2 blue balls into 3 indistinguishable boxes.
My mind leapt to the general case, and I've found that there is a bijection between ...
0
votes
1answer
98 views
balls and buckets combinations with a minimum and maximum number of empty buckets
Given $K$ balls and $M$ buckets and the limits $L1$ and $L2$ where $0<L1<L2<M$. We distribute all balls in the buckets randomly so a bucket can end up with $0$ to $K$ balls.
How do I ...
3
votes
0answers
99 views
Indistinguishable Balls Into Indistinguishable, Limited-Sized Bins
I have the following experiment
There are m indistinguishable balls and n indistinguishable bins of size s. For each ball, we pick a bin. If the bin still has capacity, the ball is placed inside ...
4
votes
2answers
109 views
Indicator variable with boxes and balls
We have 10 blue balls labeled from 1 to 10 and 10 red balls with same labels and we randomly put them into 10 boxes so that in each box is one blue and one red ball. Find the expected number of boxes, ...
1
vote
0answers
64 views
A variation of the balls-and-bins problem, with additional constraints
The set-up
Suppose that you have $n$ bins, $i$ of which already contain at least 1 ball. Suppose that you sequentially toss balls into those bins during a predefined number of rounds.
The rules
The ...
