1
vote
1answer
28 views

What is the probability of picking $4$ balls out from the two bins?

Assume there are $2$ bins (bin $a$ and bin $b$ ), and each bin contains $n$ indistinguishable balls with $n>10$. The probability of picking $k$ ball from each bin is $p_k$, ($k\ge 0$). Then what is ...
0
votes
0answers
30 views

Calculating probabilities for distributing M balls in 4 bins scenario

I have the following scenario that I need to obtain the formula for it in order to program it: There are number of balls (M balls), and there are 4 different bins (Bin1, Bin2, Bin3, Bin4) that the ...
1
vote
2answers
45 views

probability that given n balls and 60 urns no urn has more than 1 ball

A carnival game is set up so that a ball put into play has an equal chance of landing in any of 60 different slots. The operator of the game allows you to choose any number of balls and put them all ...
1
vote
0answers
38 views

Balls and bins question with nlogn balls and n bins.

The question: Suppose we randomly drop nlogn balls into n bins. Give an upper bound on the expectation of the maximum number of balls in any bin. How would this be done? I believe the answer is well ...
-1
votes
2answers
88 views

Balls and bins problem - expected number of balls needed to throw [closed]

Suppose we have n boxes and we start randomly and independently throwing balls into the boxes. (a) For a given box, what is the expected number of balls we need to throw before one of the balls lands ...
0
votes
1answer
136 views

Ball and bins & Coupon collector problem

If you know a coupon collector problem, you will know what I am talking about. But if you are not familiar with I will try to explain what is the coupon collector problem. I have $n$ bins. I throw ...
2
votes
1answer
116 views

Bins and balls model - filling first bins [close]

We have $n$ bins and $m$ balls. I want to compute the probability that in the first $k$ bins, $q$ of them will be non-empty. I can throw $m$ balls into $n$ bins in $n^m$ ways. Using Stirling ...
0
votes
2answers
54 views

Probability and conditional?

A bag contains four red balls and four white balls. A ball is selected at random, removed and replaced by a ball of the opposite colour. A second ball is then selected at random. Calculate the ...
1
vote
2answers
133 views

Probability that $\frac{n}{2}$ bins are empty [close]

A Bloom filter of length $n$ was built. I have only the first $\frac{n}{2}$ bits of this filter. How will the false positive probability change? For the whole Bloom filter, the false positive ...
0
votes
1answer
51 views

probability of specific number of balls in an urn

I have $n$ balls, I distribute them between 2 urns. Each ball goes to urn 1 with probability $p$ and urn 2 with probability $1-p$. What is the probability that there are $l$ balls in urn 1 when all ...
1
vote
1answer
184 views

Expectation of throwing $n$ balls into $n$ bins

Suppose we throw $n$ indistinguishable balls in $n$ bins at random. The throws are independent. What is the expected number of empty bins? What is the expected number of bins with one ball. Using ...
0
votes
1answer
447 views

Balls and bins probability problem

$k = \sqrt n$ balls are thrown into $n$ bins. The bins are standing in a row and numbered from 1 to $n$. What is the probability that there are no two balls in the same bin or in adjacent bins??? In ...
0
votes
2answers
133 views

A bin and balls problem

Throw 7 balls into 7 bins. Given there are exactly 2 empty boxes, find the probability that 1 bin contains 3 balls, and thus the other 4 bins contain 1 ball each. I know I could use a multinomial ...
2
votes
1answer
111 views

Bounds for max load with $n$ balls in $n$ bins?

If you throw $n$ balls into $n$ bins uniformly and independently at random, let $X$ be the number of balls in the bin with the largest number of balls in it. Is there a nice elementary way to ...
4
votes
3answers
528 views

Expected max load with $n$ balls in $n$ bins?

If you throw $n$ balls into $n$ bins uniformly and independently at random, let $X$ be the number of balls in the bin with the largest number of balls in it. Is there an elementary way to ...
2
votes
1answer
252 views

Balls and bins conditioned on the number of non-empty bins

The expected number of occupied bins in the standard balls and bins problem (with $m$ balls into $N$ bins) is $N\left( {1 - {{\left( {1 - \frac{1}{N}} \right)}^m}} \right)$. How do I compute this ...
2
votes
1answer
174 views

Average number of bins occupied when throwing $n$ balls into $N$ bins

There are $n$ balls and $N$ bins. At each time, a ball is thrown in one bin of $N$ bins at random. This repeats n times. So that in total $n$ balls are thrown into bins. The question is, on average, ...
1
vote
2answers
100 views

Urn problem: replacing white balls with black once selected

I'm trying to find the probability of an outcome where, using the traditional example, white balls are replaced by black balls once selected. Initially I have $n$ white balls and $\mu$ samples. I ...
2
votes
0answers
121 views

Modified balls and bins

Assume that we have $n$ balls and $k$ bins. The $n$ balls are are divided into $M$ sets, $\left\{ {{m_i}} \right\}_{i = 1}^M$, where $\sum\limits_{i = 1}^M {\left| {{m_i}} \right|} = n$, $|m_i| \le ...
0
votes
2answers
163 views

Probability in ball coloring

You have exactly $n^2$ balls each one of which can be colored in one of $n^2$ ways. That is total colors is $n^2$ but I am not saying all the $n^{2}$ balls are distinctly colored. However assume each ...
0
votes
1answer
119 views

balls and bins - the probability of reaching the exact expected value

Suppose I throw $n$ balls to $m$ bins (randomly and independently). The expected value of number of balls in each bin is $n/m$. How can I tell (or bound) the probability that every bin has exactly ...
2
votes
2answers
192 views

Probability of number of unique numbers in $37$ Roulette Wheel spins.

I was wondering if someone could help me answer the following question: Calculate the probability that in $37 $ consecutive spins of a roulette wheel (using an European Roulette wheel) you will have ...
0
votes
2answers
110 views

Yet another balls and boxes problem; minimum number of throws so that we have no empty boxes.

I managed to figure out how many empty boxes will be left given n amount of throws, just having a hard time figuring out the minimum number of throws necessary so that we have no empty boxes. Would it ...
8
votes
1answer
154 views

How many expected people needed until 3 share a birthday?

I asked a somewhat related question recently and then became interested in this one: how many people are required, on average, until 3 share a birthday? More generally, if we have $M$ bins, what is ...
2
votes
0answers
89 views

$m$ balls into $n$ already occupied urns

Assume that there are n urns, $k\in\{1,...,n-1\}$ of which have already at least one ball. $m$ new balls will be thrown into urns. Each of the $m$ balls is thrown randomly and uniformly into $n$ urns. ...
4
votes
1answer
210 views

$m$ balls into $n$ urns

Assume that there are $m$ balls and $n$ urns with $m>n$. Each ball is thrown randomly and uniformly into urns. That is, each ball goes into each urn with probability 1/n. What is the probability ...
5
votes
3answers
238 views

Second pair of matching birthdays

The "birthday problem" is well-known and well-studied. There are many versions of it and many questions one might ask. For example, "how many people do we need in a room to obtain at least a 50% ...
9
votes
3answers
380 views

Probability $k$ bins are non-empty

The following problem arises in the analysis of Bloom filters. Consider $m$ bins and $N=nk$ balls placed uniformly and independently at random into the bins. A query chooses $k$ bins uniformly and ...
0
votes
0answers
23 views

The distribution of balls in bins as a function of the number of balls [duplicate]

If I toss $m$ balls into $N$ bins, as a function of $m$, what distribution of balls and bins should I expect as a function of $m$? What would be the mean largest number of balls in a particular bin?
7
votes
2answers
238 views

Find: The expected number of urns that are empty

A total of $n$ balls, numbered $1$ through $n$, are put into $n$ urns, also numbered $1$ through $n$ in such a way that ball $i$ is equally likely to go into any of the urns $1, 2, . . . , i$. Find ...
5
votes
4answers
207 views

$n$ balls into $n+1$ urns (with one special urn)

Assume that there are $n$ balls numbered from $1,2,\ldots,n$ and $n+1$ urns, numbered as $0,1,\ldots,n$ Throw each ball randomly into one of $n$ urns: urn 1, ...
0
votes
0answers
162 views

Balls and Bins problem with constraint

Assume we have $B$ black balls and $R$ red balls, where $R+B$ is a multiple of 4. We want to distribute the balls in $\frac{R+B}{4}$ bins such that each bin has at least 1 red ball and at least 1 ...
4
votes
2answers
118 views

How many boxes will be empty?

$150$ balls randomly put into $100$ boxes, each ball could be put into any of these 100 boxes with same probability, after that, on average, how many boxes will be empty? No calculator. Choose one of ...
1
vote
2answers
163 views

Probability of red ball i before any black ball

Assume we have $r$ red balls and $b$ black balls in a box and we remove one ball at a time without replacement. Red balls are labeled from $1$ to $r$. We want to calculate the probability a particular ...
1
vote
0answers
72 views

Poisson Distribution?

There exists 1000 boxes. These boxes are randomly filled with balls. How many balls are required in order that only 1 in 100 boxes are left empty? This sounds like a Poisson distribution problem to ...
8
votes
1answer
265 views

Repeatedly Toss Balls into Bins

$n$ balls are randomly tossed into $m$ bins, each bin can hold $k$ balls. If a ball is tossed into a full bin (already has $k$ balls in it), it can be tossed repeatedly and randomly into the $m$ bins ...
2
votes
1answer
247 views

What is the expected number of days in a year in which exactly $k$ people in a group of $n$ people have been born?

There is a group of $n$ people and we must find the average number of days that in each of them exactly $k$ people are born ($k$ and $n$ are given). This question assumes that a year has $365$ days, ...
1
vote
1answer
142 views

$k$ balls into $n$ bins — Number of occupied bins

Suppose we throw $k$ balls into $n$ bins. Assume that $\log^2n\le k\le n$. Is there a high probability bound (preferably exponential) on the number of occupied (i.e., non-empty) bins? Something ...
0
votes
0answers
74 views

balls and bins: the first time when max-loaded is less than twice min-loaded

We have $n$ bins, in each step we throw a ball in a bin chosen uniformly and independently from the $n$ bins we have. We repeat the process $k$ times. Let $B_k$ be the number of balls in ...
0
votes
1answer
136 views

Bins in balls where bin size grows exponentially

I have $k$ bins. The first bin can fit $1$ ball. Each subsequent bin can fit two times more balls than the previous one. In other words, the $i$th bin can fit $2^i$ balls. We randomly assign $U = ...
2
votes
1answer
128 views

Amount of distinct numbers in a sequence of $k$ random numbers in range $[1,\ldots,n]$

Let $D$ be the amount of distinct numbers in a sequence of $k$ random numbers in range $[1,\ldots,n]$ (n>k). I want to show that: $D=\Omega(k)$ with exponential high probability. I'm interested in the ...
0
votes
2answers
300 views

Throwing $k$ balls into $n$ bins.

I have the following question: Throwing $k$ balls into $n$ bins. What is the probability that exactly $z$ bins are not empty? I thought about something like: $$\Pr(z)=\frac{n! z^{k-z}}{n^k ...
4
votes
1answer
257 views

Maximum load of a bin in the $n$ balls with weights into $m$ bins problem

$n$ balls, each with a weight $p_i$, are thrown into $m$ bins. Each bin is chosen with uniform probability. Prove or disprove that the expected value of the maximum load among the loads of bins is ...
4
votes
1answer
211 views

Probability - Balls and Buckets; variance question

I've been working on this problem for a while and its giving me no end of trouble! The question is this: Suppose we have 2k buckets, numbered 1 through 2k. We throw x black balls and y white balls, at ...
8
votes
5answers
596 views

Probability that all bins contain strictly more than one ball?

Here's the problem I'm working on: Given that I'm distributing $N$ balls into $K$ bins, what is the probability that all bins contain at least two (strictly more than 1) balls? This seems like a very ...
6
votes
1answer
201 views

Yet another balls and bins problem

If $p_n$ denote the probability that when $n$ balls are randomly put in $n$ bins then there is at least one bin with exactly one ball. Is there a simple (involving only little computation) reason for ...
0
votes
1answer
150 views

Expected value for a function concerning a balls and bins problem

I'm optimizing a hash function mapping $M$ items into $N$ bins and I need a criterion for evaluating the quality of the mapping. Denoting the number of items put into bin $i$ by $x_i$, an ideal ...
6
votes
2answers
2k views

If n balls are thrown into k bins, what is the probability that every bin gets at least one ball?

If $n$ balls are thrown into $k$ bins (uniformly at random and independently), what is the probability that every bin gets at least one ball? i.e. If we write $X$ for the number of empty bins, what ...
10
votes
1answer
316 views

Hyper Birthday Paradox?

There are $N$ buckets. Each second we add one new ball to a random bucket - so at $t=k$, there are a total of $k$ balls collectively in the buckets. At $t=1$, we expect that at least one bucket ...
4
votes
3answers
3k views

How can I solve bins-and-balls problems?

Below is the problem that I wanted to solve When there are $m$ balls and $n$ bins, balls are thrown into bins where each ball is thrown into a bin uniformly at random. What is the expected number ...