#| 

  Can you hop to the lily pad? in Racket/Gamble 

  From Can you hop to the lily pad?
  https://laurentlessard.com/bookproofs/can-you-hop-to-the-lily-pad/
  """
  You are a frog in a pond with an infinite number of lily pads in a 
  line, marked "1," "2," "3," etc. You are currently on pad 2, and 
  your goal is to make it to pad 1. From any given pad, there are 
  specific probabilities that you’ll jump to another pad: Whenever you 
  are on pad k, you will hop to pad k-1 with probability 1/k, and you 
  will hop to pad k+1 with probability (k-1)/k.

  What is the probability that you will ultimately make it to pad 1? 
  """

  (Via Pascal Bercker).

With a limit of 25 (took 7 minutes and 8s)

variable : last-pad
1: 14131159510139402534335173833533297/22355751135315921338695680000000000 (0.6321039908078091)
24: 1425481391569490617177/16483965967169981280000 (0.08647684631286713)
26: 154883957203/2007835830000 (0.07713975161156478)
22: 3002930905483232902649053769/42978259928244210050020700160 (0.06987092801097292)
20: 1355748871936204869205458089569021219/29517913650277380945919082301480960000 (0.04592969841970741)
...
10: 652178644255580855992082931484550273961461787618709/509431005775759471762159307950374972964995072000000000 (0.0012802099535783964)
8: 11281553651075855935400000402160239480867482701071/21617371480666144853836026837184934660014080000000000 (0.0005218744407092093)
6: 4882638952915410241198759136441010334204713523/24701050642929458446268141639454425088000000000000 (0.0001976692823109951)
4: 8008657040352550618034033169861774882193/120962618964023517885389814300672000000000000 (6.62077020896387e-5)
2: 66801404149056590509527341929875089/4028059239561222706806187622400000000000 (1.6584017308626594e-5)
mean: 11428538992217626138115628542251884005970591055390580366186663903855376589/1263977918058383575591935978859315803096312190473565571776512000000000000 (9.041723616321704)

variable : len
1: 1/2 (0.5)
26: 8224591625176518804360506166466703/22355751135315921338695680000000000 (0.3678960091921909)
3: 1/12 (0.08333333333333333)
5: 1/36 (0.027777777777777776)
7: 49/4320 (0.011342592592592593)
...
17: 2198367208193/8065516032000000 (0.00027256373919175915)
19: 5024863664465957/37262684067840000000 (0.00013484975090140446)
21: 1921322898220933003/28692266732236800000000 (6.696309204675897e-5)
23: 2067781150904326884335171/62037271437773119488000000000 (3.33312717174937e-5)
25: 371472409643107808193170994937/22355751135315921338695680000000000 (1.6616413709145468e-5)
mean: 237822992285471730651744966946548383/22355751135315921338695680000000000 (10.638112351759768)

variable : p
#t: 14131159510139402534335173833533297/22355751135315921338695680000000000 (0.6321039908078091)
#f: 8224591625176518804360506166466703/22355751135315921338695680000000000 (0.3678960091921909)
mean: 14131159510139402534335173833533297/22355751135315921338695680000000000 (0.6321039908078091)

   The value of 0.6321039908078091 is suspiciously near 1-1/exp(1) (~0.63212055882855767840).
   The difference is 0.00001656802074857840.


  * importance-sampler (100000 samples) and a limit 100

variable : last-pad
1: 0.63156
97: 0.06605000000000003
95: 0.06396000000000003
99: 0.05519000000000003
93: 0.05236000000000002
...
73: 9.000000000000005e-5
69: 6.000000000000003e-5
65: 1.0000000000000006e-5
67: 1.0000000000000006e-5
63: 1.0000000000000006e-5
mean: 35.55634000000002

variable : len
1: 0.4987100000000002
101: 0.3684400000000001
3: 0.08389000000000005
5: 0.027770000000000013
7: 0.011700000000000006
...
21: 6.000000000000003e-5
23: 2.0000000000000012e-5
33: 1.0000000000000006e-5
27: 1.0000000000000006e-5
29: 1.0000000000000006e-5
mean: 38.28562000000001

variable : p
#t: 0.63156
#f: 0.3684400000000001
mean: 0.63156



  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Racket page: http://www.hakank.org/racket/

|#

#lang gamble

; (require gamble/viz)
(require racket)
(require "gamble_utils.rkt")
; (require "gamble_distributions.rkt")


(define (model)
  (enumerate
   ; rejection-sampler
   ; importance-sampler
   ; mh-sampler

   (define start 2)

   (define target 1)   

   (define limit 25)

   (define (hop k n)
     (if (or (= k target) (> n limit))
         (list k n)
         (let [(h (categorical-vw (vector (- k 1) (+ k 1)) (vector (/ 1 k) (/ (- k 1) k))))]
           (hop h (add1 n)))))


   (define res (hop 2 0))

   (define last-pad (first res))
   (define len (second res))
   (define p (= last-pad 1))

   ; (show2 "last-pad" last-pad "len" len "p" p)
   
   (list last-pad len p)
   

   )
)

(show-marginals (model)
                (list "last-pad"
                      "len"
                      "p"
                       )
                #:num-samples 100000
                #:truncate-output 5
                ; #:skip-marginals? #t
                ; #:show-stats? #t
                ; #:credible-interval 0.84
                ; #:hpd-interval (list 0.84)
                ; #:show-histogram? #t
                ; #:show-percentiles? #t
                ; #:burn 0
                ; #:thin 0
                )