Envelope-letter matching problem

[kingwinner]

Suppose we have "n" envelopes and "n" letters and we put letters to envelopes at random.
Let I_i = I({i-th letter matches}) =1 if the i-th letter matches and 0 otherwise.
Then I_i ~ Bernoulli(1/n) for i=1,2,...,n.
====================================

My questions:

1) So we put letters to envelopes at random one by one.
I can see that when we put the FIRST letter into an envelope(i.e. i=1), then I_1 = I({1-st letter matches})~ Bernoulli(1/n).
But I don't understand why I_i ~ Bernoulli(1/n) for i=2,3,...,n. When we put the second letter into an envelope, P({2-nd letter matches}) depends on wether the first letter matched or not, right? And P({3-rd letter matches}) depends on wether the first and second letter matched or not...etc. Then why would I_i ~ Bernoulli(1/n) still be true for i=2,3,...,n ? Could someone explain, please?


2) I assume the result I_i ~ Bernoulli(1/n) for i=1,2,...,n is true. Since p=1/n is the same for i=1,2,...n, it seems to me that the probability of a success stays constant from trail to trail at 1/n. Is it true that the "number of matches" ~ Binomial(n,1/n)? Why or why not?

Any help is greatly appreciated!

 

[mXSCNT]

1.
In general, the way for letter #i to land in envelope #i is, first the i-1 letters land in other envelopes, with probability C(n-1,i-1)/C(n,i-1), then #i lands in envelope #i with probability 1/(n-i+1). When you multiply those together you get 1/n.
Alternatively you could argue by symmetry because it doesn't matter.which letter goes in which envelope first. It's easy to see that the first letter goes in its envelope with probability 1/n, and that it makes no difference to your matching process whether you start with the first letter or the tenth, so the tenth letter also would have probability 1/n.

2. A binomial random variable is the sum of independent bernoulli variables, but these are not independent.

 

[kingwinner]

1) Let's label the letters by "1","2",...,"n".

I don't understnad your second argument based on symmetry. I agree that it's easy to see that when you put your FIRST letter into an envelope, it correrctly matches its corresponding envelope with probability 1/n, and that it makes no difference to your matching process whether you start with the first letter or the tenth. But once you start with, say, the letter labelled "10", you then put letters to envelopes one by one. When you put a second letter into an envelope (here I mean the second letter according to time order, not the letter labelled "2"), P({second letter correctly matches}) depends on whether the first letter matched or not, right? And P({third letter correctly matches}) depends on whether the first and second letter matched or not...etc? It seems to me that the probabilities depend on the outcome of the previous trials. I can't see why the probabiliity of matching the i-th letter is still 1/n.


Thanks for explaining!

 

[mXSCNT]

Well, the symmetry argument requires a leap of faith that the matching process is the same no matter which envelope you start with. The first argument doesn't require that intuition. Let me explain it in more detail.

To get letter #i in envelope #i, first, you must place the first i-1 envelopes in the n-1 OTHER slots. There are C(n-1,i-1) P(i-1) ways to do this, where C is choose and P is permute. The total number of ways to place the first i-1 envelopes while ignoring the restriction to keep envelope #i empty is C(n,i-1)P(i-1). So the probability that you successfully placed the i-1 envelopes in the n-1 other slots is C(n-1,i-1)P(i-1)/(C(n,i-1)P(i-1)) = C(n-1,i-1)/C(n,i-1) = (n-1)!(i-1)!(n-i+1)!/(n!(i-1)!(n-1-i+1)!) = (n-i+1)/n.

Next you must place letter #i in envelope #i. There are n-i+1 remaining empty envelopes, so the probability that you successfully do that is 1/(n-i+1).

Now you multiply the two probabilities together: (n-i+1)/n * 1/(n-i+1) = 1/n

 

[kingwinner]

1) Thanks, now I follow your first argument perfectly.

But I am also interested in your "symmetry" argument to justify that I_i ~ Bernoulli(1/n) for all i=1,2,...,n.
I_i = I({i-th letter matches}) =1 if the i-th letter matches and 0 otherwise.
First of all, I actually have some confusion here. Is the "i-th" here referring to the ORDER of putting the letters into the envelopes? Or is the "i-th" here referring to letter i (the letter labelled i, not necessarily the order of putting it into an envelope)?

Could you please explain a little more about the "symmetry" argument?? I do not seem to understand it fully. I agree that it doesn't matter which letter goes in which envelope first and it's easy to see that the first letter (e.g. letter 10) that you put into an envelope matches correctly (envelope 10) with probability 1/n, but how about the NEXT letter(e.g. letter 8) that you put into an envelope? It DEPENDS on the result of whether the first letter (letter 10) matched correctly or not, right? And if so, then why would the probability still be 1/n?

Thank you very much!~

 

[mXSCNT]

If you assume the intuition that the final ordering of the letters in envelopes does not depend on which letter is placed before the others, then in the ordering that starts with letter 23, letter 23 must have the same probability of going in the right envelope as it would in the ordering that starts with letter 1. The former can be easily calculated as 1/n. The latter is a little more involved, but because it is the same as the former, it must also be 1/n.