Mixing
Expected number of updates of Maximum
Let $L$ be a list of unique elements. Consider the following standard algorithm for finding the maximum value in $L$:
- Initialize the current maximum of the list to be $m = −infty$.
- For $i= 1$ up through $n$,check to see if $L[i]>m$; if so, reset $m$ to be $L[i]$.
- Output $m$.
Suppose we randomly permuate the elements of $L$ before running the procedure. Calculated the expected number of times $m$ will be reset in Step 2.
probability-theory random-variables expected-value
edited Nov 21 '18 at 23:02
Asaf Karagila♦
302k32426756
asked Nov 20 '18 at 18:26
Naseeb Thapaliya
62
add a comment |
Let $L$ be a list of unique elements. Consider the following standard algorithm for finding the maximum value in $L$:
- Initialize the current maximum of the list to be $m = −infty$.
- For $i= 1$ up through $n$,check to see if $L[i]>m$; if so, reset $m$ to be $L[i]$.
- Output $m$.
Suppose we randomly permuate the elements of $L$ before running the procedure. Calculated the expected number of times $m$ will be reset in Step 2.
probability-theory random-variables expected-value
edited Nov 21 '18 at 23:02
Asaf Karagila♦
302k32426756
asked Nov 20 '18 at 18:26
Naseeb Thapaliya
62
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
Nov 20 '18 at 21:00
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
Nov 20 '18 at 21:04
Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Nov 21 '18 at 22:48
add a comment |
Let $L$ be a list of unique elements. Consider the following standard algorithm for finding the maximum value in $L$:
- Initialize the current maximum of the list to be $m = −infty$.
- For $i= 1$ up through $n$,check to see if $L[i]>m$; if so, reset $m$ to be $L[i]$.
- Output $m$.
Suppose we randomly permuate the elements of $L$ before running the procedure. Calculated the expected number of times $m$ will be reset in Step 2.
probability-theory random-variables expected-value
edited Nov 21 '18 at 23:02
Asaf Karagila♦
302k32426756
asked Nov 20 '18 at 18:26
Naseeb Thapaliya
62
Let $L$ be a list of unique elements. Consider the following standard algorithm for finding the maximum value in $L$:
- Initialize the current maximum of the list to be $m = −infty$.
- For $i= 1$ up through $n$,check to see if $L[i]>m$; if so, reset $m$ to be $L[i]$.
- Output $m$.
Suppose we randomly permuate the elements of $L$ before running the procedure. Calculated the expected number of times $m$ will be reset in Step 2.
probability-theory random-variables expected-value
probability-theory random-variables expected-value
edited Nov 21 '18 at 23:02
Asaf Karagila♦
302k32426756
asked Nov 20 '18 at 18:26
Naseeb Thapaliya
62
edited Nov 21 '18 at 23:02
Asaf Karagila♦
302k32426756
asked Nov 20 '18 at 18:26
Naseeb Thapaliya
62
edited Nov 21 '18 at 23:02
Asaf Karagila♦
302k32426756
edited Nov 21 '18 at 23:02
Asaf Karagila♦
302k32426756
edited Nov 21 '18 at 23:02
Asaf Karagila♦
302k32426756
302k32426756
asked Nov 20 '18 at 18:26
Naseeb Thapaliya
62
asked Nov 20 '18 at 18:26
Naseeb Thapaliya
62
asked Nov 20 '18 at 18:26
Naseeb Thapaliya
62
62
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
Nov 20 '18 at 21:00
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
Nov 20 '18 at 21:04
Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Nov 21 '18 at 22:48
add a comment |
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
Nov 20 '18 at 21:00
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
Nov 20 '18 at 21:04
Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Nov 21 '18 at 22:48
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
Nov 20 '18 at 21:00
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
Nov 20 '18 at 21:00
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
Nov 20 '18 at 21:04
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
Nov 20 '18 at 21:04
Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Nov 21 '18 at 22:48
Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Nov 21 '18 at 22:48
add a comment |
1 Answer
1
active
oldest
votes
Let $X_i:=L[pi(i)]$, where $pi$ denotes the random permutation of $[n]$, $X_0equiv-infty$, and $M_i:=max_{jle i}X_j$. Then the expected number of resets is
begin{align}
&mathsf{E}left[sum_{i=1}^n 1{X_i>M_{i-1}}right]=sum_{i=1}^n mathsf{P}(X_i>M_{i-1})=sum_{i=1}^nfrac{1}{i}approx ln(n+1)+gamma,
end{align}
where $gamma$ is the Euler's constant, because (thank's to the @Solomonoff'sSecret's comment),
$$
mathsf{P}(X_i>M_{i-1})=frac{(i-1)!}{i!}=frac{1}{i}.
$$
answered Nov 21 '18 at 5:04
d.k.o.
8,612528
1
Sorry, what I am getting at is you can simplify this answer by using $Pr[X_i > M_{i-1}] = frac{1}{i}$ so the sum on line 1 is $H_n$. There is no need to involve double sums or digammas. And the final formula on line 3 equals $H_n$.
– Solomonoff's Secret
Nov 21 '18 at 21:04
@Solomonoff'sSecret Sure. It is $1/i$.
– d.k.o.
Nov 21 '18 at 21:27
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%2f3006710%2fexpected-number-of-updates-of-maximum%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Let $X_i:=L[pi(i)]$, where $pi$ denotes the random permutation of $[n]$, $X_0equiv-infty$, and $M_i:=max_{jle i}X_j$. Then the expected number of resets is
begin{align}
&mathsf{E}left[sum_{i=1}^n 1{X_i>M_{i-1}}right]=sum_{i=1}^n mathsf{P}(X_i>M_{i-1})=sum_{i=1}^nfrac{1}{i}approx ln(n+1)+gamma,
end{align}
where $gamma$ is the Euler's constant, because (thank's to the @Solomonoff'sSecret's comment),
$$
mathsf{P}(X_i>M_{i-1})=frac{(i-1)!}{i!}=frac{1}{i}.
$$
answered Nov 21 '18 at 5:04
d.k.o.
8,612528
1
Sorry, what I am getting at is you can simplify this answer by using $Pr[X_i > M_{i-1}] = frac{1}{i}$ so the sum on line 1 is $H_n$. There is no need to involve double sums or digammas. And the final formula on line 3 equals $H_n$.
– Solomonoff's Secret
Nov 21 '18 at 21:04
@Solomonoff'sSecret Sure. It is $1/i$.
– d.k.o.
Nov 21 '18 at 21:27
add a comment |
Let $X_i:=L[pi(i)]$, where $pi$ denotes the random permutation of $[n]$, $X_0equiv-infty$, and $M_i:=max_{jle i}X_j$. Then the expected number of resets is
begin{align}
&mathsf{E}left[sum_{i=1}^n 1{X_i>M_{i-1}}right]=sum_{i=1}^n mathsf{P}(X_i>M_{i-1})=sum_{i=1}^nfrac{1}{i}approx ln(n+1)+gamma,
end{align}
where $gamma$ is the Euler's constant, because (thank's to the @Solomonoff'sSecret's comment),
$$
mathsf{P}(X_i>M_{i-1})=frac{(i-1)!}{i!}=frac{1}{i}.
$$
answered Nov 21 '18 at 5:04
d.k.o.
8,612528
1
Sorry, what I am getting at is you can simplify this answer by using $Pr[X_i > M_{i-1}] = frac{1}{i}$ so the sum on line 1 is $H_n$. There is no need to involve double sums or digammas. And the final formula on line 3 equals $H_n$.
– Solomonoff's Secret
Nov 21 '18 at 21:04
@Solomonoff'sSecret Sure. It is $1/i$.
– d.k.o.
Nov 21 '18 at 21:27
add a comment |
Let $X_i:=L[pi(i)]$, where $pi$ denotes the random permutation of $[n]$, $X_0equiv-infty$, and $M_i:=max_{jle i}X_j$. Then the expected number of resets is
begin{align}
&mathsf{E}left[sum_{i=1}^n 1{X_i>M_{i-1}}right]=sum_{i=1}^n mathsf{P}(X_i>M_{i-1})=sum_{i=1}^nfrac{1}{i}approx ln(n+1)+gamma,
end{align}
where $gamma$ is the Euler's constant, because (thank's to the @Solomonoff'sSecret's comment),
$$
mathsf{P}(X_i>M_{i-1})=frac{(i-1)!}{i!}=frac{1}{i}.
$$
answered Nov 21 '18 at 5:04
d.k.o.
8,612528
Let $X_i:=L[pi(i)]$, where $pi$ denotes the random permutation of $[n]$, $X_0equiv-infty$, and $M_i:=max_{jle i}X_j$. Then the expected number of resets is
begin{align}
&mathsf{E}left[sum_{i=1}^n 1{X_i>M_{i-1}}right]=sum_{i=1}^n mathsf{P}(X_i>M_{i-1})=sum_{i=1}^nfrac{1}{i}approx ln(n+1)+gamma,
end{align}
where $gamma$ is the Euler's constant, because (thank's to the @Solomonoff'sSecret's comment),
$$
mathsf{P}(X_i>M_{i-1})=frac{(i-1)!}{i!}=frac{1}{i}.
$$
answered Nov 21 '18 at 5:04
d.k.o.
8,612528
edited Nov 21 '18 at 22:00
answered Nov 21 '18 at 5:04
d.k.o.
8,612528
answered Nov 21 '18 at 5:04
d.k.o.
8,612528
answered Nov 21 '18 at 5:04
d.k.o.
8,612528
8,612528
1
Sorry, what I am getting at is you can simplify this answer by using $Pr[X_i > M_{i-1}] = frac{1}{i}$ so the sum on line 1 is $H_n$. There is no need to involve double sums or digammas. And the final formula on line 3 equals $H_n$.
– Solomonoff's Secret
Nov 21 '18 at 21:04
@Solomonoff'sSecret Sure. It is $1/i$.
– d.k.o.
Nov 21 '18 at 21:27
add a comment |
1
Sorry, what I am getting at is you can simplify this answer by using $Pr[X_i > M_{i-1}] = frac{1}{i}$ so the sum on line 1 is $H_n$. There is no need to involve double sums or digammas. And the final formula on line 3 equals $H_n$.
– Solomonoff's Secret
Nov 21 '18 at 21:04
@Solomonoff'sSecret Sure. It is $1/i$.
– d.k.o.
Nov 21 '18 at 21:27
1
1
Sorry, what I am getting at is you can simplify this answer by using $Pr[X_i > M_{i-1}] = frac{1}{i}$ so the sum on line 1 is $H_n$. There is no need to involve double sums or digammas. And the final formula on line 3 equals $H_n$.
– Solomonoff's Secret
Nov 21 '18 at 21:04
Sorry, what I am getting at is you can simplify this answer by using $Pr[X_i > M_{i-1}] = frac{1}{i}$ so the sum on line 1 is $H_n$. There is no need to involve double sums or digammas. And the final formula on line 3 equals $H_n$.
– Solomonoff's Secret
Nov 21 '18 at 21:04
@Solomonoff'sSecret Sure. It is $1/i$.
– d.k.o.
Nov 21 '18 at 21:27
@Solomonoff'sSecret Sure. It is $1/i$.
– d.k.o.
Nov 21 '18 at 21:27
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3006710%2fexpected-number-of-updates-of-maximum%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
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
Nov 20 '18 at 21:00
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
Nov 20 '18 at 21:04
Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Nov 21 '18 at 22:48