Mixing
Grimmett and Stirzaker P57 (Letter Matching)
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I'm suck on step 4 of the derivation below.
A secretary types n different letters together with matching envelopes, she then drops the pile down the stairs, and then places the letters randomly in the envelopes afterwards. Each arrangement is equally likely, and the task is to find the probability that exactly r are in their correct envelopes.
Solution:
Let $L_1, L_2,...,L_n$ denote the letters
A good letter means that is in the correct envelope
$A_i$ is the event that $L_i$ is good
$I_i$ is the indicator function of $A_i$
$j_1,..,j_r,k_r+1, ..., k_n$ is a random permutation of the numbers $1,...,n$
$S = sum_piI_j_1...I_j_r(1-I_k_r+1),...,(1-I_k_n)tag1$
Where the sum is taken over all the permutations $pi$
beginequation
S =
begincases
0 & textif X $neq$ 0\
r!(n-r)! & textif X = rtag2
endcases
endequation
Clearly the sum in equation 1 is only 1 $m=r$ and zero otherwise.
There are $r!$ permutations of the r matching letters and $(n-r)!$ permutations of the remaining numbers
Hence
$ I = fracSr!(n-r)! tag3$
Is the indicator function the exactly r letters are good.
it then says to take expectations of (4) and multiply out to obtain:
$E(S)=sum_pisum_s=0^n-r(-1)^sbinomn-rsE(I_j_1...I_j_r(I_k_r+1),...,(I_k_r+s))tag4$
They then state
$E(I_j_1...I_j_r(I_k_r+1),...,(I_k_r+s))=frac(n-r-s)!n!tag5$
Where $(n-r-s)!$ is the permutations which allocate $L_i_1,...,L_j_r, L_k_r+1,...,L_k_r+s$ to their correct envelopes.
Q1.) I'm stuck on eqn 4, broadly it seems to be calculating for a given r (number of good envelopes) the number of permutations for the remaining bad envelopes is this correct?
Q2.) Why have the last s envelopes been changed to $ I_k_r+1$ in Eqn (4) instead of $(1- I_k_r+1)$ as in Eqn (1)?
Q2b.) It says after Eqn(5) that $L_i_1,...,L_j_r, L_k_r+1,...,L_k_r+s$ to their correct envelopes? But I thought only the first set up to r was supposed to be in it's correct envelope?
Q3.) Where does the $(-1)^sbinomn-rs$ come from?
We want to find the number of permutations of the s bad letters i.e. we want to find the number of derangements is this correct?
The formula for the number of derangements $n!sum_j=0^n-kfrac(-1)^jj!$:
$(n-r)!sum_s=0^n-r-sfrac(-1)^ss!$
Which is similar but not the same.
probability
asked Jul 17 at 13:55
Bazman
365211
add a comment |Â
up vote
2
down vote
favorite
I'm suck on step 4 of the derivation below.
A secretary types n different letters together with matching envelopes, she then drops the pile down the stairs, and then places the letters randomly in the envelopes afterwards. Each arrangement is equally likely, and the task is to find the probability that exactly r are in their correct envelopes.
Solution:
Let $L_1, L_2,...,L_n$ denote the letters
A good letter means that is in the correct envelope
$A_i$ is the event that $L_i$ is good
$I_i$ is the indicator function of $A_i$
$j_1,..,j_r,k_r+1, ..., k_n$ is a random permutation of the numbers $1,...,n$
$S = sum_piI_j_1...I_j_r(1-I_k_r+1),...,(1-I_k_n)tag1$
Where the sum is taken over all the permutations $pi$
beginequation
S =
begincases
0 & textif X $neq$ 0\
r!(n-r)! & textif X = rtag2
endcases
endequation
Clearly the sum in equation 1 is only 1 $m=r$ and zero otherwise.
There are $r!$ permutations of the r matching letters and $(n-r)!$ permutations of the remaining numbers
Hence
$ I = fracSr!(n-r)! tag3$
Is the indicator function the exactly r letters are good.
it then says to take expectations of (4) and multiply out to obtain:
$E(S)=sum_pisum_s=0^n-r(-1)^sbinomn-rsE(I_j_1...I_j_r(I_k_r+1),...,(I_k_r+s))tag4$
They then state
$E(I_j_1...I_j_r(I_k_r+1),...,(I_k_r+s))=frac(n-r-s)!n!tag5$
Where $(n-r-s)!$ is the permutations which allocate $L_i_1,...,L_j_r, L_k_r+1,...,L_k_r+s$ to their correct envelopes.
Q1.) I'm stuck on eqn 4, broadly it seems to be calculating for a given r (number of good envelopes) the number of permutations for the remaining bad envelopes is this correct?
Q2.) Why have the last s envelopes been changed to $ I_k_r+1$ in Eqn (4) instead of $(1- I_k_r+1)$ as in Eqn (1)?
Q2b.) It says after Eqn(5) that $L_i_1,...,L_j_r, L_k_r+1,...,L_k_r+s$ to their correct envelopes? But I thought only the first set up to r was supposed to be in it's correct envelope?
Q3.) Where does the $(-1)^sbinomn-rs$ come from?
We want to find the number of permutations of the s bad letters i.e. we want to find the number of derangements is this correct?
The formula for the number of derangements $n!sum_j=0^n-kfrac(-1)^jj!$:
$(n-r)!sum_s=0^n-r-sfrac(-1)^ss!$
Which is similar but not the same.
probability
asked Jul 17 at 13:55
Bazman
365211
1
These are sometimes called rencontres numbers and it should be easy to see that the number of ways of having $r$ correct out of $n$ is $n choose r$ times the number of derangements of $n-r$
– Henry
Jul 17 at 14:04
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I'm suck on step 4 of the derivation below.
A secretary types n different letters together with matching envelopes, she then drops the pile down the stairs, and then places the letters randomly in the envelopes afterwards. Each arrangement is equally likely, and the task is to find the probability that exactly r are in their correct envelopes.
Solution:
Let $L_1, L_2,...,L_n$ denote the letters
A good letter means that is in the correct envelope
$A_i$ is the event that $L_i$ is good
$I_i$ is the indicator function of $A_i$
$j_1,..,j_r,k_r+1, ..., k_n$ is a random permutation of the numbers $1,...,n$
$S = sum_piI_j_1...I_j_r(1-I_k_r+1),...,(1-I_k_n)tag1$
Where the sum is taken over all the permutations $pi$
beginequation
S =
begincases
0 & textif X $neq$ 0\
r!(n-r)! & textif X = rtag2
endcases
endequation
Clearly the sum in equation 1 is only 1 $m=r$ and zero otherwise.
There are $r!$ permutations of the r matching letters and $(n-r)!$ permutations of the remaining numbers
Hence
$ I = fracSr!(n-r)! tag3$
Is the indicator function the exactly r letters are good.
it then says to take expectations of (4) and multiply out to obtain:
$E(S)=sum_pisum_s=0^n-r(-1)^sbinomn-rsE(I_j_1...I_j_r(I_k_r+1),...,(I_k_r+s))tag4$
They then state
$E(I_j_1...I_j_r(I_k_r+1),...,(I_k_r+s))=frac(n-r-s)!n!tag5$
Where $(n-r-s)!$ is the permutations which allocate $L_i_1,...,L_j_r, L_k_r+1,...,L_k_r+s$ to their correct envelopes.
Q1.) I'm stuck on eqn 4, broadly it seems to be calculating for a given r (number of good envelopes) the number of permutations for the remaining bad envelopes is this correct?
Q2.) Why have the last s envelopes been changed to $ I_k_r+1$ in Eqn (4) instead of $(1- I_k_r+1)$ as in Eqn (1)?
Q2b.) It says after Eqn(5) that $L_i_1,...,L_j_r, L_k_r+1,...,L_k_r+s$ to their correct envelopes? But I thought only the first set up to r was supposed to be in it's correct envelope?
Q3.) Where does the $(-1)^sbinomn-rs$ come from?
We want to find the number of permutations of the s bad letters i.e. we want to find the number of derangements is this correct?
The formula for the number of derangements $n!sum_j=0^n-kfrac(-1)^jj!$:
$(n-r)!sum_s=0^n-r-sfrac(-1)^ss!$
Which is similar but not the same.
probability
asked Jul 17 at 13:55
Bazman
365211
I'm suck on step 4 of the derivation below.
A secretary types n different letters together with matching envelopes, she then drops the pile down the stairs, and then places the letters randomly in the envelopes afterwards. Each arrangement is equally likely, and the task is to find the probability that exactly r are in their correct envelopes.
Solution:
Let $L_1, L_2,...,L_n$ denote the letters
A good letter means that is in the correct envelope
$A_i$ is the event that $L_i$ is good
$I_i$ is the indicator function of $A_i$
$j_1,..,j_r,k_r+1, ..., k_n$ is a random permutation of the numbers $1,...,n$
$S = sum_piI_j_1...I_j_r(1-I_k_r+1),...,(1-I_k_n)tag1$
Where the sum is taken over all the permutations $pi$
beginequation
S =
begincases
0 & textif X $neq$ 0\
r!(n-r)! & textif X = rtag2
endcases
endequation
Clearly the sum in equation 1 is only 1 $m=r$ and zero otherwise.
There are $r!$ permutations of the r matching letters and $(n-r)!$ permutations of the remaining numbers
Hence
$ I = fracSr!(n-r)! tag3$
Is the indicator function the exactly r letters are good.
it then says to take expectations of (4) and multiply out to obtain:
$E(S)=sum_pisum_s=0^n-r(-1)^sbinomn-rsE(I_j_1...I_j_r(I_k_r+1),...,(I_k_r+s))tag4$
They then state
$E(I_j_1...I_j_r(I_k_r+1),...,(I_k_r+s))=frac(n-r-s)!n!tag5$
Where $(n-r-s)!$ is the permutations which allocate $L_i_1,...,L_j_r, L_k_r+1,...,L_k_r+s$ to their correct envelopes.
Q1.) I'm stuck on eqn 4, broadly it seems to be calculating for a given r (number of good envelopes) the number of permutations for the remaining bad envelopes is this correct?
Q2.) Why have the last s envelopes been changed to $ I_k_r+1$ in Eqn (4) instead of $(1- I_k_r+1)$ as in Eqn (1)?
Q2b.) It says after Eqn(5) that $L_i_1,...,L_j_r, L_k_r+1,...,L_k_r+s$ to their correct envelopes? But I thought only the first set up to r was supposed to be in it's correct envelope?
Q3.) Where does the $(-1)^sbinomn-rs$ come from?
We want to find the number of permutations of the s bad letters i.e. we want to find the number of derangements is this correct?
The formula for the number of derangements $n!sum_j=0^n-kfrac(-1)^jj!$:
$(n-r)!sum_s=0^n-r-sfrac(-1)^ss!$
Which is similar but not the same.
probability
asked Jul 17 at 13:55
Bazman
365211
asked Jul 17 at 13:55
Bazman
365211
asked Jul 17 at 13:55
Bazman
365211
asked Jul 17 at 13:55
Bazman
365211
365211
1
These are sometimes called rencontres numbers and it should be easy to see that the number of ways of having $r$ correct out of $n$ is $n choose r$ times the number of derangements of $n-r$
– Henry
Jul 17 at 14:04
add a comment |Â
1
These are sometimes called rencontres numbers and it should be easy to see that the number of ways of having $r$ correct out of $n$ is $n choose r$ times the number of derangements of $n-r$
– Henry
Jul 17 at 14:04
1
1
These are sometimes called rencontres numbers and it should be easy to see that the number of ways of having $r$ correct out of $n$ is $n choose r$ times the number of derangements of $n-r$
– Henry
Jul 17 at 14:04
These are sometimes called rencontres numbers and it should be easy to see that the number of ways of having $r$ correct out of $n$ is $n choose r$ times the number of derangements of $n-r$
– Henry
Jul 17 at 14:04
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854522%2fgrimmett-and-stirzaker-p57-letter-matching%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
These are sometimes called rencontres numbers and it should be easy to see that the number of ways of having $r$ correct out of $n$ is $n choose r$ times the number of derangements of $n-r$
– Henry
Jul 17 at 14:04