Skip to main content
gamedev.net
🔒 Locked

Poisson disribution calculation

Started by timmy2 May 21, 2006 at 2:41 PM 1 replies 500+ views
Original Post
timmy2
timmy2
Hi I am looking for a way to calculate the function p=Lambda*t*e^(-Lambda*t). the paramter t is the missing paramter. the problem is I want to do it very fast. I think there is a way to do it because this is the poisson distribution, for n=1 (the first occurence). If you have other way to calculate the first occurence time , I will be happy to see it. Thanks Timmy
Wasting Time
Wasting Time
I assume you mean that p is specified and you want to find a t that is mapped to it? The function p(t) = L*t*exp(-L*t) [L is your Lambda, exp(x) is your e^x] has two values of t mapped to each p in [0,1/e), but only one value mapped to p = 1/e. The derivative is p'(t) = L*(1-L*t)*exp(-L*t). It is zero when t = 1/L. The function is a maximum at p(1/L) = 1/e. You want to choose q and solve p(t) = q for the values of t. It is necessary that 0 <= q <= 1/e. If q = 1/e, the answer is immediate. The rest of this post assumes q < 1/e.

Use Newton's method applied to the function f(t) = p(t) - q. The initial guess is some value t[0]. The iterates are t[n+1] = t[n] - f(t[n])/f'(t[n]), for n >= 0. So you have t[n+1] = t[n] - (L*t[n]*exp(-L*t[n]) - q)/(L*(1-L*t)*exp(-L*t[n])).

Let r0 and r1 be the values for which p(r0) = q and p(r1) = q, with r0 < 1/e < r1. If you choose t[0] = 0, or any value smaller than r0, the numerator of the last term (the fraction term) in the Newton's iterate is negative since p(t) is an increasing function on [0,1/e]. The denominator of that fraction is positive, since 1-L*t > 0 for t in [0,1/e). That means t[1] = t[0] + positiveQuantity, and so t[1] > t[0]. This will happen on successive iterates, t[n+1] > t[n], due to the same sign-based argument and due to f"(t) < 0 on [0,1/e). You have an increasing sequence bounded above, so it has a limit. The Newton's iterates will converge to r0.

Since you want the *first* time (I think), there is no need to analyze the algorithm for obtaining r1.
timmy2
timmy2
Thank you very much for your help.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.