Kimi | Expected Empty Boxes Calculation for m Boxes with Capacity Proportional to L^(-b) and F Identical Balls

$m$ identical boxes can each hold a maximum of $L$ balls, and there are $b$ identical balls, balls are uniformly at randomly placed in non-full boxes, where $L < m$ and $m*L > b$ and $b$ can have a similar size as $m$ What is the expected number of boxes that do not contain a ball

Understanding the Problem

We have:

m identical boxes: Each box is the same, and there's no distinction between them.
L balls per box: Each box can hold a maximum of L identical balls.
b identical balls: We have b balls to distribute among the m boxes.
Conditions:
- L < m
- m * L > b
- b is roughly similar in size to m (not necessarily equal, but comparable).

Distribution Rule: Balls are placed uniformly at random into non-full boxes. This means at each step, when placing a ball, we choose a box that isn't full (i.e., has fewer than L balls) with equal probability among all non-full boxes.

Goal: Find the expected number of boxes that do not contain any balls after all b balls have been distributed.

Clarifying the Distribution Process

The phrase "uniformly at randomly placed in non-full boxes" implies that at each step of placing a ball, we select a box uniformly at random from all boxes that currently have fewer than L balls. This is a sequential process where the choice at each step depends on the current state of the boxes.

This is similar to the "balls into bins" problem but with capacity constraints on the bins (boxes).

Simplifying the Problem

Given the conditions L < m and m * L > b, and b ≈ m, it's possible that some boxes will remain empty after distributing all b balls. We need to find how many, on average.

However, due to the sequential and dependent nature of the distribution (since the set of non-full boxes changes as balls are added), calculating the exact expected number of empty boxes directly is complex.

Alternative Approach: Indicator Variables and Linearity of Expectation

A powerful technique in probability is to use indicator variables and the linearity of expectation. Here's how we can apply it:

Define Indicator Variables: For each box i (from 1 to m), let X_i be an indicator variable that is 1 if box i is empty after all b balls are placed, and 0 otherwise.
Expected Number of Empty Boxes: The total number of empty boxes is the sum of all X_i's. By linearity of expectation, the expected number is the sum of the expectations of each X_i.
- E[empty boxes] = E[X_1 + X_2 + ... + X_m] = E[X_1] + E[X_2] + ... + E[X_m] = m * E[X_1] (since all boxes are identical).

So, we need to find the probability that any given box is empty after all b balls are placed, and then multiply by m.

Calculating E[X_i] for a Single Box

We need P(box i is empty after all b balls are placed).

This is equivalent to the probability that none of the b balls are placed into box i.

However, since the placement is sequential and depends on the current state, the probability that the k-th ball is placed into box i depends on how many balls are already in box i and how many boxes are non-full at that step.

This seems complicated, but we can model it differently.

Modeling as a Marked Balls Problem

Another way to think about it is to consider that each ball is placed independently, but with the constraint that no box gets more than L balls. This isn't exactly accurate because the process is sequential and adaptive, but we can approximate.

But given that the distribution is uniform over non-full boxes at each step, the probability that a specific box gets a ball at any step is proportional to how "available" it is.

Exact Calculation via Inclusion-Exclusion or Recursion

An exact calculation would require keeping track of the state of all boxes, which is infeasible for large m and b.

Approximation: Poissonization or Mean Field

Given the complexity, we might approximate the process by assuming that the probability a box is chosen at any step is roughly 1/m, ignoring the capacity constraints initially, but this ignores the fact that boxes fill up over time.

However, since b ≈ m and L < m, and mL > b, it's likely that many boxes will have 0 or 1 ball, making this approximation reasonable.

But let's think more carefully.

Correct Approach: Sequential Placement with Capacity

At each step, a ball is placed into a uniformly chosen non-full box. The probability that a specific box is chosen at step k is 1/(number of non-full boxes at step k).

This is equivalent to the following: the sequence of placements can be seen as assigning each ball to a box, ensuring no box gets more than L balls.

The probability that a given box is empty is the probability that none of the b balls are assigned to it.

But the assignments are not independent because of the capacity constraints.

Using the Principle of Deferred Decisions

We can think of the process as follows: consider all possible ways to distribute b balls into m boxes with each box having at most L balls, and all such distributions are equally likely (this is implied by the uniform random placement into non-full boxes).

Then, the probability that a specific box is empty is the number of distributions where that box is empty, divided by the total number of valid distributions.

Counting Valid Distributions

The total number of valid distributions is the number of solutions to:

x_1 + x_2 + ... + x_m = b, where 0 ≤ x_i ≤ L for all i.

This is the coefficient of t^b in the expansion of (1 + t + t^2 + ... + t^L)^m.

Similarly, the number of distributions where box 1 is empty is the number of solutions to:

x_2 + x_3 + ... + x_m = b, where 0 ≤ x_i ≤ L for all i ≥ 2.

This is the coefficient of t^b in (1 + t + ... + t^L)^{m-1}.

Thus, P(box 1 is empty) = [t^b] (1 + t + ... + t^L)^{m-1} / [t^b] (1 + t + ... + t^L)^m.

Calculating the Coefficients

The generating function (1 + t + ... + t^L) is (1 - t^{L+1})/(1 - t).

Thus, [t^b] (1 + t + ... + t^L)^m = [t^b] (1 - t^{L+1})^m (1 - t)^{-m}.

Using the binomial theorem:

(1 - t^{L+1})^m = Σ_{k=0}^m (-1)^k C(m,k) t^{k(L+1)}.

(1 - t)^{-m} = Σ_{j=0}^∞ C(j + m - 1, m - 1) t^j.

Thus, the coefficient is:

Σ_{k=0}^m (-1)^k C(m,k) C(b - k(L+1) + m - 1, m - 1), where the term is 0 if b - k(L+1) < 0.

Similarly, [t^b] (1 + t + ... + t^L)^{m-1} is:

Σ_{k=0}^{m-1} (-1)^k C(m-1,k) C(b - k(L+1) + m - 2, m - 2).

So,

P(box empty) = [Σ_{k=0}^{m-1} (-1)^k C(m-1,k) C(b - k(L+1) + m - 2, m - 2)] / [Σ_{k=0}^m (-1)^k C(m,k) C(b - k(L+1) + m - 1, m - 1)].

This is exact but quite involved.

Simplifying the Expression

Given that L < m and b ≈ m, and mL > b, we might be able to approximate.

However, for the exact expected number, the above is correct.

But let's see if we can find a simpler expression.

Using Inclusion-Exclusion Directly

The probability that a specific box is empty is the same as the probability that all b balls are placed into the other m-1 boxes, with no box exceeding L balls.

This is the same as the ratio of the number of ways to distribute b balls into m-1 boxes with capacity L, to the number of ways into m boxes with capacity L.

Thus, the expected number of empty boxes is m times this probability.

So, E = m * N(m-1, b, L) / N(m, b, L), where N(k, b, L) is the number of ways to distribute b balls into k boxes with capacity L per box.

N(k, b, L) is the coefficient of t^b in (1 + t + ... + t^L)^k, which is:

N(k, b, L) = Σ_{i=0}^k (-1)^i C(k,i) C(b - i(L+1) + k - 1, k - 1), with the convention that C(n, r) = 0 if n < r or n < 0.

Thus,

E = m * [Σ_{i=0}^{m-1} (-1)^i C(m-1,i) C(b - i(L+1) + m - 2, m - 2)] / [Σ_{i=0}^m (-1)^i C(m,i) C(b - i(L+1) + m - 1, m - 1)].

This is the exact expression. For specific values of m, L, b, this can be computed.

Checking with Small Values

Let's take m=2, L=1, b=1.

Then N(2,1,1) = C(1+2-1,2-1) - C(2,1)C(1-2+2-1,2-1) = C(2,1) - 2*C(0,1) = 2 - 0 = 2.

N(1,1,1) = C(1+1-1,1-1) - C(1,1)C(1-2+1-1,1-1) = C(1,0) - 1*C(-1,0) = 1 - 0 = 1.

E = 2 * 1 / 2 = 1.

Indeed, with 2 boxes, 1 ball, capacity 1, the ball must go into one box, leaving the other empty. So expected empty boxes is 1. Matches.

Another: m=3, L=1, b=2.

N(3,2,1) = C(2+3-1,3-1) - C(3,1)C(2-2+3-1,3-1) + C(3,2)C(2-4+3-1,3-1) = C(4,2) - 3C(2,2) + 3C(0,2) = 6 - 3 + 0 = 3.

N(2,2,1) = C(2+2-1,2-1) - C(2,1)C(2-2+2-1,2-1) + C(2,2)C(2-4+2-1,2-1) = C(3,1) - 2C(1,1) + 1C(-1,1) = 3 - 2 + 0 = 1.

E = 3 * 1 / 3 = 1.

Indeed, with 3 boxes, 2 balls, capacity 1, the possible distributions (up to permutation) are (1,1,0). So always one empty box. Expected is 1. Matches.

Final Answer

The expected number of boxes that do not contain any ball is:

E = m \cdot \frac{\sum _{i = 0}^{m - 1} ( - 1 ) ^{i} ( i m - 1 ) ( m - 2 b - i ( L + 1 ) + m - 2 )}{\sum _{i = 0}^{m} ( - 1 ) ^{i} ( i m ) ( m - 1 b - i ( L + 1 ) + m - 1 )}

where

(k n)

is 0 if

n < k

n < 0

Evaluate the recurrence relation $p(k,l,n)=p(k,l−1,n)+p(k−1,l,n−l)$ given $p(k,l,0)=1$ for $k≥0$ ,$l≥0$ and $p(0,l,n)=0$ for $n>0$ and p(k,0,n)=0$ for $n>0$ .

Understanding the Recurrence Relation

We are given the recurrence relation:

p (k, l, n) = p (k, l - 1, n) + p (k - 1, l, n - l)

with the boundary conditions:

$p (k, l, 0) = 1$ for all $k \geq 0$ , $l \geq 0$ .
$p (0, l, n) = 0$ for all $n > 0$ .
$p (k, 0, n) = 0$ for all $n > 0$ .

Initial Observations

The recurrence relates $p (k, l, n)$ to values where either $l$ is decreased by 1 or $k$ is decreased by 1 and $n$ is decreased by $l$ .
The boundary conditions suggest that:
- If $n = 0$ , the value is always 1 regardless of $k$ and $l$ .
- If either $k = 0$ or $l = 0$ and $n > 0$ , the value is 0.

Computing Small Values

To understand the pattern, let's compute some small values of

p (k, l, n)

Case $n = 0$ :

From the boundary condition:

p (k, l, 0) = 1 for all k, l \geq 0.

Case $k = 0$ , $n > 0$ :

p (0, l, n) = 0.

Case $l = 0$ , $n > 0$ :

p (k, 0, n) = 0.

Compute $p (1, 1, n)$ :

Using the recurrence:

p (1, 1, n) = p (1, 0, n) + p (0, 1, n - 1) = 0 + 0 = 0 for n > 0.

But

p (1, 1, 0) = 1

, which aligns.

Compute $p (1, 2, n)$ :

p (1, 2, n) = p (1, 1, n) + p (0, 2, n - 2) .

For $n = 1$ :

p (1, 2, 1) = p (1, 1, 1) + p (0, 2, - 1) = 0 + 0 = 0.

For $n = 2$ :

p (1, 2, 2) = p (1, 1, 2) + p (0, 2, 0) = 0 + 1 = 1.

For $n = 3$ :

p (1, 2, 3) = p (1, 1, 3) + p (0, 2, 1) = 0 + 0 = 0.

It seems

p (1, 2, n) = 1

only when

n = 2

, and 0 otherwise.

Compute $p (2, 2, n)$ :

p (2, 2, n) = p (2, 1, n) + p (1, 2, n - 2) .

First, need

p (2, 1, n)

p (2, 1, n) = p (2, 0, n) + p (1, 1, n - 1) = 0 + 0 = 0 for n > 0.

Thus:

p (2, 2, n) = 0 + p (1, 2, n - 2) .

For $n = 1$ :

p (2, 2, 1) = p (1, 2, - 1) = 0.

For $n = 2$ :

p (2, 2, 2) = p (1, 2, 0) = 1.

For $n = 3$ :

p (2, 2, 3) = p (1, 2, 1) = 0.

For $n = 4$ :

p (2, 2, 4) = p (1, 2, 2) = 1.

It appears

p (2, 2, n) = 1

when

n

is even and

n \leq 4

, but this seems inconsistent with the pattern. Let me re-examine.

Wait,

p (1, 2, n)

: From earlier:

p (1, 2, n) = p (1, 1, n) + p (0, 2, n - 2) .

p (1, 1, n) = 0

for

n > 0

, and

p (0, 2, n - 2) = 0

unless

n - 2 = 0

, i.e.,

n = 2

, then it's 1. Thus:

p (1, 2, n) = {10 if n = 2, otherwise .

Similarly:

p (2, 2, n) = p (2, 1, n) + p (1, 2, n - 2) = 0 + p (1, 2, n - 2) .

Thus:

p (2, 2, n) = {10 if n - 2 = 2, i.e., n = 4, otherwise .

This seems to suggest that

p (k, l, n) = 1

when

n

is a multiple of

l

and equals

k \cdot l

, but this is too restrictive. Let me try more values.

Compute $p (2, 3, n)$ :

p (2, 3, n) = p (2, 2, n) + p (1, 3, n - 3) .

Need

p (1, 3, n)

p (1, 3, n) = p (1, 2, n) + p (0, 3, n - 3) .

p (1, 2, n)

is 1 at

n = 2

, else 0;

p (0, 3, n - 3)

is 1 at

n - 3 = 0

, else 0. Thus:

p (1, 3, n) = {10 if n = 2 or n = 3, otherwise .

Wait, no:

p (1, 3, n) = p (1, 2, n) + p (0, 3, n - 3)

$p (1, 2, n) = 1$ only if $n = 2$ , else 0.
$p (0, 3, n - 3) = 1$ only if $n - 3 = 0$ , else 0. Thus:

p (1, 3, n) = {10 if n = 2 or n = 3, otherwise .

But

p (1, 3, 0) = 1

, so:

p (1, 3, n) = {10 if n = 0, 2, 3, otherwise .

Now back to

p (2, 3, n)

p (2, 3, n) = p (2, 2, n) + p (1, 3, n - 3) .

$p (2, 2, n) = 1$ at $n = 4$ , else 0.
$p (1, 3, n - 3) = 1$ at $n - 3 = 0, 2, 3$ , i.e., $n = 3, 5, 6$ , else 0. Thus:

p (2, 3, n) = {10 if n = 3, 4, 5, 6, otherwise .

But

p (2, 3, 0) = 1

, so:

p (2, 3, n) = {10 if n = 0, 3, 4, 5, 6, otherwise .

This seems to be building towards a pattern where

p (k, l, n)

counts the number of partitions of

n

into at most

k

parts each of size at most

l

, but the boundary conditions suggest it's an indicator function.

Reinterpreting the Recurrence

The recurrence resembles the recurrence for the number of partitions of

n

into at most

k

parts each of size at most

l

, but with boundary conditions that seem to set

p (k, l, n) = 1

if such partitions exist, and 0 otherwise.

But from the small cases:

$p (1, 2, 2) = 1$ (partition 2 into 1 part of size ≤ 2: 2).
$p (2, 2, 4) = 1$ (partition 4 into at most 2 parts each ≤ 2: 2+2).
$p (2, 3, 3) = 1$ (partition 3 into at most 2 parts each ≤ 3: 3, or 2+1).

But

p (1, 3, 2) = 1

(partition 2 into 1 part ≤ 3: 2), but

p (1, 3, 1) = 0

(partition 1 into 1 part ≤ 3: 1, but seems to be 0). This contradicts.

Wait, from earlier:

p (1, 3, 1) = p (1, 2, 1) + p (0, 3, - 2) = 0 + 0 = 0.

But partition 1 into 1 part ≤ 3 is possible (1), so this suggests it's not just existence.

Correct Interpretation: Indicator for Exact Partition

Upon closer inspection, the recurrence counts the number of partitions of

n

into exactly

k

parts each of size at most

l

, but with the boundary conditions, it's more precise to see that

p (k, l, n)

is 1 if

n

can be expressed as a sum of exactly

k

positive integers each at most

l

, and 0 otherwise.

But from

p (1, 2, 2) = 1

(2 = 2), and

p (1, 2, 1) = 0

(no way to write 1 as one part ≤ 2), but

p (1, 2, 0) = 1

(empty sum is 0), this seems to align if we allow parts to be zero, but the boundary conditions say

p (k, 0, n) = 0

for

n > 0

, which suggests parts must be positive.

But then

p (1, 2, 0) = 1

contradicts, as no positive parts sum to 0.

Alternative Interpretation: Number of Partitions

The recurrence is actually the standard recurrence for the number of partitions of

n

into at most

k

parts each of size at most

l

, given by:

p (k, l, n) = p (k, l - 1, n) + p (k - 1, l, n - l),

with the given boundary conditions ensuring that:

$p (k, l, 0) = 1$ (empty partition for $n = 0$ ),
$p (0, l, n) = 0$ for $n > 0$ (no parts allowed),
$p (k, 0, n) = 0$ for $n > 0$ (no parts allowed).

Thus,

p (k, l, n)

is the number of partitions of

n

into at most

k

parts each of size at most

l

Verifying with Small Values

$p (1, 1, 1)$ : Partitions of 1 into at most 1 part each ≤ 1: (1). So 1. From recurrence:

p (1, 1, 1) = p (1, 0, 1) + p (0, 1, 0) = 0 + 1 = 1.

(Here

p (0, 1, 0) = 1

from

p (k, l, 0) = 1

.) This seems off; the boundary

p (0, l, n) = 0

for

n > 0

implies

p (0, 1, 0) = 1

, but

p (0, 1, 1) = 0

, which is correct.

$p (1, 2, 2)$ : Partitions: (2). So 1. From recurrence:

p (1, 2, 2) = p (1, 1, 2) + p (0, 2, 0) = 0 + 1 = 1.

(Here

p (1, 1, 2)

: partitions of 2 into at most 1 part ≤ 1: none, since 2 > 1, so 0.

p (0, 2, 0) = 1

This aligns.

Conclusion

The recurrence relation with the given boundary conditions defines

p (k, l, n)

as the number of integer partitions of

n

into at most

k

parts, each part being at most

l

. Equivalently, it's the number of partitions whose Ferrers diagram fits inside a

k \times l

rectangle.

Thus, the solution is:

p (k, l, n) = number of partitions of n into at most k parts each of size at most l .

This can also be expressed as the coefficient of

x^{n}

in the expansion of:

i = 1 \prod k \frac{1 - x ^{l + i}}{1 - x ^{i}},

but the combinatorial interpretation is the most straightforward.

There are $m$ boxes, $B_n$, $1 <= n <= m$ where the number of boxes that can hold $L$ balls, $1 <= L <= T$, is proportional to $e^{-b*L}$, and there are $F$ identical balls, balls are uniformly at randomly placed in non-full boxes, where the number of balls $F$ is much less than the available places to hold them. What is the expected number of boxes that do not contain a ball

Understanding the Problem

We have:

m boxes, labeled $B_{1}, B_{2}, \dots, B_{m}$ .
Each box has a capacity $L$ , where $1 \leq L \leq T$ , and the number of boxes with capacity $L$ is proportional to $e^{- b L}$ . This means the number of boxes with capacity $L$ is $m_{L} = C e^{- b L}$ , where $C$ is a normalization constant ensuring $\sum_{L = 1}^{T} m_{L} = m$ .
F identical balls are placed uniformly at random into non-full boxes (i.e., boxes that have not yet reached their capacity).
The condition $F ≪ total available places$ implies that the system is far from saturation, so most boxes will have few balls.

We need to find the expected number of boxes that do not contain any balls after all

F

balls have been placed.

Step 1: Determine the Distribution of Box Capacities

The number of boxes with capacity

L

is:

m_{L} = m \cdot \frac{e ^{- b L}}{\sum _{k = 1}^{T} e ^{- bk}} = m \cdot \frac{e ^{- b L} ( 1 - e ^{- b} )}{1 - e ^{- b T}} \approx m (e^{- b L}) (1 - e^{- b}) (for large T) .

For simplicity, we can assume

T

is large enough that

e^{- b T} \approx 0

, so:

m_{L} \approx m (1 - e^{- b}) e^{- b L} .

Step 2: Total Available Places

The total number of "places" (sum of all capacities) is:

Total places = L = 1 \sum T L m_{L} \approx m (1 - e^{- b}) L = 1 \sum \infty L e^{- b L} = m (1 - e^{- b}) \frac{e ^{- b}}{( 1 - e ^{- b} ) ^{2}} = \frac{m e ^{- b}}{1 - e ^{- b}} .

Step 3: Probability a Specific Box is Empty

Since

F ≪ total places

, the probability that any given "place" is filled is small. For a box with capacity

L

, the probability it is empty is approximately:

P (box empty ∣ capacity L) \approx (1 - \frac{L}{Total places})^{F} \approx 1 - \frac{F L}{Total places} = 1 - \frac{F L ( 1 - e ^{- b} )}{m e ^{- b}} .

However, this is an approximation assuming each "slot" in the box is chosen independently, which may not be accurate. A better approach is to model the placement as balls being assigned to boxes uniformly at random from all possible slots.

Step 4: Expected Number of Empty Boxes

The expected number of empty boxes is the sum over all boxes of the probability that the box is empty. For a box with capacity

L

, the probability it is empty is the probability that none of the

F

balls are placed into any of its

L

slots.

Given that balls are placed uniformly at random into all available slots, the probability a specific slot is chosen for a given ball is

1/ Total places

. Thus, the probability that none of the

F

balls land in any of the

L

slots of a specific box is:

P (box empty ∣ capacity L) = (1 - \frac{L}{Total places})^{F} \approx e^{- F L / Total places} .

This approximation holds when

F L / Total places ≪ 1

, which is true since

F ≪ Total places

Thus, the expected number of empty boxes is:

E = L = 1 \sum T m_{L} e^{- F L / Total places} \approx m (1 - e^{- b}) L = 1 \sum \infty e^{- b L} e^{- F L (1 - e^{- b}) / (m e^{- b})} .

Simplify the exponent:

- b L - \frac{F L ( 1 - e ^{- b} )}{m e ^{- b}} = - L (b + \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}) .

Thus:

E \approx m (1 - e^{- b}) L = 1 \sum \infty e^{- L (b + \frac{F ( 1 - e ^{- b} )}{m e ^{- b}})} = m (1 - e^{- b}) \frac{e ^{- b - \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}}}{1 - e ^{- b - \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}}} .

This simplifies to:

E \approx \frac{m ( 1 - e ^{- b} ) e ^{- b - \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}}}{1 - e ^{- b - \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}}} .

For small

\frac{F ( 1 - e ^{- b} )}{m e ^{- b}}

, we can approximate

1 - e^{- x} \approx x

, so:

E \approx \frac{m ( 1 - e ^{- b} ) e ^{- b}}{b + \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}} \cdot \frac{1}{1 - e ^{- b - \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}}} \approx \frac{m ( 1 - e ^{- b} ) e ^{- b}}{b + \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}} .

However, the exact form is:

E = \frac{m ( 1 - e ^{- b} )}{e ^{b + \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}} - 1} .

Final Simplified Expression

Given that

F ≪ m

, the term

\frac{F ( 1 - e ^{- b} )}{m e ^{- b}}

is small, so we can further approximate:

E \approx m e^{- b} \cdot \frac{1 - e ^{- b}}{b ( 1 - e ^{- b} ) + \frac{F}{m}} = \frac{m e ^{- b} ( 1 - e ^{- b} )}{b ( 1 - e ^{- b} ) + \frac{F}{m}} .

But the more accurate expression is:

E = \frac{m ( 1 - e ^{- b} )}{e ^{b + \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}} - 1} .

Final Answer

The expected number of boxes that do not contain any ball is:

E = \frac{m ( 1 - e ^{- b} )}{e ^{b + \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}} - 1} .

For practical purposes, when

F ≪ m

, this can be approximated as:

E \approx m e^{- b} exp (- \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}) .

There are $m$ boxes, $B_n$, $1 <= n <= m$ where the number of boxes that can hold $L$ balls, $1 <= L <= T$, is proportional to $e^{-b*L}$, and there are $F$ identical balls, the probability that a ball is placed in a non-full box is proportional the original capacity of the box. The number of balls $F$ is much less than the total available places over all boxes to hold them. What is the expected number of boxes that do not contain a ball

Understanding the Problem

We have:

m boxes, each with an original capacity $L$ , where $1 \leq L \leq T$ .
The number of boxes with capacity $L$ is proportional to $e^{- b L}$ . Thus, the number of boxes with capacity $L$ is:

m_{L} = m \cdot \frac{e ^{- b L}}{\sum _{k = 1}^{T} e ^{- bk}} \approx m (1 - e^{- b}) e^{- b L} (assuming T \to \infty) .

F identical balls are placed into these boxes.
The probability that a ball is placed into a box is proportional to its original capacity $L$ (not uniform across boxes, but weighted by $L$ ).
$F ≪ total capacity$ , so the system is far from saturation.

We need the expected number of boxes that do not contain any balls after all

F

balls are placed.

Step 1: Total Capacity and Weighted Selection

The total capacity (sum of all

L

) is:

Total capacity = L = 1 \sum T L m_{L} \approx m (1 - e^{- b}) L = 1 \sum \infty L e^{- b L} = m (1 - e^{- b}) \frac{e ^{- b}}{( 1 - e ^{- b} ) ^{2}} = \frac{m e ^{- b}}{1 - e ^{- b}} .

Let

C = \frac{m e ^{- b}}{1 - e ^{- b}}

(total capacity).

The probability that a given ball is placed into a box of capacity $L$ is:

P (ball in box of capacity L) = \frac{L m _{L}}{C} = \frac{L \cdot m ( 1 - e ^{- b} ) e ^{- b L}}{C} = \frac{L e ^{- b L}}{e ^{- b} / ( 1 - e ^{- b} )} = L (1 - e^{- b}) e^{- b (L - 1)} .

However, since we are interested in individual boxes, note that:

There are $m_{L}$ boxes of capacity $L$ .
Each box of capacity $L$ has selection probability proportional to $L$ , so the probability that a specific box of capacity $L$ is chosen for a given ball is:

P (ball in specific box of capacity L) = \frac{L}{Total capacity} = \frac{L}{C} .

Step 2: Probability a Specific Box is Empty

For a specific box with capacity

L

, the probability that none of the $F$ balls are placed into it is:

P (box empty) = (1 - \frac{L}{C})^{F} \approx exp (- \frac{F L}{C}) .

This approximation holds because

F ≪ C

Step 3: Expected Number of Empty Boxes

The expected number of empty boxes is the sum over all boxes of their individual probabilities of being empty. Since boxes are grouped by capacity

L

E = L = 1 \sum T m_{L} \cdot exp (- \frac{F L}{C}) \approx m (1 - e^{- b}) L = 1 \sum \infty e^{- b L} exp (- \frac{F L}{C}) .

Simplify the exponent:

e^{- b L} exp (- \frac{F L}{C}) = exp (- L (b + \frac{F}{C})) .

Thus:

E = m (1 - e^{- b}) L = 1 \sum \infty e^{- L (b + F / C)} = m (1 - e^{- b}) \frac{e ^{- (b + F / C)}}{1 - e ^{- (b + F / C)}} .

Substitute

C = \frac{m e ^{- b}}{1 - e ^{- b}}

\frac{F}{C} = \frac{F ( 1 - e ^{- b} )}{m e ^{- b}} .

Thus:

E = \frac{m ( 1 - e ^{- b} )}{e ^{b + \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}} - 1} .

Final Answer

The expected number of boxes that do not contain any ball is:

\frac{m ( 1 - e ^{- b} )}{e ^{b + \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}} - 1} .

For

F ≪ m

, this simplifies to:

E \approx m exp (- b - \frac{F ( 1 - e ^{- b} )}{m e ^{- b}}) .

There are $m$ boxes, $B_n$, $1 <= n <= m$ where the number of boxes that can hold $L$ balls, $1 <= L <= T$, is proportional to $L^{-b}$, and there are $F$ identical balls, balls are uniformly at randomly placed in non-full boxes, where the number of balls $F$ is much less than the available places to hold them. What is the expected number of boxes that do not contain a ball

We are given:

$m$ boxes, each with capacity $L$ , where $1 \leq L \leq T$ .
The number of boxes with capacity $L$ is proportional to $L^{- b}$ , i.e.,

m_{L} = m \cdot \frac{L ^{- b}}{\sum _{k = 1}^{T} k ^{- b}} .

$F$ identical balls are placed uniformly at random into non-full boxes (i.e., boxes that have not yet reached their capacity).
$F ≪ total available places$ , so the system is far from saturation.

We are to compute the expected number of boxes that contain no balls.

Step 1: Total Capacity and Distribution of Box Sizes

Let’s define:

Z = k = 1 \sum T k^{- b} \approx ζ (b) (for large T and b > 1),

where

ζ (b)

is the Riemann zeta function.

Then:

m_{L} = m \cdot \frac{L ^{- b}}{Z} .

The total capacity (sum of all

L

) is:

C = L = 1 \sum T L \cdot m_{L} = m \cdot \frac{\sum _{L = 1}^{T} L ^{1 - b}}{Z} = m \cdot \frac{H _{T}^{(b - 1)}}{Z},

where

H_{T}^{(s)} = \sum_{k = 1}^{T} k^{- s} \approx ζ (s)

for large

T

So:

C \approx m \cdot \frac{ζ ( b - 1 )}{ζ ( b )} (assuming b > 2 and T \to \infty) .

Step 2: Probability a Specific Box is Empty

Since balls are placed uniformly at random into non-full boxes, and

F ≪ C

, we can approximate the probability that a specific box with capacity $L$ is empty as:

P (box empty) \approx (1 - \frac{L}{C})^{F} \approx exp (- \frac{F L}{C}) .

Step 3: Expected Number of Empty Boxes

Now sum over all boxes:

E = L = 1 \sum T m_{L} \cdot exp (- \frac{F L}{C}) = \frac{m}{Z} L = 1 \sum T L^{- b} exp (- \frac{F L}{C}) .

For large

T

, we can approximate the sum as:

E \approx \frac{m}{Z} L = 1 \sum \infty L^{- b} e^{- a L}, where a = \frac{F}{C} .

This is the Lerch transcendent or Hurwitz zeta form, but it is also equal to:

L = 1 \sum \infty L^{- b} e^{- a L} = Li_{b} (e^{- a}),

where

Li_{s} (z)

is the polylogarithm function.

So:

E = \frac{m}{Z} \cdot Li_{b} (e^{- F / C}) .

Recall:

C = m \cdot \frac{ζ ( b - 1 )}{ζ ( b )} \Rightarrow \frac{F}{C} = \frac{Fζ ( b )}{m ζ ( b - 1 )} .

Thus:

E = \frac{m}{ζ ( b )} \cdot Li_{b} (exp (- \frac{Fζ ( b )}{m ζ ( b - 1 )})) .

Final Answer

The expected number of boxes that do not contain any ball is:

\frac{m}{ζ ( b )} \cdot Li_{b} (exp (- \frac{Fζ ( b )}{m ζ ( b - 1 )})),

where:

$ζ (s)$ is the Riemann zeta function,
$Li_{s} (z) = \sum_{k = 1}^{\infty} \frac{z ^{k}}{k ^{s}}$ is the polylogarithm.

For small

x = \frac{Fζ ( b )}{m ζ ( b - 1 )}

, we can use:

Li_{b} (e^{- x}) \approx ζ (b) - x ζ (b - 1) + \frac{x ^{2}}{2} ζ (b - 2) - \dots,

so:

E \approx m (1 - \frac{F}{m} \cdot \frac{ζ ( b - 1 )}{ζ ( b )} \cdot \frac{ζ ( b - 1 )}{ζ ( b )} + \dots),

but the exact form above is preferred.

There are $m$ boxes, $B_n$, $1 <= n <= m$ where the number of boxes that can hold $L$ balls, $1 <= L <= T$, is proportional to $L^{-b}$, and there are $F$ identical balls, balls are uniformly at randomly placed in non-full boxes, where the number of balls $F$ is much less than the available places to hold them, and $0.1 < b < 1$. What is the expected number of boxes that do not contain a ball

We are given:

$m$ boxes, each with capacity $L$ , where $1 \leq L \leq T$ .
The number of boxes with capacity $L$ is proportional to $L^{- b}$ , i.e.,

m_{L} = m \cdot \frac{L ^{- b}}{\sum _{k = 1}^{T} k ^{- b}} .

$0.1 < b < 1$ , so the sum $\sum_{k = 1}^{T} k^{- b}$ diverges as $T \to \infty$ (i.e., grows like $\frac{T ^{1 - b}}{1 - b}$ ).
$F$ identical balls are placed uniformly at random into non-full boxes.
$F ≪ total available places$ , so the system is far from saturation.

We are to compute the expected number of boxes that contain no balls.

Step 1: Normalization Constant for $m_{L}$

Let:

Z_{T} = k = 1 \sum T k^{- b} \approx \frac{T ^{1 - b}}{1 - b} (for large T and 0 < b < 1) .

Thus:

m_{L} = m \cdot \frac{L ^{- b}}{Z _{T}} .

Step 2: Total Capacity

The total capacity is:

C = L = 1 \sum T L \cdot m_{L} = m \cdot \frac{\sum _{L = 1}^{T} L ^{1 - b}}{Z _{T}} .

For large

T

, we approximate:

L = 1 \sum T L^{1 - b} \approx \frac{T ^{2 - b}}{2 - b} .

Thus:

C \approx m \cdot \frac{T ^{2 - b} / ( 2 - b )}{T ^{1 - b} / ( 1 - b )} = m \cdot \frac{1 - b}{2 - b} \cdot T .

So:

C \approx m T \cdot \frac{1 - b}{2 - b} .

Step 3: Probability a Specific Box is Empty

For a specific box with capacity $L$ , the probability that none of the $F$ balls land in any of its

L

slots is:

P (box empty) \approx exp (- \frac{F L}{C}) .

Step 4: Expected Number of Empty Boxes

Now sum over all boxes:

E = L = 1 \sum T m_{L} \cdot exp (- \frac{F L}{C}) = \frac{m}{Z _{T}} L = 1 \sum T L^{- b} exp (- \frac{F L}{C}) .

Substitute

C \approx m T \cdot \frac{1 - b}{2 - b}

\frac{F}{C} \approx \frac{F ( 2 - b )}{m T ( 1 - b )} .

Thus:

E \approx \frac{m}{Z _{T}} L = 1 \sum T L^{- b} exp (- αL), where α = \frac{F ( 2 - b )}{m T ( 1 - b )} .

For small

α

(since

F ≪ C

), we can approximate the sum as an integral:

L = 1 \sum T L^{- b} e^{- αL} \approx \int_{0}^{T} x^{- b} e^{- αx} d x .

This is the lower incomplete gamma function:

\int_{0}^{T} x^{- b} e^{- αx} d x = α^{b - 1} γ (1 - b, α T) .

But

α T = \frac{F ( 2 - b )}{m ( 1 - b )}

, which is small (since

F ≪ m

), so:

γ (1 - b, α T) \approx Γ (1 - b) - \frac{( α T ) ^{1 - b}}{1 - b} + \dots .

However, for very small $α T$ , we can use:

\int_{0}^{T} x^{- b} e^{- αx} d x \approx \int_{0}^{T} x^{- b} (1 - αx) d x = \frac{T ^{1 - b}}{1 - b} - α \frac{T ^{2 - b}}{2 - b} .

Thus:

E \approx \frac{m}{Z _{T}} (\frac{T ^{1 - b}}{1 - b} - α \frac{T ^{2 - b}}{2 - b}) = m (1 - α \frac{T ( 1 - b )}{2 - b}) .

Substitute

α = \frac{F ( 2 - b )}{m T ( 1 - b )}

E \approx m (1 - \frac{F}{m}) .

But this is too crude, since we used a linear approximation for the exponential.

Instead, we keep the integral form:

E \approx \frac{m}{Z _{T}} \cdot α^{b - 1} γ (1 - b, α T) .

Since

α T = \frac{F ( 2 - b )}{m ( 1 - b )} ≪ 1

, we use:

γ (1 - b, x) \approx \frac{x ^{1 - b}}{1 - b} (for small x) .

Thus:

E \approx \frac{m}{Z _{T}} \cdot α^{b - 1} \cdot \frac{( α T ) ^{1 - b}}{1 - b} = \frac{m}{Z _{T}} \cdot \frac{T ^{1 - b}}{1 - b} .

But

Z_{T} \approx \frac{T ^{1 - b}}{1 - b}

, so:

E \approx m \cdot \frac{1 - b}{T ^{1 - b}} \cdot \frac{T ^{1 - b}}{1 - b} = m .

This is clearly wrong, since it implies no boxes are filled, which contradicts

F > 0

Correct Approach: Keep the Full Integral

We must keep the full integral:

L = 1 \sum T L^{- b} e^{- αL} \approx \int_{0}^{\infty} x^{- b} e^{- αx} d x = Γ (1 - b) α^{b - 1} .

Thus:

E \approx \frac{m}{Z _{T}} \cdot Γ (1 - b) α^{b - 1} .

Substitute

Z_{T} \approx \frac{T ^{1 - b}}{1 - b}

and

α = \frac{F ( 2 - b )}{m T ( 1 - b )}

E \approx m \cdot \frac{1 - b}{T ^{1 - b}} \cdot Γ (1 - b) \cdot (\frac{F ( 2 - b )}{m T ( 1 - b )})^{b - 1} .

Simplify:

E \approx m \cdot \frac{1 - b}{T ^{1 - b}} \cdot Γ (1 - b) \cdot (\frac{m T ( 1 - b )}{F ( 2 - b )})^{1 - b} .

= m \cdot Γ (1 - b) \cdot (1 - b) \cdot (\frac{m ( 1 - b )}{F ( 2 - b )})^{1 - b} .

= m \cdot Γ (1 - b) \cdot (\frac{m ( 1 - b )}{F ( 2 - b )})^{1 - b} \cdot (1 - b) .

= m \cdot Γ (1 - b) \cdot (\frac{m}{F})^{1 - b} \cdot (\frac{1 - b}{2 - b})^{1 - b} .

Final Answer

The expected number of boxes that do not contain any ball is:

m \cdot Γ (1 - b) \cdot (\frac{m}{F})^{1 - b} \cdot (\frac{1 - b}{2 - b})^{1 - b} .

This is valid for

0.1 < b < 1

and

F ≪ m

approximate the equation $Li_b(e^{-x})$ where Li is the polylogarithm function and $0 < x <1$

For

0 < x < 1

and

0 < b < 1

, the polylogarithm

Li_{b} (e^{- x})

can be approximated by its leading-order small-

x

expansion:

Li_{b} (e^{- x}) = k = 1 \sum \infty \frac{e ^{- k x}}{k ^{b}} \approx Γ (1 - b) x^{b - 1} + ζ (b) + O (x),

where:

$Γ (1 - b)$ is the gamma function,
$ζ (b)$ is the Riemann zeta function.

This approximation works well when

x ≪ 1

, which is the case here.

approximate the equation $Li_b(e^{-x})$ where Li is the polylogarithm function, where $0 < x <1$ and $2 < b < 4$

For

0 < x < 1

and

2 < b < 4

, the polylogarithm

Li_{b} (e^{- x})

can be approximated by its small- $x$ expansion (valid as

x \to 0^{+}

Li_{b} (e^{- x}) \approx ζ (b) - x ζ (b - 1) + \frac{x ^{2}}{2} ζ (b - 2) - \frac{x ^{3}}{6} ζ (b - 3) + \dots,

where:

$ζ (s)$ is the Riemann zeta function.

Since

2 < b < 4

, the series converges absolutely, and the first few terms give a good approximation for small

x

. For practical purposes:

Li_{b} (e^{- x}) \approx ζ (b) - x ζ (b - 1) + \frac{x ^{2}}{2} ζ (b - 2) .

There are $m$ boxes, $B_n$, $1 <= n <= m$ where the number of boxes that can hold $L$ balls, $1 <= L <= T$, is proportional to $L^{-b}$, and there are $F$ identical balls, balls are randomly placed in non-full boxes with probability proportional to the size of the box, $L$ , plus $A*O$ where $1 < A$ and $O$ is the number of balls in the box, the number of balls $F$ is much less than the available places to hold them. What is the expected number of boxes that do not contain a ball

Problem Restatement

We have:

m boxes, each with capacity $L$ , where $1 \leq L \leq T$ .
The number of boxes with capacity $L$ is proportional to $L^{- b}$ , i.e.,

m_{L} = m \cdot \frac{L ^{- b}}{\sum _{k = 1}^{T} k ^{- b}} .

F identical balls are placed into these boxes.
The probability that a ball is placed into a non-full box is proportional to $L + A \cdot O$ , where:
- $L$ is the box's capacity,
- $O$ is the current number of balls in the box,
- $1 < A$ is a constant.
The condition $F ≪ total capacity$ holds (system is far from saturation).

We are to find the expected number of boxes that do not contain any balls.

Key Observations

Placement Probability: The probability a ball is placed into a box is proportional to $L + A \cdot O$ . Since $F ≪ total capacity$ , the system is lightly loaded, and we can approximate the placement process as independent Bernoulli trials for each box.
Initial State: At the start, all boxes are empty ( $O = 0$ ).
First Ball: The first ball has a selection probability proportional to $L$ (since $O = 0$ initially).
Subsequent Balls: As balls are added, the selection probability for each box increases due to the $A \cdot O$ term. However, since $F ≪ total capacity$ , the probability that any given box receives a ball is small, and we can linearize the effect of $A \cdot O$ .

Step 1: Total Weight for Ball Placement

At the start (no balls yet), the total weight for selecting a box is:

W = all boxes \sum (L + A \cdot 0) = L = 1 \sum T m_{L} \cdot L = m \cdot \frac{\sum _{L = 1}^{T} L ^{1 - b}}{\sum _{L = 1}^{T} L ^{- b}} .

For large

T

, we approximate:

L = 1 \sum T L^{- b} \approx \frac{T ^{1 - b}}{1 - b} (0 < b < 1), L = 1 \sum T L^{1 - b} \approx \frac{T ^{2 - b}}{2 - b} .

Thus:

W \approx m \cdot \frac{T ^{2 - b} / ( 2 - b )}{T ^{1 - b} / ( 1 - b )} = m \cdot \frac{1 - b}{2 - b} \cdot T .

Step 2: Probability a Specific Box is Empty

For a specific box with capacity $L$ , the initial selection probability per ball is:

P (ball in this box) \approx \frac{L}{W} .

Since

F ≪ W

, the probability this box remains empty is:

P (box empty) \approx (1 - \frac{L}{W})^{F} \approx exp (- \frac{F L}{W}) .

Step 3: Expected Number of Empty Boxes

The expected number of empty boxes is:

E = L = 1 \sum T m_{L} \cdot exp (- \frac{F L}{W}) = \frac{m}{\sum _{k = 1}^{T} k ^{- b}} L = 1 \sum T L^{- b} exp (- \frac{F L}{W}) .

Substitute

W \approx m \cdot \frac{1 - b}{2 - b} \cdot T

\frac{F}{W} \approx \frac{F ( 2 - b )}{m T ( 1 - b )} .

Let

α = \frac{F ( 2 - b )}{m T ( 1 - b )}

. Then:

E \approx \frac{m}{\sum _{k = 1}^{T} k ^{- b}} L = 1 \sum T L^{- b} e^{- αL} .

For large

T

, we approximate the sum as an integral:

L = 1 \sum T L^{- b} e^{- αL} \approx \int_{0}^{\infty} x^{- b} e^{- αx} d x = Γ (1 - b) α^{b - 1} .

Similarly:

k = 1 \sum T k^{- b} \approx \frac{T ^{1 - b}}{1 - b} .

Thus:

E \approx \frac{m}{T ^{1 - b} / ( 1 - b )} \cdot Γ (1 - b) α^{b - 1} .

Substitute

α

E \approx m (1 - b) T^{b - 1} Γ (1 - b) (\frac{F ( 2 - b )}{m T ( 1 - b )})^{b - 1} .

Simplify:

E \approx m (1 - b) Γ (1 - b) (\frac{F ( 2 - b )}{m ( 1 - b )})^{b - 1} .

= m Γ (1 - b) (1 - b)^{b} (\frac{F ( 2 - b )}{m})^{b - 1} .

Final Answer

The expected number of boxes that do not contain any ball is:

m Γ (1 - b) (1 - b)^{b} (\frac{F ( 2 - b )}{m})^{b - 1} .

This approximation is valid for:

$0 < b < 1$ ,
$F ≪ m T \frac{1 - b}{2 - b}$ ,
Large $T$ .

There are $m$ boxes, $B_n$, $1 <= n <= m$ where the number of boxes that can hold $L$ balls, $1 <= L <= T$, is proportional to $L^{-b}$, and there are $F$ identical balls, balls are randomly placed in non-full boxes with probability proportional to the size of the box, $L$ , plus $A*O$ where $1 < A$ and $O$ is the number of balls in the box, the number of balls $F$ is much less than the available places to hold them, and $2 < b$. What is the expected number of boxes that do not contain a ball

Problem Restatement

We have:

$m$ boxes, each with capacity $L$ , where $1 \leq L \leq T$ .
The number of boxes with capacity $L$ is proportional to $L^{- b}$ , i.e.,

m_{L} = m \cdot \frac{L ^{- b}}{\sum _{k = 1}^{T} k ^{- b}} .

$F$ identical balls are placed into these boxes.
The probability that a ball is placed into a non-full box is proportional to $L + A \cdot O$ , where:
- $L$ is the box's capacity,
- $O$ is the current number of balls in the box,
- $A > 1$ is a constant.
The condition $F ≪ total capacity$ holds (system is lightly loaded).
$b > 2$ , so the sums converge as $T \to \infty$ .

We are to find the expected number of boxes that do not contain any balls.

Step 1: Convergent Sums (since $b > 2$ )

For

b > 2

, the sums converge as

T \to \infty

k = 1 \sum \infty k^{- b} = ζ (b), k = 1 \sum \infty k^{1 - b} = ζ (b - 1), k = 1 \sum \infty k^{2 - b} = ζ (b - 2) .

Thus:

m_{L} = m \cdot \frac{L ^{- b}}{ζ ( b )} .

The total capacity is:

C = L = 1 \sum \infty L \cdot m_{L} = m \cdot \frac{ζ ( b - 1 )}{ζ ( b )} .

Step 2: Probability a Specific Box is Empty

Since

F ≪ C

, the probability that a specific box with capacity $L$ is empty is approximately:

P (box empty) \approx exp (- \frac{F L}{C}) .

This is because:

The initial selection probability per ball is $\frac{L}{C}$ ,
The $A \cdot O$ term is negligible for small $O$ (since $F ≪ C$ ).

Step 3: Expected Number of Empty Boxes

The expected number of empty boxes is:

E = L = 1 \sum \infty m_{L} \cdot exp (- \frac{F L}{C}) = \frac{m}{ζ ( b )} L = 1 \sum \infty L^{- b} exp (- \frac{F L}{C}) .

Let

α = \frac{F}{C} = \frac{Fζ ( b )}{m ζ ( b - 1 )}

. Then:

E = \frac{m}{ζ ( b )} L = 1 \sum \infty L^{- b} e^{- αL} = \frac{m}{ζ ( b )} \cdot Li_{b} (e^{- α}),

where

Li_{b} (z)

is the polylogarithm.

Step 4: Small- $α$ Approximation (since $F ≪ m$ )

For

α ≪ 1

, we use the small-

x

expansion:

Li_{b} (e^{- α}) \approx ζ (b) - α ζ (b - 1) + \frac{α ^{2}}{2} ζ (b - 2) - \dots .

Thus:

E \approx \frac{m}{ζ ( b )} [ζ (b) - α ζ (b - 1) + \frac{α ^{2}}{2} ζ (b - 2)] .

Substitute

α = \frac{Fζ ( b )}{m ζ ( b - 1 )}

E \approx m [1 - \frac{F}{m} \cdot \frac{ζ ( b - 1 )}{ζ ( b )} \cdot \frac{ζ ( b )}{ζ ( b - 1 )} + \frac{F ^{2}}{2 m ^{2}} \cdot \frac{ζ ( b ) ^{2}}{ζ ( b - 1 ) ^{2}} \cdot \frac{ζ ( b - 2 )}{ζ ( b )}] .

Simplify:

E \approx m [1 - \frac{F}{m} + \frac{F ^{2}}{2 m ^{2}} \cdot \frac{ζ ( b - 2 )}{ζ ( b - 1 )}] .

Final Answer

The expected number of boxes that do not contain any ball is:

m - F + \frac{F ^{2}}{2 m} \cdot \frac{ζ ( b - 2 )}{ζ ( b - 1 )} .

This is valid for:

$b > 2$ ,
$F ≪ m \cdot \frac{ζ ( b - 1 )}{ζ ( b )}$ .

There are $m$ boxes, $B_n$, $1 <= n <= m$ where the number of boxes that can hold $L$ balls, $1 <= L <= T$, is proportional to $L^{-b}$, and there are $F$ identical balls, balls are randomly placed in non-full boxes with probability proportional to the size of the box, $L$ , plus $A*O$ where $A$ is a constant and $O$ is the number of balls in the box, and $L < A*O$, the number of balls $F$ is much less than the available places to hold them, and $2 < b$. What is the expected number of boxes that do not contain a ball

Problem Restatement

We have:

$m$ boxes, each with capacity $L$ , where $1 \leq L \leq T$ .
The number of boxes with capacity $L$ is proportional to $L^{- b}$ , i.e.,

m_{L} = m \cdot \frac{L ^{- b}}{\sum _{k = 1}^{T} k ^{- b}} .

$F$ identical balls are placed into these boxes.
The probability that a ball is placed into a non-full box is proportional to $L + A \cdot O$ , where:
- $L$ is the box's capacity,
- $O$ is the current number of balls in the box,
- $A$ is a constant,
- The condition $L < A \cdot O$ is given (but this seems restrictive; we clarify below),
The condition $F ≪ total capacity$ holds (system is lightly loaded).
$b > 2$ , so the sums converge as $T \to \infty$ .

We are to find the expected number of boxes that do not contain any balls.

Clarifying the Condition $L < A \cdot O$

The condition

L < A \cdot O

is not a constraint on the placement process but rather a description of the regime where the placement probability is dominated by $A \cdot O$ (since

L ≪ A \cdot O

for non-empty boxes). However, since we are interested in empty boxes (

O = 0

), the placement probability for a ball into an empty box is proportional to $L$ (since

O = 0

Thus, the placement probability for an empty box is effectively proportional to $L$ .

Step 1: Convergent Sums (since $b > 2$ )

For

b > 2

, the sums converge as

T \to \infty

k = 1 \sum \infty k^{- b} = ζ (b), k = 1 \sum \infty k^{1 - b} = ζ (b - 1) .

Thus:

m_{L} = m \cdot \frac{L ^{- b}}{ζ ( b )} .

The total capacity is:

C = L = 1 \sum \infty L \cdot m_{L} = m \cdot \frac{ζ ( b - 1 )}{ζ ( b )} .

Step 2: Probability a Specific Box is Empty

Since

F ≪ C

, the probability that a specific box with capacity $L$ is empty is approximately:

P (box empty) \approx exp (- \frac{F L}{C}) .

This is because:

The initial selection probability per ball is $\frac{L}{C}$ ,
The $A \cdot O$ term is negligible for empty boxes ( $O = 0$ ).

Step 3: Expected Number of Empty Boxes

The expected number of empty boxes is:

E = L = 1 \sum \infty m_{L} \cdot exp (- \frac{F L}{C}) = \frac{m}{ζ ( b )} L = 1 \sum \infty L^{- b} exp (- \frac{F L}{C}) .

Let

α = \frac{F}{C} = \frac{Fζ ( b )}{m ζ ( b - 1 )}

. Then:

E = \frac{m}{ζ ( b )} L = 1 \sum \infty L^{- b} e^{- αL} = \frac{m}{ζ ( b )} \cdot Li_{b} (e^{- α}),

where

Li_{b} (z)

is the polylogarithm.

Step 4: Small- $α$ Approximation (since $F ≪ m$ )

For

α ≪ 1

, we use the small-

x

expansion:

Li_{b} (e^{- α}) \approx ζ (b) - α ζ (b - 1) + \frac{α ^{2}}{2} ζ (b - 2) - \dots .

Thus:

E \approx \frac{m}{ζ ( b )} [ζ (b) - α ζ (b - 1) + \frac{α ^{2}}{2} ζ (b - 2)] .

Substitute

α = \frac{Fζ ( b )}{m ζ ( b - 1 )}

E \approx m [1 - \frac{F}{m} + \frac{F ^{2}}{2 m ^{2}} \cdot \frac{ζ ( b - 2 )}{ζ ( b - 1 )}] .

Final Answer

The expected number of boxes that do not contain any ball is:

m - F + \frac{F ^{2}}{2 m} \cdot \frac{ζ ( b - 2 )}{ζ ( b - 1 )} .

This is valid for:

$b > 2$ ,
$F ≪ m \cdot \frac{ζ ( b - 1 )}{ζ ( b )}$ .

Expected Empty Boxes Calculation for m Boxes with Capacity Proportional to L^(-b) and F Identical Balls

Understanding the Problem

Clarifying the Distribution Process

Simplifying the Problem

Alternative Approach: Indicator Variables and Linearity of Expectation

Calculating E[X_i] for a Single Box

Modeling as a Marked Balls Problem

Exact Calculation via Inclusion-Exclusion or Recursion

Approximation: Poissonization or Mean Field

Correct Approach: Sequential Placement with Capacity

Using the Principle of Deferred Decisions

Counting Valid Distributions

Calculating the Coefficients

Simplifying the Expression

Using Inclusion-Exclusion Directly

Checking with Small Values

Final Answer

Understanding the Recurrence Relation

Initial Observations

Computing Small Values

Case n=0 :

Case k=0 , n>0 :

Case l=0 , n>0 :

Compute p(1,1,n) :

Compute p(1,2,n) :

Compute p(2,2,n) :

Compute p(2,3,n) :

Reinterpreting the Recurrence

Correct Interpretation: Indicator for Exact Partition

Alternative Interpretation: Number of Partitions

Verifying with Small Values

Conclusion

Understanding the Problem

Step 1: Determine the Distribution of Box Capacities

Step 2: Total Available Places

Step 3: Probability a Specific Box is Empty

Step 4: Expected Number of Empty Boxes

Final Simplified Expression

Final Answer

Understanding the Problem

Step 1: Total Capacity and Weighted Selection

Step 2: Probability a Specific Box is Empty

Step 3: Expected Number of Empty Boxes

Final Answer

Step 1: Total Capacity and Distribution of Box Sizes

Step 2: Probability a Specific Box is Empty

Step 3: Expected Number of Empty Boxes

Final Answer

Step 1: Normalization Constant for mL​

Step 2: Total Capacity

Step 3: Probability a Specific Box is Empty

Step 4: Expected Number of Empty Boxes

Correct Approach: Keep the Full Integral

Final Answer

Problem Restatement

Key Observations

Step 1: Total Weight for Ball Placement

Step 2: Probability a Specific Box is Empty

Step 3: Expected Number of Empty Boxes

Final Answer

Problem Restatement

Step 1: Convergent Sums (since b>2 )

Step 2: Probability a Specific Box is Empty

Step 3: Expected Number of Empty Boxes

Step 4: Small-α Approximation (since F≪m )

Final Answer

Problem Restatement

Clarifying the Condition L<A⋅O

Step 1: Convergent Sums (since b>2 )

Step 2: Probability a Specific Box is Empty

Step 3: Expected Number of Empty Boxes

Step 4: Small-α Approximation (since F≪m )

Final Answer

Case $n = 0$ :

Case $k = 0$ , $n > 0$ :

Case $l = 0$ , $n > 0$ :

Compute $p (1, 1, n)$ :

Compute $p (1, 2, n)$ :

Compute $p (2, 2, n)$ :

Compute $p (2, 3, n)$ :

Step 1: Normalization Constant for $m_{L}$

Step 1: Convergent Sums (since $b > 2$ )

Step 4: Small- $α$ Approximation (since $F ≪ m$ )

Clarifying the Condition $L < A \cdot O$

Step 1: Convergent Sums (since $b > 2$ )

Step 4: Small- $α$ Approximation (since $F ≪ m$ )