It's about distribution or arrangement of $m$ distinct or identical balls into $n$ distinct or identical bins with all possible combinations.

learn more… | top users | synonyms

0
votes
2answers
355 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 ...
3
votes
1answer
68 views

Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
3
votes
1answer
116 views

Expected total number of balls in all bins after throwing balls uniformly randomly to bins that have limited capacity

Consider throwing $n$ balls uniformly randomly to $L$ bins. Each bin has capacity $G$, meaning that if a ball is threw to a bin that already has $G$ balls in it, the ball is discarded. Is that ...
2
votes
1answer
251 views

Jee Main 2015 Question. Probabilty

If $12$ identical balls are to be placed in $3$ identical boxes, then the probability that one of the boxes contains exactly $3$ balls is: (1) $22 \times(\frac{1}{3})^{11}$ (2) $\frac{55}{3} \times (\...
2
votes
1answer
149 views

About the distribution of balls in bins

Suppose we have $n$ balls and $n$ bins, and consider the following process: at stage $k$, we throw $\ln{n}$ balls into the bins, independently at random. We stop after $n/\ln{n}$ stages, when all ...
2
votes
1answer
112 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
vote
1answer
32 views

Find the number of unique paths, given a fixed set, that produce a given output.

I'm looking to find the probability of selecting a given number M given a set of N numbers in a bounded range (or potentially in several differently bounded ranges, but I'm starting simple). I'm ...
0
votes
1answer
85 views

Balls into bins

I have $n$ bins such that each bin may contain at most $2$ balls. we start inserting $k$ balls into the bins, by choosing randomly for each ball the bin to which it will be inserted. what is the ...
0
votes
1answer
47 views

$n$ users placed in cells randomly and independently and figure out the expected value

Suppose $n$ users placed in $m$ cells randomly and independently. Let $i$ belongs from $1$ to $n$, and each user $i$ wants to get file $f_i$. Now suppose each different users independently has file $...
0
votes
1answer
85 views

Balls into bins, probability that $k$ of the bins has at least 2 balls

$n$ balls are thrown uniformly randomly into $m$ bins, I'd like to calculate the probability that exactly $k$ bins have at least 2 balls. This is of course doable using the multinomial distribution, ...
0
votes
1answer
46 views

Probability of having K cigarettes in one of the 2 packs of cigarettes

We have 2 packs of cigarettes, N cigarettes in each of the pack. We keep taking out a cigarette from those packs randomly, until one of the packs gets empty. How much is probability that the other ...
0
votes
1answer
43 views

Given $d>8$ boxes and $n$ balls. . What is $P(A \cup B \cup C)$?

Given $d>8$ boxes and $n$ balls. Consider event $A$=boxes numbered $1,2,3,4$ receive 0 balls.$B=3,4,5,6$ receive 0 balls, $C=5,6,7,8$ receive zero balls. What is $P(A \cup B \cup C)$? Attempt: ...
0
votes
1answer
78 views

Expected number in b bins with max k balls each, balls in bins question

Suppose we have b bins and each bin could have max k balls. We have sufficient balls and what is the expected number if we need to full all bins? I know the answer when k = 1, the expected number is b ...
5
votes
0answers
35 views

More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
4
votes
0answers
93 views

Probability of having at least $j$ collisions when tossing $m$ balls into $n$ bins

Suppose that we throw $m$ balls into $n$ bins uniformly and independantly at random. We consider collisions as distinct unordered pairs, e.g., if 3 balls are tossed in one bin, we count 3 collisions. ...
3
votes
0answers
89 views

Maximum bin load for $\alpha n$ balls into $n$ bins

In a paper I am reading the author writes: A standard result concerning balls and bins shows that if we throw at least $\alpha n$ balls into at most $n$ bins, then the maximum bin load is $(1+o(1))...
3
votes
0answers
119 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. ...
2
votes
0answers
35 views

$\mathbb{P}[X_1(k^\ast)] \leq \left( \frac{e}{k^\ast} \right)^{k^\ast} \frac{1}{1-e/k^\ast} \leq n^{-2}$ inequality is used to prove the theorem

In the book Randomized Algorithms from Motwani and Raghavan, it is stated in page 44 that $$\mathbb{P}[X_1(k^\ast)] \leq \left( \frac{e}{k^\ast} \right)^{k^\ast} \frac{1}{1-e/k^\ast} \leq n^{-2}.$$ ...
2
votes
0answers
134 views

Partition counting problem with cap on pairwise intersection

Fix $T_1,\ldots T_m$ as pair-wise disjoint $k$-subsets of $\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$. For any $j\le k$, how many sets of the form $\{C_1,\ldots,C_m\}$ are ...
2
votes
0answers
92 views

How to estimate pigeonhole principle?

I was thinking about this after my professor mentioned the pigeonhole principle in class. Let's say we have $N$ items and $M$ containers. Here we assume $N > M$. We will randomly place each of the $...
2
votes
0answers
179 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 k$...
2
votes
0answers
116 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 ...
2
votes
0answers
91 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 maximum-...
1
vote
0answers
22 views

Relation of relative numbers of (restricted) ways to distribute identical / distinct objects into distinct bins

If want to know if the following inequality holds for general values of $s \leq n \ll m$. $$\frac{C_0(n,m,s)}{C_0(n,m)} \leq \frac{p(n,m,s)}{m^n}$$ $C_0(n,m) = \binom{n+m-1}{m-1}$ is the number of ...
1
vote
0answers
62 views

Throwing balls into bins, where some of the bins are closed after one ball

My question is a variant of the balls-in-bins problem (similar to the coupon collector problem), where I'm interested in how many of the $n$ bins will be empty after throwing $k$ balls. As far as I ...
1
vote
0answers
101 views

Number of ways to write a tuple of positive integers as a sum of tuples with certain constraints

There are $N$ boxes into which we put $mn$ balls in $m$ steps, where in each step we insert $n$ balls, each of which goes into a different box. In how many ways can we do this so that box $B_i$, $1 \...
1
vote
0answers
67 views

Balls and Bins [Raab 1998 proof]

I cannot work out the proof in one of the steps. The following is copied from the original paper “Balls into Bins” — A Simple and Tight Analysis: The case when $n\log n \ll m \leq n \text{polylog}(n)$...
1
vote
0answers
115 views

Balls and Bins- Hash Table: a Concrete Example

My question is related to this: http://cs.stackexchange.com/questions/49027/balanced-allocation-hash-table-overflow-probability/49030#49030 In [1,2], it is said that if we throw $n$ balls into $...
1
vote
0answers
64 views

Labeled balls and urns. Finding the probability for a specific pairing.

I was reading a text and came across this problem. The wording is a little terse so I'm not clear on why the result is true. Given N balls and N urns, all of which are labeled. The balls are ...
1
vote
0answers
58 views

Balls into bins with repelling balls and bins, probability 1 or more of a specified subset of bins is empty?

I have $N$ sets of differently colored balls, each set a distinct color and each set consisting of 3 balls. There are 9 bins. Balls are tossed and will land into bins uniformly randomly, except if ...
1
vote
0answers
96 views

Expansion for r-associated Stirling numbers of the second kind

I am looking for a paper or guidance for expanding the r-associated Stirling numbers of the second kind $S_r(n,k)$. $S_r(n,k)$ is the number of ways to partition a set of n objects into k subsets, ...
1
vote
0answers
150 views

Probability of drawing balls with different colours

In a jar of balls with different colours, can we find a general probability distribution of having n distinct colours with N number of balls grabbed ? Assuming that any colours have an equal chance to ...
1
vote
0answers
141 views

n bins, m balls and m>n: Probability of at least r bin containing exactly k balls.When bins are numeret from 1…n and ball is equale.

I want to calculate this probability .In this question $N$ bins, $m$ balls: Probability of any bin containing *exactly* $k$ balls. calculate this but I can not understand this calculation.To be more ...
1
vote
0answers
113 views

Distribution of maximum/minimum proportion in a sampling process

I am facing something that can be explained as a balls & urns problem. Suppose you have $B$ black and $W$ white balls inside an urn. They are randomly chosen, one by one, without replacement, and ...
1
vote
0answers
149 views

Occupancy distribution bounds for $k$ balls in $m$ bins

Suppose we throw $k$ (distinct) balls into $m$ (distinct) bins, and let $B$ count the number of non-empty bins. I am interested in lower bounds on $B$. More precisely, I wish to bound from above the ...
1
vote
0answers
233 views

The probability of two balls going into the same bin

Suppose I have n bins and n balls with label on them. What would be the probability that I throw the i th ball into the same bin as the j th ball? Is it just 1/n because there is a probability of 1/n ...
1
vote
0answers
231 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 ...
0
votes
0answers
100 views

Combinatorial object and formula for n distinguishable balls in k distinguishable bins?

Balls and bins have labels; n >= k. Bins must have 1 or more balls, but balls can only be assigned once. For now, I will say all balls need to be assigned. In reading Wikipedia on the twelvefold way,...
0
votes
0answers
28 views

Selecting point of reference when counting

When arranging people (A, B, C, D, E) in seats (1,2,3,4,5), why isn't it same to count with reference to seats eg. (number of people can sit in seat number 1) * (number of people can sit in seat ...
0
votes
0answers
53 views

I need a help to understand a paper about Balls and Bins and bins max load

I must declare that I have asked a similar question before but I did not get any answer. I do need a concrete example and formula allowing me to determine maximum number of balls in a bin with ...
0
votes
0answers
66 views

Balls and Bins when #balls < #bins

I did some search on Balls and Bins problem. But I haven't found out any bounds when the number of balls ($m$) is less than the number of bins($n$). I am aware of the cases when $m \geq n$ so will ...
0
votes
0answers
159 views

Standard problem of Balls and Bins

A general classification of balls and boxes problems in combinatorics in 12 ways. There are 12 categories since 1. Balls may be distinguishable or indistinguishable; 2. Boxes may be distinguishable or ...
0
votes
0answers
117 views

balls in bins — waiting time until $k$ bins are occupied

Consider the classic balls in bins problem: we throw balls one by one into $n$ bins independently and uniformly. Define $\tau(k)$ for $1 \le k \le n$ to be the number of balls we have thrown until $k$ ...