Upper Bound on Expected Value of $n$ i.i.d. Poisson random variables.
$begingroup$
Let ${X_i }_{i=1}^n$ be i.i.d. from a Poisson random variable with mean $lambda$ and let $$M_n = max_{1 le i le n} X_i.$$
What is a tight upper bound on $mathbb{E}[M_n]$? I can prove that
begin{equation}
mathbb{E}[M_n] le frac{(lambda+1) log n}{log log n} + O left( frac{1}{log log n} right)
end{equation}
but numerically this bound is not tight. Can someone give a tighter analysis or point to a reference with one?
Proof of my bound:
Let $s > 0$. Then by Jensen's inequality,
$$ e^{s mathbb{E}[M_n]} le mathbb{E}[e^{sM_n}] le sum_{i-1}^n mathbb{E}[e^{sX_i}] = ne^{lambda(e^s-1)}$$
from the moment generating function. Then taking the logarithm of both sides gives
$$ mathbb{E}[M_n] le frac{log n}s + frac{lambda(e^s-1)}{s}.$$
Finally, the minimum of the function on the right hand side should be around $s = log log n$ which gives the bound above.
probability probability-distributions expected-value
asked Dec 6 '18 at 18:41
Sandeep SilwalSandeep Silwal
5,84311236
$endgroup$
add a comment |
$begingroup$
Let ${X_i }_{i=1}^n$ be i.i.d. from a Poisson random variable with mean $lambda$ and let $$M_n = max_{1 le i le n} X_i.$$
What is a tight upper bound on $mathbb{E}[M_n]$? I can prove that
begin{equation}
mathbb{E}[M_n] le frac{(lambda+1) log n}{log log n} + O left( frac{1}{log log n} right)
end{equation}
but numerically this bound is not tight. Can someone give a tighter analysis or point to a reference with one?
Proof of my bound:
Let $s > 0$. Then by Jensen's inequality,
$$ e^{s mathbb{E}[M_n]} le mathbb{E}[e^{sM_n}] le sum_{i-1}^n mathbb{E}[e^{sX_i}] = ne^{lambda(e^s-1)}$$
from the moment generating function. Then taking the logarithm of both sides gives
$$ mathbb{E}[M_n] le frac{log n}s + frac{lambda(e^s-1)}{s}.$$
Finally, the minimum of the function on the right hand side should be around $s = log log n$ which gives the bound above.
probability probability-distributions expected-value
asked Dec 6 '18 at 18:41
Sandeep SilwalSandeep Silwal
5,84311236
$endgroup$
$begingroup$
Some back of the envelope calculations lead me to believe that is the right asymptotic growth. What numerics do you have to show it's not tight? Is it the $log n/ log log n$ asymptotic or just the constant $lambda+1$?
$endgroup$
– maridia
Dec 7 '18 at 2:24
$begingroup$
Just the constant $lambda + 1$. I do think its $O(log n / log log n)$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:27
$begingroup$
Does the constant 1 match better? You're clearly losing something by going from max to sum.
$endgroup$
– maridia
Dec 7 '18 at 2:35
$begingroup$
1 is definitely too small. Also the constant should depend on $lambda$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:37
$begingroup$
Are you sure? Take a look at this paper: arxiv.org/pdf/0903.4373.pdf Apparently $M_n$ becomes super concentrated as $n to infty$ and with high probability lies in an interval of length 1 located $~ log n /log log n$ independent of $lambda$.
$endgroup$
– maridia
Dec 7 '18 at 2:48
add a comment |
$begingroup$
Let ${X_i }_{i=1}^n$ be i.i.d. from a Poisson random variable with mean $lambda$ and let $$M_n = max_{1 le i le n} X_i.$$
What is a tight upper bound on $mathbb{E}[M_n]$? I can prove that
begin{equation}
mathbb{E}[M_n] le frac{(lambda+1) log n}{log log n} + O left( frac{1}{log log n} right)
end{equation}
but numerically this bound is not tight. Can someone give a tighter analysis or point to a reference with one?
Proof of my bound:
Let $s > 0$. Then by Jensen's inequality,
$$ e^{s mathbb{E}[M_n]} le mathbb{E}[e^{sM_n}] le sum_{i-1}^n mathbb{E}[e^{sX_i}] = ne^{lambda(e^s-1)}$$
from the moment generating function. Then taking the logarithm of both sides gives
$$ mathbb{E}[M_n] le frac{log n}s + frac{lambda(e^s-1)}{s}.$$
Finally, the minimum of the function on the right hand side should be around $s = log log n$ which gives the bound above.
probability probability-distributions expected-value
asked Dec 6 '18 at 18:41
Sandeep SilwalSandeep Silwal
5,84311236
$endgroup$
Let ${X_i }_{i=1}^n$ be i.i.d. from a Poisson random variable with mean $lambda$ and let $$M_n = max_{1 le i le n} X_i.$$
What is a tight upper bound on $mathbb{E}[M_n]$? I can prove that
begin{equation}
mathbb{E}[M_n] le frac{(lambda+1) log n}{log log n} + O left( frac{1}{log log n} right)
end{equation}
but numerically this bound is not tight. Can someone give a tighter analysis or point to a reference with one?
Proof of my bound:
Let $s > 0$. Then by Jensen's inequality,
$$ e^{s mathbb{E}[M_n]} le mathbb{E}[e^{sM_n}] le sum_{i-1}^n mathbb{E}[e^{sX_i}] = ne^{lambda(e^s-1)}$$
from the moment generating function. Then taking the logarithm of both sides gives
$$ mathbb{E}[M_n] le frac{log n}s + frac{lambda(e^s-1)}{s}.$$
Finally, the minimum of the function on the right hand side should be around $s = log log n$ which gives the bound above.
probability probability-distributions expected-value
probability probability-distributions expected-value
asked Dec 6 '18 at 18:41
Sandeep SilwalSandeep Silwal
5,84311236
asked Dec 6 '18 at 18:41
Sandeep SilwalSandeep Silwal
5,84311236
asked Dec 6 '18 at 18:41
Sandeep SilwalSandeep Silwal
5,84311236
asked Dec 6 '18 at 18:41
Sandeep SilwalSandeep Silwal
5,84311236
asked Dec 6 '18 at 18:41
Sandeep SilwalSandeep Silwal
5,84311236
5,84311236
$begingroup$
Some back of the envelope calculations lead me to believe that is the right asymptotic growth. What numerics do you have to show it's not tight? Is it the $log n/ log log n$ asymptotic or just the constant $lambda+1$?
$endgroup$
– maridia
Dec 7 '18 at 2:24
$begingroup$
Just the constant $lambda + 1$. I do think its $O(log n / log log n)$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:27
$begingroup$
Does the constant 1 match better? You're clearly losing something by going from max to sum.
$endgroup$
– maridia
Dec 7 '18 at 2:35
$begingroup$
1 is definitely too small. Also the constant should depend on $lambda$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:37
$begingroup$
Are you sure? Take a look at this paper: arxiv.org/pdf/0903.4373.pdf Apparently $M_n$ becomes super concentrated as $n to infty$ and with high probability lies in an interval of length 1 located $~ log n /log log n$ independent of $lambda$.
$endgroup$
– maridia
Dec 7 '18 at 2:48
add a comment |
$begingroup$
Some back of the envelope calculations lead me to believe that is the right asymptotic growth. What numerics do you have to show it's not tight? Is it the $log n/ log log n$ asymptotic or just the constant $lambda+1$?
$endgroup$
– maridia
Dec 7 '18 at 2:24
$begingroup$
Just the constant $lambda + 1$. I do think its $O(log n / log log n)$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:27
$begingroup$
Does the constant 1 match better? You're clearly losing something by going from max to sum.
$endgroup$
– maridia
Dec 7 '18 at 2:35
$begingroup$
1 is definitely too small. Also the constant should depend on $lambda$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:37
$begingroup$
Are you sure? Take a look at this paper: arxiv.org/pdf/0903.4373.pdf Apparently $M_n$ becomes super concentrated as $n to infty$ and with high probability lies in an interval of length 1 located $~ log n /log log n$ independent of $lambda$.
$endgroup$
– maridia
Dec 7 '18 at 2:48
$begingroup$
Some back of the envelope calculations lead me to believe that is the right asymptotic growth. What numerics do you have to show it's not tight? Is it the $log n/ log log n$ asymptotic or just the constant $lambda+1$?
$endgroup$
– maridia
Dec 7 '18 at 2:24
$begingroup$
Some back of the envelope calculations lead me to believe that is the right asymptotic growth. What numerics do you have to show it's not tight? Is it the $log n/ log log n$ asymptotic or just the constant $lambda+1$?
$endgroup$
– maridia
Dec 7 '18 at 2:24
$begingroup$
Just the constant $lambda + 1$. I do think its $O(log n / log log n)$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:27
$begingroup$
Just the constant $lambda + 1$. I do think its $O(log n / log log n)$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:27
$begingroup$
Does the constant 1 match better? You're clearly losing something by going from max to sum.
$endgroup$
– maridia
Dec 7 '18 at 2:35
$begingroup$
Does the constant 1 match better? You're clearly losing something by going from max to sum.
$endgroup$
– maridia
Dec 7 '18 at 2:35
$begingroup$
1 is definitely too small. Also the constant should depend on $lambda$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:37
$begingroup$
1 is definitely too small. Also the constant should depend on $lambda$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:37
$begingroup$
Are you sure? Take a look at this paper: arxiv.org/pdf/0903.4373.pdf Apparently $M_n$ becomes super concentrated as $n to infty$ and with high probability lies in an interval of length 1 located $~ log n /log log n$ independent of $lambda$.
$endgroup$
– maridia
Dec 7 '18 at 2:48
$begingroup$
Are you sure? Take a look at this paper: arxiv.org/pdf/0903.4373.pdf Apparently $M_n$ becomes super concentrated as $n to infty$ and with high probability lies in an interval of length 1 located $~ log n /log log n$ independent of $lambda$.
$endgroup$
– maridia
Dec 7 '18 at 2:48
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The paper https://arxiv.org/pdf/0903.4373.pdf mentions that as $n to infty$, $M_n$ becomes concentrated at two adjacent values located asymptotically at $sim log n/ log log n$ independent of $lambda$ with probability approaching 1. Even tighter estimates are given there.
answered Dec 7 '18 at 2:55
maridiamaridia
1,065113
$endgroup$
$begingroup$
Hmm interesting, can you clarify how tight the bounds are exactly? The paper does not give much detail on the rate of convergence
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:57
$begingroup$
You can see from the Figure 3. It's really tight apparently. They claim the formula they give has error less than 1 (at least over the values of $n$ and $lambda$ in that figure). They don't seem to offer much in the way of proofs.
$endgroup$
– maridia
Dec 7 '18 at 2:59
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%2f3028882%2fupper-bound-on-expected-value-of-n-i-i-d-poisson-random-variables%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
$begingroup$
The paper https://arxiv.org/pdf/0903.4373.pdf mentions that as $n to infty$, $M_n$ becomes concentrated at two adjacent values located asymptotically at $sim log n/ log log n$ independent of $lambda$ with probability approaching 1. Even tighter estimates are given there.
answered Dec 7 '18 at 2:55
maridiamaridia
1,065113
$endgroup$
$begingroup$
Hmm interesting, can you clarify how tight the bounds are exactly? The paper does not give much detail on the rate of convergence
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:57
$begingroup$
You can see from the Figure 3. It's really tight apparently. They claim the formula they give has error less than 1 (at least over the values of $n$ and $lambda$ in that figure). They don't seem to offer much in the way of proofs.
$endgroup$
– maridia
Dec 7 '18 at 2:59
add a comment |
$begingroup$
The paper https://arxiv.org/pdf/0903.4373.pdf mentions that as $n to infty$, $M_n$ becomes concentrated at two adjacent values located asymptotically at $sim log n/ log log n$ independent of $lambda$ with probability approaching 1. Even tighter estimates are given there.
answered Dec 7 '18 at 2:55
maridiamaridia
1,065113
$endgroup$
$begingroup$
Hmm interesting, can you clarify how tight the bounds are exactly? The paper does not give much detail on the rate of convergence
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:57
$begingroup$
You can see from the Figure 3. It's really tight apparently. They claim the formula they give has error less than 1 (at least over the values of $n$ and $lambda$ in that figure). They don't seem to offer much in the way of proofs.
$endgroup$
– maridia
Dec 7 '18 at 2:59
add a comment |
$begingroup$
The paper https://arxiv.org/pdf/0903.4373.pdf mentions that as $n to infty$, $M_n$ becomes concentrated at two adjacent values located asymptotically at $sim log n/ log log n$ independent of $lambda$ with probability approaching 1. Even tighter estimates are given there.
answered Dec 7 '18 at 2:55
maridiamaridia
1,065113
$endgroup$
The paper https://arxiv.org/pdf/0903.4373.pdf mentions that as $n to infty$, $M_n$ becomes concentrated at two adjacent values located asymptotically at $sim log n/ log log n$ independent of $lambda$ with probability approaching 1. Even tighter estimates are given there.
answered Dec 7 '18 at 2:55
maridiamaridia
1,065113
edited Dec 7 '18 at 3:04
answered Dec 7 '18 at 2:55
maridiamaridia
1,065113
answered Dec 7 '18 at 2:55
maridiamaridia
1,065113
answered Dec 7 '18 at 2:55
maridiamaridia
1,065113
1,065113
$begingroup$
Hmm interesting, can you clarify how tight the bounds are exactly? The paper does not give much detail on the rate of convergence
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:57
$begingroup$
You can see from the Figure 3. It's really tight apparently. They claim the formula they give has error less than 1 (at least over the values of $n$ and $lambda$ in that figure). They don't seem to offer much in the way of proofs.
$endgroup$
– maridia
Dec 7 '18 at 2:59
add a comment |
$begingroup$
Hmm interesting, can you clarify how tight the bounds are exactly? The paper does not give much detail on the rate of convergence
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:57
$begingroup$
You can see from the Figure 3. It's really tight apparently. They claim the formula they give has error less than 1 (at least over the values of $n$ and $lambda$ in that figure). They don't seem to offer much in the way of proofs.
$endgroup$
– maridia
Dec 7 '18 at 2:59
$begingroup$
Hmm interesting, can you clarify how tight the bounds are exactly? The paper does not give much detail on the rate of convergence
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:57
$begingroup$
Hmm interesting, can you clarify how tight the bounds are exactly? The paper does not give much detail on the rate of convergence
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:57
$begingroup$
You can see from the Figure 3. It's really tight apparently. They claim the formula they give has error less than 1 (at least over the values of $n$ and $lambda$ in that figure). They don't seem to offer much in the way of proofs.
$endgroup$
– maridia
Dec 7 '18 at 2:59
$begingroup$
You can see from the Figure 3. It's really tight apparently. They claim the formula they give has error less than 1 (at least over the values of $n$ and $lambda$ in that figure). They don't seem to offer much in the way of proofs.
$endgroup$
– maridia
Dec 7 '18 at 2:59
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%2f3028882%2fupper-bound-on-expected-value-of-n-i-i-d-poisson-random-variables%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
$begingroup$
Some back of the envelope calculations lead me to believe that is the right asymptotic growth. What numerics do you have to show it's not tight? Is it the $log n/ log log n$ asymptotic or just the constant $lambda+1$?
$endgroup$
– maridia
Dec 7 '18 at 2:24
$begingroup$
Just the constant $lambda + 1$. I do think its $O(log n / log log n)$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:27
$begingroup$
Does the constant 1 match better? You're clearly losing something by going from max to sum.
$endgroup$
– maridia
Dec 7 '18 at 2:35
$begingroup$
1 is definitely too small. Also the constant should depend on $lambda$.
$endgroup$
– Sandeep Silwal
Dec 7 '18 at 2:37
$begingroup$
Are you sure? Take a look at this paper: arxiv.org/pdf/0903.4373.pdf Apparently $M_n$ becomes super concentrated as $n to infty$ and with high probability lies in an interval of length 1 located $~ log n /log log n$ independent of $lambda$.
$endgroup$
– maridia
Dec 7 '18 at 2:48