Expected number of updates of Maximum
up vote
1
down vote
favorite
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 foundations expected-value
edited 2 hours ago
d.k.o.
8,079527
asked 13 hours ago
Naseeb Thapaliya
62
add a comment |
up vote
1
down vote
favorite
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 foundations expected-value
edited 2 hours ago
d.k.o.
8,079527
asked 13 hours ago
Naseeb Thapaliya
62
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
10 hours ago
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
10 hours ago
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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 foundations expected-value
edited 2 hours ago
d.k.o.
8,079527
asked 13 hours ago
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 foundations expected-value
probability-theory random-variables foundations expected-value
edited 2 hours ago
d.k.o.
8,079527
asked 13 hours ago
Naseeb Thapaliya
62
edited 2 hours ago
d.k.o.
8,079527
asked 13 hours ago
Naseeb Thapaliya
62
edited 2 hours ago
d.k.o.
8,079527
edited 2 hours ago
d.k.o.
8,079527
edited 2 hours ago
d.k.o.
8,079527
8,079527
asked 13 hours ago
Naseeb Thapaliya
62
asked 13 hours ago
Naseeb Thapaliya
62
asked 13 hours ago
Naseeb Thapaliya
62
62
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
10 hours ago
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
10 hours ago
add a comment |
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
10 hours ago
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
10 hours ago
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
10 hours ago
Perhaps this, or something like it: cs.stackexchange.com/questions/63682/…
– Ethan Bolker
10 hours ago
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
10 hours ago
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
10 hours ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
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}) \
&qquad =sum_{i=1}^nmathsf{E}left[mathsf{P}(X_i>M_{i-1}mid X_i)right]=frac{1}{n}sum_{i=1}^nsum_{j=1}^nbinom{j-1}{i-1}binom{n-1}{i-1}^{-1} \
&qquad=Psi(n+1)+gamma,
end{align}
where $Psi$ is the digamma function and $gamma=-Psi(1)$ is the Euler's constant.
answered 2 hours ago
d.k.o.
8,079527
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
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}) \
&qquad =sum_{i=1}^nmathsf{E}left[mathsf{P}(X_i>M_{i-1}mid X_i)right]=frac{1}{n}sum_{i=1}^nsum_{j=1}^nbinom{j-1}{i-1}binom{n-1}{i-1}^{-1} \
&qquad=Psi(n+1)+gamma,
end{align}
where $Psi$ is the digamma function and $gamma=-Psi(1)$ is the Euler's constant.
answered 2 hours ago
d.k.o.
8,079527
add a comment |
up vote
0
down vote
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}) \
&qquad =sum_{i=1}^nmathsf{E}left[mathsf{P}(X_i>M_{i-1}mid X_i)right]=frac{1}{n}sum_{i=1}^nsum_{j=1}^nbinom{j-1}{i-1}binom{n-1}{i-1}^{-1} \
&qquad=Psi(n+1)+gamma,
end{align}
where $Psi$ is the digamma function and $gamma=-Psi(1)$ is the Euler's constant.
answered 2 hours ago
d.k.o.
8,079527
add a comment |
up vote
0
down vote
up vote
0
down vote
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}) \
&qquad =sum_{i=1}^nmathsf{E}left[mathsf{P}(X_i>M_{i-1}mid X_i)right]=frac{1}{n}sum_{i=1}^nsum_{j=1}^nbinom{j-1}{i-1}binom{n-1}{i-1}^{-1} \
&qquad=Psi(n+1)+gamma,
end{align}
where $Psi$ is the digamma function and $gamma=-Psi(1)$ is the Euler's constant.
answered 2 hours ago
d.k.o.
8,079527
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}) \
&qquad =sum_{i=1}^nmathsf{E}left[mathsf{P}(X_i>M_{i-1}mid X_i)right]=frac{1}{n}sum_{i=1}^nsum_{j=1}^nbinom{j-1}{i-1}binom{n-1}{i-1}^{-1} \
&qquad=Psi(n+1)+gamma,
end{align}
where $Psi$ is the digamma function and $gamma=-Psi(1)$ is the Euler's constant.
answered 2 hours ago
d.k.o.
8,079527
edited 1 hour ago
answered 2 hours ago
d.k.o.
8,079527
answered 2 hours ago
d.k.o.
8,079527
answered 2 hours ago
d.k.o.
8,079527
8,079527
add a comment |
add a comment |
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
10 hours ago
Thank you for the comment. However, my question is about the expected value that the algorithm will output m in list L.
– Naseeb Thapaliya
10 hours ago