## schematics-development — Discussion of Schematics project and code development

You can subscribe to this list here.

 2002 2003 2004 2005 2006 2007 2008 2013 Jan Feb Mar Apr May Jun Jul Aug Sep (21) Oct (24) Nov (80) Dec (13) Jan (13) Feb (34) Mar (22) Apr (21) May (48) Jun (33) Jul (3) Aug (2) Sep (3) Oct (12) Nov (12) Dec (7) Jan (22) Feb (5) Mar (58) Apr (80) May (74) Jun (79) Jul (15) Aug (122) Sep (63) Oct (8) Nov (1) Dec (2) Jan (13) Feb (24) Mar (5) Apr (16) May (27) Jun Jul (5) Aug Sep Oct (3) Nov (8) Dec (2) Jan (1) Feb (5) Mar (11) Apr (1) May (16) Jun (5) Jul (2) Aug Sep Oct (1) Nov (1) Dec (5) Jan (4) Feb (4) Mar (4) Apr (5) May (1) Jun Jul Aug (3) Sep (1) Oct (1) Nov (1) Dec (3) Jan (1) Feb Mar (1) Apr May (1) Jun (1) Jul (6) Aug (5) Sep (3) Oct Nov Dec Jan (1) Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
S M T W T F S

1
(2)
2
(4)
3

4
(1)
5
(6)
6
(7)
7

8

9
(3)
10
(2)
11
(1)
12
(5)
13
(3)
14
(4)
15

16
(1)
17
(1)
18

19

20
(1)
21

22

23

24

25
(1)
26

27
(3)
28

29

30
(2)
31
(1)

Showing 4 results of 4

 Re: [Schematics-development] discrete random variables From: - 2003-05-02 22:29:39 ```sebastian.egner@... wrote: > > Dear people at Schematics, > > Mike Sperber forwarded me a short discussion related to using > pseudo random values with given probability distribution. > In other words, given probabilities p[0], .., p[n-1] summing to one, > construct a pseudo-random process for values x in {0..n-1} > such that Pr{x = k} = p[k]. > > I would like to bring to your attention that there is a method to > draw the next pseudo-random value in O(1), after having > prepared a datastructure of size O(n). This method is known > as the "method of aliases" by A. J. Walker (Electronic Letters 1974). > It will be much faster than the code currently used in Schemathics > which uses time O(n) for drawing the next random value. > > For convenience, I just wrote some code for this :-) That's service. I'll incorporate this as soon as possible. [When exam start for real] -- Jens Axel Søgaard ```
 Re: [Schematics-development] Schemathics: Documentation of random variables From: - 2003-05-02 22:15:27 ```MJ Ray wrote: >Jens_Axel_Søgaard wrote: > > >>at all, but a so called distributiun [the set of >>distributions is a extension of the space of functions], >> >> > >Do you mean distributions? > Yes, but by distributions (also called generalized functions) I do not mean functions given by the distribution of a random variable. The relationship between functions and distribution are somewhat similar to the relationship between the reals R and the complex numbers C. During the process of solving an eqution of degree three, one can use numbers from C as temporary results, and in the end get a solution from R [which historically led to the discovery of C]. Thus some problems concerning real numbers is easier to solve, if one sees R as a subset if the larger space C. In physics Dirac needed a function with the properties 1. f(x) = 0 when x <> 0 2. integral f(x) from -oo to oo = 1 The equation 2. is not solvable in the space of real functions of one variable, since the integral of function does not depend on the value of f in any specific point. Nevertheless Dirac made calculations with a function named delta that satisfied equation 2, and got correct results (in the space of real functions of a real variabel). The idea is now to embed the set of functions in a larger space, where thus equation has a solution. The definition of distributions and a lenghty discussion can be found at MathWorld. ; The short version is: Generalized functions [a.ka.distributions] are defined as continuous linear functionals ; over a space ; of infinitely differentiable functions such that all continuous functions have derivatives which are themselves generalized functions. One clever thing (if I remember correctly) is that the differential operator can be extended to the entire space of distribution s.t. you (if you calculate in the space of distributions) suddenly can differentiate more functions than you used to. Hmm. This got pretty long, but I couldn't help my self. -- Jens Axel Søgaard ```
 [Schematics-development] discrete random variables From: - 2003-05-02 15:37:05 Attachments: Message as HTML ```Dear people at Schematics, Mike Sperber forwarded me a short discussion related to using pseudo random values with given probability distribution. In other words, given probabilities p[0], .., p[n-1] summing to one, construct a pseudo-random process for values x in {0..n-1} such that Pr{x = k} = p[k]. I would like to bring to your attention that there is a method to draw the next pseudo-random value in O(1), after having prepared a datastructure of size O(n). This method is known as the "method of aliases" by A. J. Walker (Electronic Letters 1974). It will be much faster than the code currently used in Schemathics which uses time O(n) for drawing the next random value. For convenience, I just wrote some code for this :-) If there would be a good implementation for priority queues around, the preparation phase could be improved... Cheers, Sebastian. ; Random Source for Discrete Distribution ; ======================================= ; ; Sebastian.Egner@..., 2-May-2003 ; in R5RS-Scheme using ; SRFI-23 (error), ; SRFI-27 (random sources), ; SRFI-42 (eager comprehensions) ; load this into Scheme48 0.57 with SRFI-27: ; ,config ,load srfi-27.scm ; ,open srfi-27 srfi-23 ; ,load ec.scm ; from srfi.schemers.org, SRFI-42 ; (random-source-make-discretes s w) ; given a source s of random bits in the sense of SRFI-27 ; and a vector w of n >= 1 non-negative real numbers, ; this procedure constructs and returns a procedure rand ; such that (rand) returns the next integer x in {0..n-1} ; from a pseudo random sequence with ; ; Pr{x = k} = w[k] / Sum(w[i] : i) ; ; for all k in {0..n-1}. (define (random-source-make-discretes s w) (define (check-weights w) (if (not (and (vector? w) (>= (vector-length w) 1) (forall?-ec (:vector wi w) (and (number? wi) (not (negative? wi)))))) (error "bad vector of weights" w))) (define (make-cutoff-alias w) (define eps (expt 10 -6)) (define n (vector-length w)) (define cutoff (make-vector n 1)) (define alias (make-vector n 0)) (define avg-w (/ (sum-ec (:vector wi w) wi) n)) (define b (vector-of-length-ec n (:vector wi w) (- wi avg-w))) (let loop ((sum-abs-b (sum-ec (:vector bi b) (abs bi)))) (if (< sum-abs-b eps) (list cutoff alias) (let ((imin 0) (bmin (vector-ref b 0)) (imax 0) (bmax (vector-ref b 0))) (do-ec (:vector bi (index i) b) (begin (if (< bi bmin) (begin (set! imin i) (set! bmin bi))) (if (> bi bmax) (begin (set! imax i) (set! bmax bi))))) (vector-set! cutoff imin (+ 1 (/ bmin avg-w))) (vector-set! alias imin imax) (vector-set! b imin 0) (vector-set! b imax (+ bmin bmax)) (loop (+ sum-abs-b (- (abs bmin)) (- (abs bmax)) (+ (abs (vector-ref b imax))))))))) (check-weights w) (let* ((c-a (make-cutoff-alias w)) (cutoff (car c-a)) (alias (cadr c-a)) (randi (random-source-make-integers s)) (randu (random-source-make-reals s)) (n (vector-length cutoff))) (lambda () (let ((i (randi n))) (if (< (randu) (vector-ref cutoff i)) i (vector-ref alias i)))))) ; example ;(define r1 ; (random-source-make-discretes ; default-random-source ; (vector-ec (: i 0 29) (* 0.1 (expt 0.9 i))))) ; Geo(0.1) ; ; now (r1) -> x in {0..29} with Pr{x = i} = w[i]/Sum(w[j] : j) ; where w[j] = 0.1 0.9^j. ; ;(define (hist rand n iters) ; gather a histogram ; (let ((h (make-vector n 0))) ; (do-ec (:range i iters) ; (:let x (rand)) ; (vector-set! h x (+ (vector-ref h x) 1))) ; h)) ; ; ,time (hist r1 30 1000000) ; -> a vector approximating the geometric distribution ---- Dr. Sebastian Egner Senior Scientist Philips Research Laboratories Prof. Holstlaan 4 (postbox WY63, kamer WY 6-55) 5656 AA Eindhoven The Netherlands tel: +31 40 27-42069 *** new telephone number fax: +31 40 27-42566 *** new fax number email: sebastian.egner@...```
 Re: [Schematics-development] Schemathics: Documentation of random variables From: MJ Ray - 2003-05-02 13:29:00 ```=?iso-8859-1?Q?Jens_Axel_S=F8gaard?= wrote: > at all, but a so called distributiun [the set of > distributions is a extension of the space of functions], Do you mean distributions? I would have thought that the set of distributions was a restriction of the space of functions, because of the requirements for them to have certain properties. ICBW: it's been far too long. -- MJR http://mjr.towers.org.uk/ IM: slef@... This is my home web site. This for Jabber Messaging. How's my writing? Let me know via any of my contact details. ```

Showing 4 results of 4