30
votes
3answers
5k views

Making 400k random choices from 400k samples seems to always end up with 63% distinct choices, why?

I have a very simple simulation program, the sequence is: Create an array of 400k elements Use a PRNG to pick an index, and mark the element (repeat 400k times) Count number of marked elements. An ...
1
vote
1answer
56 views

Is there a fast, reasonably accurate estimator for multinomial PDF?

I am working on a balls in boxes kind of problem, where the probability of a ball ending up in a certain box varies by box, that is, each box has some probability P of getting any ball, all together ...
2
votes
3answers
53 views

Find the probability that the $4$th ball removed from the box is white

A box has $10$ balls, $6$ of which are black and $4$ of which are white. $3$ balls are removed from the box, their color unnoted. Find the probability that a fourth ball removed from the box is ...
1
vote
1answer
43 views

Expectation time for at least 2 balls in each bin

Given $N$ bins and an unlimited number of balls, to be assigned one ball per time unit to a uniformly random bin. What is the expected time to achieve at least 2 balls in every bin? From a previous ...
0
votes
1answer
80 views

$N$ bins, $m$ balls: Probability of any bin containing *exactly* $k$ balls.

This is an extension to question 821984: Given $N$ balls independently distributed randomly among $m$ bins, what is the probability that at least one bin gets exactly $k$ balls? And is this ...
1
vote
1answer
44 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 ...
1
vote
2answers
61 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
61 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
125 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
178 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
131 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
62 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
137 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
58 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
228 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
508 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
147 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
117 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
670 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
307 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
200 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
105 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
126 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
170 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
125 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
237 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
112 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
161 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
91 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
235 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
255 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
403 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 ...
7
votes
2answers
291 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
214 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
172 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
135 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
175 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
76 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
276 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
282 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
160 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
76 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
144 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
129 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
306 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
264 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
224 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
635 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
203 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
155 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 ...