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 (second according to time order) 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!Please Register or Log in to view the hidden image!
You're correct, but you're being asked for the probability distribution for I[sub]i[/sub] given no knowledge about whether the other letters were matched correctly. The problem just states that a bunch of letters are randomly assigned to the envelopes. What you're sensing intuitively is that the I[sub]i[/sub]'s aren't independent random variables. There are correlations (dependencies) between them. For example, it is impossible for all but one of the letters to be matched to the correct envelope. (Note: I'm assuming that the letters are matched one-to-one with the envelopes, ie. no envelope contains two letters). Well the sum of identically distributed Bernouilli variables is only binomially distributed if the Bernouilli's are independent variables...
Let's label the letters by "1","2",...,"n". 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. Now you have n-1 letters left and when you put a second letter into an envelope (here I mean the second letter according to time order, not necessarily 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 don't see why the probabiliity of matching the i-th letter is still 1/n. Thanks for explaining!Please Register or Log in to view the hidden image!
Use Email! Please Register or Log in to view the hidden image! Please Register or Log in to view the hidden image!
Let's say there are 10 letters and envelopes (n = 10), and consider what happens for the second one as a particular illustrative example. There are three possibilities: Letter #1 was matched correctly. There was a probability of 1 in 10 of this happening, and now there's a probability of 1 in 9 that letter #2 will be matched correctly. Letter #1 was incorrectly placed in envelope #2. There was a probability of 1 in 10 of this happening, and now the probability that letter #2 will be matched correctly is zero since letter #1 is already in letter #2's envelope. Letter #1 was incorrectly placed in one of the 8 other envelopes. There was a probability of 8 in 10 of this happening, and now there's a probability of 1 in 9 that letter #2 will be matched correctly to envelope #2. If you add over all these possibilities, then the probability that letter #2 is matched correctly is just: \(\frac{1}{10} \times \frac{1}{9} \,+\, \frac{1}{10} \times 0 \,+\, \frac{8}{10} \times \frac{1}{9} \,=\, \frac{1}{10}\)So P(I[sub]2[/sub] = 1) = [sup]1[/sup]/[sub]10[/sub]. Another way of looking at it is that all the final configurations (of the kind: letter 1 matched to envelope 3, letter 2 matched to...) are equally probable, and any given letter is matched to its correct envelope in [sup]1[/sup]/[sub]n[/sub][sup]th[/sup] of all the possible configurations.
I do not think any of the previous posts presented a valid analysis. Consider the following. There n! ways to put n objects into n containers requiring one & only one object in each container. You can put any of n objects in the first container; Any of (n-1) into the second container; Et cetera. Note that n! is also the number of possible permutations of the first n integers. This problem is equivalent to randomly ordering the first n integers and asking for the probability of integer k being in position k. How many permutations are possible if integer k is in position k? You can assign the remaining (n-1) integers in (n-1)! ways. Probability equals n! / (n-1)!, which equals n.
