Bound on the tail of a Poisson branching processExtinction probability of binomial branching process tends to poisson one.The minimum degree of G(n,p) with p=(1+o(1))ln(n)/nBranching process - generating functionNumber of k-cliques in random graphs is PoissonBranching process interpretation of giant componentClique numbers and Theorem 4.5.1 in “The Probabilistic Method” by Alon and SpencerRandom graph processFinding threshold for Erdos-Renyi random graph to be connected using branching processBinomial converging to Poisson in branching process view of $G(n,p)$There is probability $O(p^k)=O(n^-k)$ that $C(v)$ has more than $k-1$ edges?
Why restrict private health insurance?
Why do we say 'Pairwise Disjoint', rather than 'Disjoint'?
What is better: yes / no radio, or simple checkbox?
Is this Paypal Github SDK reference really a dangerous site?
Boss Telling direct supervisor I snitched
School performs periodic password audits. Is my password compromised?
(Codewars) Linked Lists-Sorted Insert
Create chunks from an array
How can I portion out frozen cookie dough?
Rationale to prefer local variables over instance variables?
PTIJ: Sport in the Torah
Yet another question on sums of the reciprocals of the primes
Are all players supposed to be able to see each others' character sheets?
How do I raise a figure (placed with wrapfig) to be flush with the top of a paragraph?
How would an energy-based "projectile" blow up a spaceship?
How can I wire a Raspberry Pi to an 8-relay board in a tidy professional manner?
Did Amazon pay $0 in taxes last year?
Is it possible to clone a polymorphic object without manually adding overridden clone method into each derived class in C++?
Do Paladin Auras of Differing Oaths Stack?
Giving a career talk in my old university, how prominently should I tell students my salary?
Called into a meeting and told we are being made redundant (laid off) and "not to share outside". Can I tell my partner?
Difference between `nmap local-IP-address` and `nmap localhost`
Finding the minimum value of a function without using Calculus
What is this tube in a jet engine's air intake?
Bound on the tail of a Poisson branching process
Extinction probability of binomial branching process tends to poisson one.The minimum degree of G(n,p) with p=(1+o(1))ln(n)/nBranching process - generating functionNumber of k-cliques in random graphs is PoissonBranching process interpretation of giant componentClique numbers and Theorem 4.5.1 in “The Probabilistic Method” by Alon and SpencerRandom graph processFinding threshold for Erdos-Renyi random graph to be connected using branching processBinomial converging to Poisson in branching process view of $G(n,p)$There is probability $O(p^k)=O(n^-k)$ that $C(v)$ has more than $k-1$ edges?
$begingroup$
I'm trying to understand this argument from "The Probabilsitic Method" book:
Let $T_c$ be the time of extinction for a Poisson branching process with parameter $c$. The authors prove that $$P[T_c=k] = frace^-ck(ck)^k-1 k! .$$
From this they argue that, by Stirling's approximation, $$P[T_c = k] sim frac12 pik^-3/2c^-1(ce^1-c)^k.$$
If we assume $c<1$, then $ce^1-c<1$ and $P[T_c=k]$ approaches $0$ at exponential speed.
This is where I get lost: This gives a bound on the tail distribution: $P[T_c ge u] < e^-u(alpha +o(1)),$ where $alpha = c-1-ln c > 0$.
Where does this come from? Is it some application of the Chernoff bound (if so, which version?), or is it more elementary than that?
random-graphs probabilistic-method
asked yesterday
theQmantheQman
44638
$endgroup$
add a comment |
$begingroup$
I'm trying to understand this argument from "The Probabilsitic Method" book:
Let $T_c$ be the time of extinction for a Poisson branching process with parameter $c$. The authors prove that $$P[T_c=k] = frace^-ck(ck)^k-1 k! .$$
From this they argue that, by Stirling's approximation, $$P[T_c = k] sim frac12 pik^-3/2c^-1(ce^1-c)^k.$$
If we assume $c<1$, then $ce^1-c<1$ and $P[T_c=k]$ approaches $0$ at exponential speed.
This is where I get lost: This gives a bound on the tail distribution: $P[T_c ge u] < e^-u(alpha +o(1)),$ where $alpha = c-1-ln c > 0$.
Where does this come from? Is it some application of the Chernoff bound (if so, which version?), or is it more elementary than that?
random-graphs probabilistic-method
asked yesterday
theQmantheQman
44638
$endgroup$
add a comment |
$begingroup$
I'm trying to understand this argument from "The Probabilsitic Method" book:
Let $T_c$ be the time of extinction for a Poisson branching process with parameter $c$. The authors prove that $$P[T_c=k] = frace^-ck(ck)^k-1 k! .$$
From this they argue that, by Stirling's approximation, $$P[T_c = k] sim frac12 pik^-3/2c^-1(ce^1-c)^k.$$
If we assume $c<1$, then $ce^1-c<1$ and $P[T_c=k]$ approaches $0$ at exponential speed.
This is where I get lost: This gives a bound on the tail distribution: $P[T_c ge u] < e^-u(alpha +o(1)),$ where $alpha = c-1-ln c > 0$.
Where does this come from? Is it some application of the Chernoff bound (if so, which version?), or is it more elementary than that?
random-graphs probabilistic-method
asked yesterday
theQmantheQman
44638
$endgroup$
I'm trying to understand this argument from "The Probabilsitic Method" book:
Let $T_c$ be the time of extinction for a Poisson branching process with parameter $c$. The authors prove that $$P[T_c=k] = frace^-ck(ck)^k-1 k! .$$
From this they argue that, by Stirling's approximation, $$P[T_c = k] sim frac12 pik^-3/2c^-1(ce^1-c)^k.$$
If we assume $c<1$, then $ce^1-c<1$ and $P[T_c=k]$ approaches $0$ at exponential speed.
This is where I get lost: This gives a bound on the tail distribution: $P[T_c ge u] < e^-u(alpha +o(1)),$ where $alpha = c-1-ln c > 0$.
Where does this come from? Is it some application of the Chernoff bound (if so, which version?), or is it more elementary than that?
random-graphs probabilistic-method
random-graphs probabilistic-method
asked yesterday
theQmantheQman
44638
asked yesterday
theQmantheQman
44638
asked yesterday
theQmantheQman
44638
asked yesterday
theQmantheQman
44638
asked yesterday
theQmantheQman
44638
44638
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
$$P(T_c ge u) = sum_k=u^infty P(T_c=k)
le frac12pi u^-3/2 c^-1 sum_k=u^infty (c e^1-c)^k
= frac12pi u^-3/2 c^-1 frac11-ce^1-c cdot(c e^1-c)^u.$$
The last term is
$$(ce^1-c)^u = e^-ualpha$$
with $alpha := c-1-ln c$.
The logarithm of the other terms is
$$ln left(frac12pi u^-3/2 c^-1 frac11-ce^1-cright)
= -frac32 ln u + C_c = o(u)$$
where $C_c = lnleft(frac12pi c^-1 frac11-ce^1-cright)$.
Exponentiating both sides yields
$$frac12pi u^-3/2 c^-1 frac11-ce^1-c = e^-u o(1).$$
answered yesterday
angryavianangryavian
42.1k23381
$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%2f3140414%2fbound-on-the-tail-of-a-poisson-branching-process%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$
$$P(T_c ge u) = sum_k=u^infty P(T_c=k)
le frac12pi u^-3/2 c^-1 sum_k=u^infty (c e^1-c)^k
= frac12pi u^-3/2 c^-1 frac11-ce^1-c cdot(c e^1-c)^u.$$
The last term is
$$(ce^1-c)^u = e^-ualpha$$
with $alpha := c-1-ln c$.
The logarithm of the other terms is
$$ln left(frac12pi u^-3/2 c^-1 frac11-ce^1-cright)
= -frac32 ln u + C_c = o(u)$$
where $C_c = lnleft(frac12pi c^-1 frac11-ce^1-cright)$.
Exponentiating both sides yields
$$frac12pi u^-3/2 c^-1 frac11-ce^1-c = e^-u o(1).$$
answered yesterday
angryavianangryavian
42.1k23381
$endgroup$
add a comment |
$begingroup$
$$P(T_c ge u) = sum_k=u^infty P(T_c=k)
le frac12pi u^-3/2 c^-1 sum_k=u^infty (c e^1-c)^k
= frac12pi u^-3/2 c^-1 frac11-ce^1-c cdot(c e^1-c)^u.$$
The last term is
$$(ce^1-c)^u = e^-ualpha$$
with $alpha := c-1-ln c$.
The logarithm of the other terms is
$$ln left(frac12pi u^-3/2 c^-1 frac11-ce^1-cright)
= -frac32 ln u + C_c = o(u)$$
where $C_c = lnleft(frac12pi c^-1 frac11-ce^1-cright)$.
Exponentiating both sides yields
$$frac12pi u^-3/2 c^-1 frac11-ce^1-c = e^-u o(1).$$
answered yesterday
angryavianangryavian
42.1k23381
$endgroup$
add a comment |
$begingroup$
$$P(T_c ge u) = sum_k=u^infty P(T_c=k)
le frac12pi u^-3/2 c^-1 sum_k=u^infty (c e^1-c)^k
= frac12pi u^-3/2 c^-1 frac11-ce^1-c cdot(c e^1-c)^u.$$
The last term is
$$(ce^1-c)^u = e^-ualpha$$
with $alpha := c-1-ln c$.
The logarithm of the other terms is
$$ln left(frac12pi u^-3/2 c^-1 frac11-ce^1-cright)
= -frac32 ln u + C_c = o(u)$$
where $C_c = lnleft(frac12pi c^-1 frac11-ce^1-cright)$.
Exponentiating both sides yields
$$frac12pi u^-3/2 c^-1 frac11-ce^1-c = e^-u o(1).$$
answered yesterday
angryavianangryavian
42.1k23381
$endgroup$
$$P(T_c ge u) = sum_k=u^infty P(T_c=k)
le frac12pi u^-3/2 c^-1 sum_k=u^infty (c e^1-c)^k
= frac12pi u^-3/2 c^-1 frac11-ce^1-c cdot(c e^1-c)^u.$$
The last term is
$$(ce^1-c)^u = e^-ualpha$$
with $alpha := c-1-ln c$.
The logarithm of the other terms is
$$ln left(frac12pi u^-3/2 c^-1 frac11-ce^1-cright)
= -frac32 ln u + C_c = o(u)$$
where $C_c = lnleft(frac12pi c^-1 frac11-ce^1-cright)$.
Exponentiating both sides yields
$$frac12pi u^-3/2 c^-1 frac11-ce^1-c = e^-u o(1).$$
answered yesterday
angryavianangryavian
42.1k23381
answered yesterday
angryavianangryavian
42.1k23381
answered yesterday
angryavianangryavian
42.1k23381
answered yesterday
angryavianangryavian
42.1k23381
42.1k23381
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%2f3140414%2fbound-on-the-tail-of-a-poisson-branching-process%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
