[WP34s] Inverse discrete probability distributions « Next Oldest | Next Newest »

 ▼ Eduardo Duenez Unregistered Posts: 56 Threads: 10 Joined: May 2006 05-15-2012, 12:30 PM Hello all, The post will be long, but I see no other way to make what I think is a very important point clearly enough. I was helping my daughter with her homework. She had to spin a roulette many times and count the frequencies of different outcomes. I wrote a 34s program to do a Monte Carlo simulation. That way she could do about 1000 rolls in 2 seconds (a loop calling RAN# and increasing the appropriate register each time). Just for fun, I decided to write a second program to do the same but using the inverse binomial distribution instead, only to quickly realize that the implementation of inverse discrete distributions on the 34s is "off by one". Let me explain. For simplicity let us consider the geometric distribution, say with parameter p=0.5 stored in J. Such a geometric variable takes the value m=0 with probability 1/2, m=1 with probability 1/4, m=2 with prob=1/8, etc. The distribution function (the function Geom in the 34s), is the function F(x) defined for all real values of x as follows: F(x) = 0 if x<0 F(x) = 1/2 if 0<=x<1 F(x) = 3/4 if 1<=x<2 F(x) = 7/8 if 2<=x<3 ... F(x) = 1 - 1/2^n if n-1<=x=0 are almost always one unit smaller than they ought to be. The values returned should be: Geom-1(x) is undefined if x<0 (one can probably argue this should be either -1, or -infinity, or NaN. The point is that nobody should ever need to evaluate an inverse distribution function when the argument is not in the range 0<=x<=1.), Geom-1(x) = 0 if 0<=x<=1/2, Geom-1(x) = 1 if 1/2= 0.5. What you seem to want is for the inverse to round up. I.e. the smallest integer n such that Pr(x <= n) > p. Both approaches are valid, the question is which one is more desirable here. Anyone want to make a case either way? The x<0 case is a bug and it will be fixed once this question is answered. - Pauli Edited: 15 May 2012, 9:03 p.m. Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 05-15-2012, 09:45 PM Quote:PS: I have the source code of the probability distributions, but I could not quickly make sense of it so as to point out more specifically how to implement the changes. Sorry. The final fix for the discrete distributions is at label qf_discrete_final in trunk/xrom/distributions/geometric.wp34s. Changing this is the easiest way to alter the rounding behaviour of all discrete distributions at once. The question remains: what behaviour is most desirable? - Pauli ▼ Eduardo Duenez Unregistered Posts: 56 Threads: 10 Joined: May 2006 05-15-2012, 11:27 PM Well, my original post advocates the "rounding up" method, and my opinion is strongly for it. Although I'm no Wolfram fanboy, they have a decent discussion on the "method of inverse transforms" http://demonstrations.wolfram.com/TheMethodOfInverseTransforms/ The "Details" section of that page explains how to use the inverse distribution function to generate a variable with any given distribution starting from a uniformly distributed variable as simulated by RAN#. I want to emphasize that this method *only* works if the inverse distribution is computed rounding up rather than down. I consider the use of the inverse distribution function in transforming uniformly distributed RAN# numbers into random numbers with a *different* distribution to be the quintessential use of these inverses (when "rounding up" is used, as I have advocated, in the way I find mathematically more natural). So I ask the question: Under what circumstances would it be more natural or useful to define the inverse distribution by rounding down? If I have a chance tomorrow, I'll try to find a proper reference (e.g., a textbook) on this matter. Eduardo Eduardo Duenez Unregistered Posts: 56 Threads: 10 Joined: May 2006 05-16-2012, 11:00 AM For reference, here's a couple of web pages describing how the inverse distribution function should be defined (either of these is far better than the reference I gave in my original post, which although correct is just lecture notes for a sophomore-level course in actuarial models). First one, by faculty at the Computer Science Dept. of Ben Gurion University in Israel: Another one, written in complete generality (using slightly higher mathematical lingo and including a proof of the Inverse Distribution Theorem), by Ursa Pantle, a statistician at Universität Ulm in Germany: In a nutshell, for a variable with distribution F(x) = probability that the random variable takes values <=x, the generalized inverse distribution function is defined by: F-1(y) = infimum of values x such that F(x)>=y. In particular, if F(x) < y then F-1(y) must be at least x, and in fact if the underlying distribution is discrete, then F-1(y)>x ---in other words, rounding must be done up, never down. Eduardo ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 05-16-2012, 07:34 PM These links are talking about generating distributed random numbers -- this doesn't necessary relate to the inverse cumulative distribution function for a discrete random variable. The inverse function is ill defined -- both what the 34S and what you want are inverses in the sense that they return the correct values over the integers which is the domain of the discrete distributions. That all said, nobody else has said anything thus far and I really don't mind which way these functions are defined (it is only an INC or DEC between them), so I'll go ahead and change them to the upward rounding flavours in due course. - Pauli ▼ Eduardo Duenez Unregistered Posts: 56 Threads: 10 Joined: May 2006 05-16-2012, 11:06 PM Quote: That all said, nobody else has said anything thus far and I really don't mind which way these functions are defined (it is only an INC or DEC between them), so I'll go ahead and change them to the upward rounding flavours in due course. Precisely, since the strict inverses are undefined for most real numbers, it becomes a matter of extending the definition in the most useful manner. Probabilists and statisticians have a preferred way of defining this generalized inverse (viz., the documents I have referenced in my prior posts in this thread). I noticed the 34s inverse discrete distribution functions differ from such definition in most of their domain, and I have tried pointing out so. That said, I certainly do not wish to impose the work on you or the 34s team. I'm sure I can figure out how to make the code changes myself and contribute them to the project given a little time. So long as the changes are welcome, that is. Eduardo ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 05-16-2012, 11:38 PM The changes are already done, just not built yet. They'll need testing however... The only constraint I remember on discrete distributions was they had to be right continuous and both of these definitions are that. Well, beyond always being non-negative and integrating/summing to unity as all distributions must. It's been a while since I classed myself a statistician and longer still since I studied postgraduate probability theory so I might have forgotten something.... Anyway, the point is moot now. - Pauli ▼ Eduardo Duenez Unregistered Posts: 56 Threads: 10 Joined: May 2006 05-17-2012, 12:11 PM Quote: The changes are already done, just not built yet. They'll need testing however... Consider me first in line to test! (In due course.) Eduardo ▼ fhub Unregistered Posts: 1,216 Threads: 75 Joined: Jun 2011 05-17-2012, 12:31 PM Quote: Consider me first in line to test! (In due course.) Well, you can test! ;-) The changes are already built-in: http://wp34s.svn.sourceforge.net/viewvc/wp34s?view=revision&revision=3054 Franz

 Possibly Related Threads… Thread Author Replies Views Last Post [HP Prime]How to get Discrete-Time Fourier Transform uklo 0 1,514 11-18-2013, 08:02 PM Last Post: uklo Inverse binomial Richard Berler 7 2,547 07-09-2013, 06:23 AM Last Post: Marcus von Cube, Germany SandMath routine of the week: Inverse Gamma Function Ángel Martin 39 9,273 03-24-2013, 08:19 AM Last Post: peacecalc [WP34S] WP34S firmware on the AT91SAM7L-STK dev kit? jerome ibanes 1 1,189 10-04-2012, 04:59 PM Last Post: Paul Dale [WP34S] Inverse F Distribution--Danged "Domain Error" Issue is Back Les Wright 16 4,463 05-23-2012, 10:28 PM Last Post: Les Wright [WP34S] Curious Bug in Inverse Normal Function Les Wright 61 12,530 05-01-2012, 02:44 AM Last Post: Paul Dale [WP34S] Inverse t CDF throws "Domain Error" for probabilities close to 0.5 Les Wright 10 2,702 04-19-2012, 03:25 AM Last Post: Paul Dale [WP34S] Bug in Inverse CDF for F-distribution Les Wright 19 4,194 04-15-2012, 11:17 AM Last Post: Dieter 32E's Normal & Inverse Normal Distribution Matt Agajanian 27 6,864 04-14-2012, 06:07 PM Last Post: Dieter [wp34s] Incomplete Gamma on the wp34s Les Wright 18 5,016 12-06-2011, 11:07 AM Last Post: Namir

Forum Jump: