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
0answers
33 views
Combinatorics: arranging $n$ balls in $k$ cell with condition
Im learning combinatorics, and I came across a question I couldn't find the answer to:
I have $n$ identical balls and $k$ different cells, I want to find the number of ways to arrange the balls with ...
0
votes
1answer
22 views
Probability that the nth urn is empty
A total of $n$ balls are thrown to $m$ urns, each urn has the same probability of catching a ball. What is the probability that the $n$th urn is empty?
What i've tried:
i figured the probability of ...
0
votes
0answers
23 views
Probability of “no bin containing more than some number of balls” when randomly toss nlgn balls into n bins?
I am asked:
Randomly tossing $nlg(n)$ balls into $n$ bins, find $C$ such that $\text{Pr}(\text{No bins containing more than } Clg(n) \text{ balls}) \ge 1-\frac{1}{n}$.
I'm thinking that using ...
0
votes
0answers
41 views
Calculating expected value for X given a scenario
This question was given to me as a review for an upcoming exam:
$12$ baseballs are dropped into $5$ empty bins. Let $X$ be the number of empty bins after dropping the balls.
Calculate $\langle X \...
1
vote
1answer
47 views
How to solve this probability/combinatorics question about balls in bins
Below is the problem that I need to solve
Suppose you blindly place five balls labeled A, B, C, D and E inside five bins labeled A, B, C, D and E. What are the chances that, in your selection, no ...
0
votes
1answer
36 views
Polya's scheme for two urns
I don't know why I can't solve this problem using Polya's method .$$$$ There are two boxes,one of which contains 5 black and 7 white marbles and the other have 2 black and 2 white marbles .randomly ...
2
votes
1answer
55 views
Expected draws to find $z$ of the same colored balls in $y$ urns
There are $y$ urns
Each urn contains $x$ distinctly colored balls. The contents of each urn are identical to start out.
You can choose an urn to draw from and draw without replacement, adding that ...
0
votes
3answers
71 views
In how many way we can arrange 4 books on 7 different shelves - with no specific demandings?
I was given an unconventional combinatorics question I was struggling with.
Suppose we have 4 books and 7 different bookshelves.
In how many ways the books can be arranged without loss of generality?
...
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
1answer
33 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
21 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
47 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
156 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
29 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
51 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
58 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
43 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
105 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
55 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
106 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
47 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
85 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
22 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
353 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
48 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
78 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
59 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
1answer
105 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
44 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
67 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
24 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
30 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
161 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
42 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
70 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
60 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
60 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
76 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
80 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
70 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
79 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
127 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
46 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
207 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 ...
