## Galton

### April 10, 2012

The program decomposes into three pieces: drop one marble, drop a series of marbles, and draw a histogram. Here’s the function to drop one marble, which merely needs to count the number of times the marble moves right, signalled when the random integer is 1:

`(define (drop bins)`

(do ((b bins (- b 1))

(z 0 (+ z (randint 2))))

((= b 1) z)))

Function `galton`

drops a series of marbles:

`(define (galton marbles bins)`

(let ((bs (make-vector bins 0)))

(do ((m 0 (+ m 1))) ((= m marbles) bs)

(let ((b (drop bins)))

(vector-set! bs b

(+ (vector-ref bs b) 1))))))

Then the histogram, which scales itself and is displayed horizontally, using an auxiliary function to draw the row of asterisks:

`(define (stars n)`

(do ((n n (- n 1))) ((zero? n) (newline))

(display #\*)))

`(define (histogram xs)`

(let* ((max-x (apply max (vector->list xs)))

(len (vector-length xs))

(n (ceiling (/ max-x len))))

(do ((x 0 (+ x 1))) ((= x len))

(stars (ceiling (/ (vector-ref xs x) n))))))

Here’s a sample run:

`> (histogram (galton 1000 8))`

*

**

******

********

********

*****

**

*

We used `randint`

from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/HatuCXPz.

[…] today’s Programming Praxis exercise, our goal is to simulate a Galton board and display the frequencies of […]

My Haskell solution (see http://bonsaicode.wordpress.com/2012/04/10/programming-praxis-galton/ for a version with comments):

In R, after realizing that the sum of 200 Bernoulli trials with p=0.5 (each success means falling to the right at a pin, incrementing the bin number by 1) is a binomial trial with n=200 and p=0.5, one obtains the final result thus.

That is a bar plot for 1000 balls through 200 levels of pins on the board, hence 201 bins. The real histogram command of R has also the tabulation of values built-in, but I think the bar plot obtained above looks nice for this.

Perl solution, output scaled to $MAX_WIDTH characters

Here’s a quick and dirty Galton board animation in Python 2.7.

My answer in Go:

Forth version, with a RNG developed in an earlier exercise (not included here.)

Execution: