Stack Exchange Network

Stack Exchange network consists of 174 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.

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