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