combinatorics/probability problem (1 Viewer)

[milton]

I have a problem that I've been thinking about. It seems to quite ubiquitious and generic.
I have n pigeonholes and a large number of letters. There are 2 parts to this q:

1. I take n letters and randomly put each of them in a pigeonhole. On average, what fraction of the n pigeonholes will be non-empty (i.e. have at least 1 letter each). and investigate what happens as n tends to infinity.


2. Now the pigeonholes are empty again. I randomly put each letter into a pigeonhole and keep on going until I all pigeonholes have at least 1 letter each. On average, how many letters have I used (in terms of n) and find the limit (if it exists) as n tends to infinity.

 

[jyu]

I have a problem that I've been thinking about. It seems to quite ubiquitious and generic.
I have n pigeonholes and a large number of letters. There are 2 parts to this q:

1. I take n letters and randomly put each of them in a pigeonhole. On average, what fraction of the n pigeonholes will be non-empty (i.e. have at least 1 letter each). and investigate what happens as n tends to infinity.


2. Now the pigeonholes are empty again. I randomly put each letter into a pigeonhole and keep on going until I all pigeonholes have at least 1 letter each. On average, how many letters have I used (in terms of n) and find the limit (if it exists) as n tends to infinity.

This is an investigation:

For part 1.

When n = 1, fraction = 1/1

n = 2, fraction = 2/3

n = 3, fraction = 3/5

n = 4, fraction = 4/7

n = 5, fraction = 5/9
.

.

n = n, fraction = n/(2n - 1)

As n tends to infinity, fraction = n/(2n - 1) =1/(2 - 1/n) tends to 1/2.

I shall investigate further after some sleep.

:wave:

 

[jyu]

I have a problem that I've been thinking about. It seems to quite ubiquitious and generic.
I have n pigeonholes and a large number of letters. There are 2 parts to this q:

1. I take n letters and randomly put each of them in a pigeonhole. On average, what fraction of the n pigeonholes will be non-empty (i.e. have at least 1 letter each). and investigate what happens as n tends to infinity.


2. Now the pigeonholes are empty again. I randomly put each letter into a pigeonhole and keep on going until I all pigeonholes have at least 1 letter each. On average, how many letters have I used (in terms of n) and find the limit (if it exists) as n tends to infinity.

Question 2:

From my previous post, for n = n, fraction (non-empty) = n/(2n - 1)

.: fraction (empty) = 1 - n/(2n - 1).

.: number of empty pigeonholes after the distribution of n letters
=n[1 - n/(2n - 1)].

.: number of letters in the next round of distribution
=n[1 - n/(2n - 1)].

Let f(n) = n[1 - n/(2n - 1)].


.: number of empty pigeonholes after the distribution of n[1 - n/(2n - 1)] letters = f(n[1 - n/(2n - 1)]) = f(f(n)).

.: number of letters in the next round of distribution
= f(f(n)).

This process is repeated until f(f(f(....f(n)....))) < 1.

Total number of letters = n + f(n) + f(f(n)) + f(f(f(n))) + ......

As n becomes large, 1 - n/(2n - 1) approaches 1/2, f(n) approaches n(1/2),

f(f(n)) approaches n(1/2)^2, f(f(f(n))) approaches n(1/2)^3, ......

Total number of letters = n + n(1/2) + n(1/2)^2 + n(1/2)^3 + ......
= n(1 + 1/2 + (1/2)^2 + (1/2)^3 + ......)
= 2n.

:wave: