random-distributions/binomial.ss
;;; PLT Scheme Science Collection
;;; random-distributions/bernoulli.ss
;;; Copyright (c) 2004-2007 M. Douglas Williams
;;;
;;; This library is free software; you can redistribute it and/or
;;; modify it under the terms of the GNU Lesser General Public
;;; License as published by the Free Software Foundation; either
;;; version 2.1 of the License, or (at your option) any later version.
;;;
;;; This library is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
;;; Lesser General Public License for more details.
;;;
;;; You should have received a copy of the GNU Lesser General Public
;;; License along with this library; if not, write to the Free
;;; Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
;;; 02111-1307 USA.
;;;
;;; -------------------------------------------------------------------
;;;
;;; This module implements the bernoulli distribution.  It is based on
;;; the Random Number Distributions in the GNU Scientific Library.
;;;
;;; Version  Date      Description
;;; 1.0.0    09/28/04  Marked as ready for Release 1.0.  Added
;;;                    contracts for functions.  (Doug Williams)
;;; 2.0.0    11/19/07  Added unchecked versions of functions and
;;;                    getting ready for PLT Scheme 4.0 (Doug Williams)

(module binomial mzscheme
  
  (require (lib "contract.ss"))
  
  (provide
   (rename random-binomial unchecked-random-binomial)
   (rename binomial-pdf unchecked-binomial-pdf))
  
  (provide/contract
   (random-binomial
    (case-> (-> random-source? (real-in 0.0 1.0) natural-number/c natural-number/c)
            (-> (real-in 0.0 1.0) natural-number/c natural-number/c)))
   (binomial-pdf
    (-> natural-number/c (real-in 0.0 1.0) natural-number/c (>=/c 0.0))))
  
  (require "../random-source.ss")
  (require "../special-functions/gamma.ss")
  (require "beta.ss")
  
  ;; random-binomial: random-source x real x integer -> integer
  ;; random-binomial: real x integer -> integer
  ;;
  ;; This routine returns a random variate from a binomial distribution
  ;; with n independent trials and probability p.
  (define random-binomial
    (case-lambda
      ((r p n)
       (let ((a 0)
             (b 0)
             (k 0))
         (let loop ()
           (if (> n 10)
               (begin
                 (set! a (+ 1 (quotient n 2)))
                 (set! b (+ 1 n (- a)))
                 (let ((x (unchecked-random-beta 
                           r
                           (exact->inexact a)
                           (exact->inexact b))))
                   (if (>= x p)
                       (begin
                         (set! n (- a 1))
                         (set! p (/ p x)))
                       (begin
                         (set! k (+ k a))
                         (set! n (- b 1))
                         (set! p (/ (- p x) (- 1.0 x))))))
                 (loop))))
         (do ((i 0 (+ i 1)))
             ((= i n) k)
           (let ((u (unchecked-random-uniform r)))
             (if (< u p)
                 (set! k (+ k 1)))))))
      ((p n)
       (random-binomial (current-random-source) p n))))
  
  ;; binomial-pdf: integer x real x integer -> real
  ;;
  ;; This function computes the probability density p(x) at x for a
  ;; binomial distribution with n independent trials and probability p.
  (define (binomial-pdf k p n)
    (if (> k n)
        0.0
        (let ((ln_c_nk (unchecked-lnchoose n k)))
          (exp (+ ln_c_nk
                  (* k (log p))
                  (* (- n k)
                     (log (- 1.0 p))))))))
  
)