Independence of probability of $a_k$ being the largest element among the first $k$ elements in the...
$begingroup$
The question is:
Let $n ge 2$ be an integer and consider a uniformly random permutation
($a_1$, $a_2$, . . . , $a_n$) of the set (1, 2, . . . , n).
For each $k$ with $1 le k le n$, define the event
$A_k$ = "$a_k$ is the largest element among the first $k$ elements
in the permutation".
Let $k$ and $l$ be two integers with $1 le k lt l le n$. Prove that the events $A_k$ and $A_l$ are independent.
I know that we should define Pr($A_k$), Pr($A_k$), Pr($A_k cap A_l$) and than check relation between those but I keep getting into a dead end where those events are dependent.
probability combinatorics permutations independence
$endgroup$
add a comment |
$begingroup$
The question is:
Let $n ge 2$ be an integer and consider a uniformly random permutation
($a_1$, $a_2$, . . . , $a_n$) of the set (1, 2, . . . , n).
For each $k$ with $1 le k le n$, define the event
$A_k$ = "$a_k$ is the largest element among the first $k$ elements
in the permutation".
Let $k$ and $l$ be two integers with $1 le k lt l le n$. Prove that the events $A_k$ and $A_l$ are independent.
I know that we should define Pr($A_k$), Pr($A_k$), Pr($A_k cap A_l$) and than check relation between those but I keep getting into a dead end where those events are dependent.
probability combinatorics permutations independence
$endgroup$
add a comment |
$begingroup$
The question is:
Let $n ge 2$ be an integer and consider a uniformly random permutation
($a_1$, $a_2$, . . . , $a_n$) of the set (1, 2, . . . , n).
For each $k$ with $1 le k le n$, define the event
$A_k$ = "$a_k$ is the largest element among the first $k$ elements
in the permutation".
Let $k$ and $l$ be two integers with $1 le k lt l le n$. Prove that the events $A_k$ and $A_l$ are independent.
I know that we should define Pr($A_k$), Pr($A_k$), Pr($A_k cap A_l$) and than check relation between those but I keep getting into a dead end where those events are dependent.
probability combinatorics permutations independence
$endgroup$
The question is:
Let $n ge 2$ be an integer and consider a uniformly random permutation
($a_1$, $a_2$, . . . , $a_n$) of the set (1, 2, . . . , n).
For each $k$ with $1 le k le n$, define the event
$A_k$ = "$a_k$ is the largest element among the first $k$ elements
in the permutation".
Let $k$ and $l$ be two integers with $1 le k lt l le n$. Prove that the events $A_k$ and $A_l$ are independent.
I know that we should define Pr($A_k$), Pr($A_k$), Pr($A_k cap A_l$) and than check relation between those but I keep getting into a dead end where those events are dependent.
probability combinatorics permutations independence
probability combinatorics permutations independence
asked Dec 24 '18 at 14:12
MrKadek750MrKadek750
253
253
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
To specify a permutation where $a_k$ is the largest among ${a_1,dots,a_k}$, you choose which $k$ numbers form the set ${a_1,dots,a_k}$ in $binom{n}k$ ways, you place the largest at the $k^{th}$ spot in $1$ way, you order the other elements in $(k-1)!$ ways, then you order the other $n-k$ elements in $(n-k)!$ ways. Therefore,
$$
P(A_k)=frac{text{# of valid permutations}}{text{total number of permutations}}=frac{binom{n}k(k-1)!(n-k)!}{n!}=frac1k
$$
Similarly, letting $k<ell$, in order to specify a permutation where $a_ell$ is the largest among $a_1,dots a_ell$ and $a_k$ among $a_1,dots,a_k$, you
- Choose the set ${a_1,dots,a_ell}$ in $binom{n}ell$ ways.
- Place the largest element in the $ell^{th}$ spot.
- From the remaining $ell-1$ numbers, choose ${a_1,dots,a_k}$ in $binom{ell-1}k$ ways.
- Place the largest of those $k$ numbers in the $k^{th}$ spot.
- Choose an order for $a_{k+1},a_{k+2},dots,a_{ell-1}$ in $(ell-1-k)!$ ways.
- Choose an order for $a_1,dots,a_{k-1}$ in $(k-1)!$ ways.
- Choose an order for$a_{ell+1},dots,a_n$ in $(n-ell)!$ ways.
If you multiply all hose numbers out and divide by $n!$, wou will get $frac{1}{kell}$.
$endgroup$
$begingroup$
Beautiful, thank you!
$endgroup$
– MrKadek750
Dec 25 '18 at 15:04
add a comment |
$begingroup$
For each $k$ let $[n]_k$ be the family of all subsets of the set ${1,dots,n}$ of size $k$. Then
$$p_{k,n}=P(A_k)=sum_{Sin [n]_k} P(A_k|{a_1,dots,a_k}=S) P({a_1,dots,a_k}=S)=$$ $$sum_{Sin [n]_k} frac 1kP({a_1,dots,a_k}=S)=frac 1ksum_{Sin [n]_k} P({a_1,dots,a_k}=S)=frac 1k.$$
$$P(A_kcap A_l)=sum_{Sin [n]_l} P(A_kcap A_l|{a_1,dots,a_l}=S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l P(A_k|{a_1,dots,a_{l-1}}=Ssetminusmax S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l p_{k,l-1}P({a_1,dots,a_l}=S)=sum_{Sin [n]_l} frac 1lfrac 1{k} P({a_1,dots,a_l}=S)=$$ $$ frac 1lfrac 1{k}sum_{Sin [n]_l} P({a_1,dots,a_l}=S)= frac 1lfrac 1{k}=P(A_l)P(A_k).$$
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3051281%2findependence-of-probability-of-a-k-being-the-largest-element-among-the-first%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To specify a permutation where $a_k$ is the largest among ${a_1,dots,a_k}$, you choose which $k$ numbers form the set ${a_1,dots,a_k}$ in $binom{n}k$ ways, you place the largest at the $k^{th}$ spot in $1$ way, you order the other elements in $(k-1)!$ ways, then you order the other $n-k$ elements in $(n-k)!$ ways. Therefore,
$$
P(A_k)=frac{text{# of valid permutations}}{text{total number of permutations}}=frac{binom{n}k(k-1)!(n-k)!}{n!}=frac1k
$$
Similarly, letting $k<ell$, in order to specify a permutation where $a_ell$ is the largest among $a_1,dots a_ell$ and $a_k$ among $a_1,dots,a_k$, you
- Choose the set ${a_1,dots,a_ell}$ in $binom{n}ell$ ways.
- Place the largest element in the $ell^{th}$ spot.
- From the remaining $ell-1$ numbers, choose ${a_1,dots,a_k}$ in $binom{ell-1}k$ ways.
- Place the largest of those $k$ numbers in the $k^{th}$ spot.
- Choose an order for $a_{k+1},a_{k+2},dots,a_{ell-1}$ in $(ell-1-k)!$ ways.
- Choose an order for $a_1,dots,a_{k-1}$ in $(k-1)!$ ways.
- Choose an order for$a_{ell+1},dots,a_n$ in $(n-ell)!$ ways.
If you multiply all hose numbers out and divide by $n!$, wou will get $frac{1}{kell}$.
$endgroup$
$begingroup$
Beautiful, thank you!
$endgroup$
– MrKadek750
Dec 25 '18 at 15:04
add a comment |
$begingroup$
To specify a permutation where $a_k$ is the largest among ${a_1,dots,a_k}$, you choose which $k$ numbers form the set ${a_1,dots,a_k}$ in $binom{n}k$ ways, you place the largest at the $k^{th}$ spot in $1$ way, you order the other elements in $(k-1)!$ ways, then you order the other $n-k$ elements in $(n-k)!$ ways. Therefore,
$$
P(A_k)=frac{text{# of valid permutations}}{text{total number of permutations}}=frac{binom{n}k(k-1)!(n-k)!}{n!}=frac1k
$$
Similarly, letting $k<ell$, in order to specify a permutation where $a_ell$ is the largest among $a_1,dots a_ell$ and $a_k$ among $a_1,dots,a_k$, you
- Choose the set ${a_1,dots,a_ell}$ in $binom{n}ell$ ways.
- Place the largest element in the $ell^{th}$ spot.
- From the remaining $ell-1$ numbers, choose ${a_1,dots,a_k}$ in $binom{ell-1}k$ ways.
- Place the largest of those $k$ numbers in the $k^{th}$ spot.
- Choose an order for $a_{k+1},a_{k+2},dots,a_{ell-1}$ in $(ell-1-k)!$ ways.
- Choose an order for $a_1,dots,a_{k-1}$ in $(k-1)!$ ways.
- Choose an order for$a_{ell+1},dots,a_n$ in $(n-ell)!$ ways.
If you multiply all hose numbers out and divide by $n!$, wou will get $frac{1}{kell}$.
$endgroup$
$begingroup$
Beautiful, thank you!
$endgroup$
– MrKadek750
Dec 25 '18 at 15:04
add a comment |
$begingroup$
To specify a permutation where $a_k$ is the largest among ${a_1,dots,a_k}$, you choose which $k$ numbers form the set ${a_1,dots,a_k}$ in $binom{n}k$ ways, you place the largest at the $k^{th}$ spot in $1$ way, you order the other elements in $(k-1)!$ ways, then you order the other $n-k$ elements in $(n-k)!$ ways. Therefore,
$$
P(A_k)=frac{text{# of valid permutations}}{text{total number of permutations}}=frac{binom{n}k(k-1)!(n-k)!}{n!}=frac1k
$$
Similarly, letting $k<ell$, in order to specify a permutation where $a_ell$ is the largest among $a_1,dots a_ell$ and $a_k$ among $a_1,dots,a_k$, you
- Choose the set ${a_1,dots,a_ell}$ in $binom{n}ell$ ways.
- Place the largest element in the $ell^{th}$ spot.
- From the remaining $ell-1$ numbers, choose ${a_1,dots,a_k}$ in $binom{ell-1}k$ ways.
- Place the largest of those $k$ numbers in the $k^{th}$ spot.
- Choose an order for $a_{k+1},a_{k+2},dots,a_{ell-1}$ in $(ell-1-k)!$ ways.
- Choose an order for $a_1,dots,a_{k-1}$ in $(k-1)!$ ways.
- Choose an order for$a_{ell+1},dots,a_n$ in $(n-ell)!$ ways.
If you multiply all hose numbers out and divide by $n!$, wou will get $frac{1}{kell}$.
$endgroup$
To specify a permutation where $a_k$ is the largest among ${a_1,dots,a_k}$, you choose which $k$ numbers form the set ${a_1,dots,a_k}$ in $binom{n}k$ ways, you place the largest at the $k^{th}$ spot in $1$ way, you order the other elements in $(k-1)!$ ways, then you order the other $n-k$ elements in $(n-k)!$ ways. Therefore,
$$
P(A_k)=frac{text{# of valid permutations}}{text{total number of permutations}}=frac{binom{n}k(k-1)!(n-k)!}{n!}=frac1k
$$
Similarly, letting $k<ell$, in order to specify a permutation where $a_ell$ is the largest among $a_1,dots a_ell$ and $a_k$ among $a_1,dots,a_k$, you
- Choose the set ${a_1,dots,a_ell}$ in $binom{n}ell$ ways.
- Place the largest element in the $ell^{th}$ spot.
- From the remaining $ell-1$ numbers, choose ${a_1,dots,a_k}$ in $binom{ell-1}k$ ways.
- Place the largest of those $k$ numbers in the $k^{th}$ spot.
- Choose an order for $a_{k+1},a_{k+2},dots,a_{ell-1}$ in $(ell-1-k)!$ ways.
- Choose an order for $a_1,dots,a_{k-1}$ in $(k-1)!$ ways.
- Choose an order for$a_{ell+1},dots,a_n$ in $(n-ell)!$ ways.
If you multiply all hose numbers out and divide by $n!$, wou will get $frac{1}{kell}$.
answered Dec 24 '18 at 16:46
Mike EarnestMike Earnest
24.3k22151
24.3k22151
$begingroup$
Beautiful, thank you!
$endgroup$
– MrKadek750
Dec 25 '18 at 15:04
add a comment |
$begingroup$
Beautiful, thank you!
$endgroup$
– MrKadek750
Dec 25 '18 at 15:04
$begingroup$
Beautiful, thank you!
$endgroup$
– MrKadek750
Dec 25 '18 at 15:04
$begingroup$
Beautiful, thank you!
$endgroup$
– MrKadek750
Dec 25 '18 at 15:04
add a comment |
$begingroup$
For each $k$ let $[n]_k$ be the family of all subsets of the set ${1,dots,n}$ of size $k$. Then
$$p_{k,n}=P(A_k)=sum_{Sin [n]_k} P(A_k|{a_1,dots,a_k}=S) P({a_1,dots,a_k}=S)=$$ $$sum_{Sin [n]_k} frac 1kP({a_1,dots,a_k}=S)=frac 1ksum_{Sin [n]_k} P({a_1,dots,a_k}=S)=frac 1k.$$
$$P(A_kcap A_l)=sum_{Sin [n]_l} P(A_kcap A_l|{a_1,dots,a_l}=S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l P(A_k|{a_1,dots,a_{l-1}}=Ssetminusmax S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l p_{k,l-1}P({a_1,dots,a_l}=S)=sum_{Sin [n]_l} frac 1lfrac 1{k} P({a_1,dots,a_l}=S)=$$ $$ frac 1lfrac 1{k}sum_{Sin [n]_l} P({a_1,dots,a_l}=S)= frac 1lfrac 1{k}=P(A_l)P(A_k).$$
$endgroup$
add a comment |
$begingroup$
For each $k$ let $[n]_k$ be the family of all subsets of the set ${1,dots,n}$ of size $k$. Then
$$p_{k,n}=P(A_k)=sum_{Sin [n]_k} P(A_k|{a_1,dots,a_k}=S) P({a_1,dots,a_k}=S)=$$ $$sum_{Sin [n]_k} frac 1kP({a_1,dots,a_k}=S)=frac 1ksum_{Sin [n]_k} P({a_1,dots,a_k}=S)=frac 1k.$$
$$P(A_kcap A_l)=sum_{Sin [n]_l} P(A_kcap A_l|{a_1,dots,a_l}=S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l P(A_k|{a_1,dots,a_{l-1}}=Ssetminusmax S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l p_{k,l-1}P({a_1,dots,a_l}=S)=sum_{Sin [n]_l} frac 1lfrac 1{k} P({a_1,dots,a_l}=S)=$$ $$ frac 1lfrac 1{k}sum_{Sin [n]_l} P({a_1,dots,a_l}=S)= frac 1lfrac 1{k}=P(A_l)P(A_k).$$
$endgroup$
add a comment |
$begingroup$
For each $k$ let $[n]_k$ be the family of all subsets of the set ${1,dots,n}$ of size $k$. Then
$$p_{k,n}=P(A_k)=sum_{Sin [n]_k} P(A_k|{a_1,dots,a_k}=S) P({a_1,dots,a_k}=S)=$$ $$sum_{Sin [n]_k} frac 1kP({a_1,dots,a_k}=S)=frac 1ksum_{Sin [n]_k} P({a_1,dots,a_k}=S)=frac 1k.$$
$$P(A_kcap A_l)=sum_{Sin [n]_l} P(A_kcap A_l|{a_1,dots,a_l}=S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l P(A_k|{a_1,dots,a_{l-1}}=Ssetminusmax S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l p_{k,l-1}P({a_1,dots,a_l}=S)=sum_{Sin [n]_l} frac 1lfrac 1{k} P({a_1,dots,a_l}=S)=$$ $$ frac 1lfrac 1{k}sum_{Sin [n]_l} P({a_1,dots,a_l}=S)= frac 1lfrac 1{k}=P(A_l)P(A_k).$$
$endgroup$
For each $k$ let $[n]_k$ be the family of all subsets of the set ${1,dots,n}$ of size $k$. Then
$$p_{k,n}=P(A_k)=sum_{Sin [n]_k} P(A_k|{a_1,dots,a_k}=S) P({a_1,dots,a_k}=S)=$$ $$sum_{Sin [n]_k} frac 1kP({a_1,dots,a_k}=S)=frac 1ksum_{Sin [n]_k} P({a_1,dots,a_k}=S)=frac 1k.$$
$$P(A_kcap A_l)=sum_{Sin [n]_l} P(A_kcap A_l|{a_1,dots,a_l}=S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l P(A_k|{a_1,dots,a_{l-1}}=Ssetminusmax S) P({a_1,dots,a_l}=S)=$$
$$sum_{Sin [n]_l} frac 1l p_{k,l-1}P({a_1,dots,a_l}=S)=sum_{Sin [n]_l} frac 1lfrac 1{k} P({a_1,dots,a_l}=S)=$$ $$ frac 1lfrac 1{k}sum_{Sin [n]_l} P({a_1,dots,a_l}=S)= frac 1lfrac 1{k}=P(A_l)P(A_k).$$
answered Dec 24 '18 at 16:22
Alex RavskyAlex Ravsky
42.4k32383
42.4k32383
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3051281%2findependence-of-probability-of-a-k-being-the-largest-element-among-the-first%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown