Create a gist now

Instantly share code, notes, and snippets.

Simulation of Coupon Collector's problem in K (Kona)
/ Coupon collector's problem
/ E.g. how many times is required to throw a die
/ until all 6 values has been shown.
/
/ Or: How many coupons must be bought to get the the complete collection.
/
/ http://en.wikipedia.org/wiki/Coupon_collector%27s_problem
/ Let's simulate the die version.
/ Define some helper functions:
/ frequency table
table:{b@<b:(x@*:'a),'#:'a:=x}
/ average (arithmetic mean)
am:{(+/x)%#x}
/ Here is the simulation. See the explanations below.
table ({#{p:();while[6>#?p;(p,:1?6)];p}[]}'!100)
/ Sample result:
/ (6 1
/ 7 3
/ 8 5
/ 9 7
/ 10 5
/ 11 10
/ 12 10
/ 13 6
/ 14 9
/ 15 8
/ 16 5
/ 17 7
/ 18 7
/ 19 4
/ 21 1
/ 22 3
/ 23 3
/ 24 1
/ 27 2
/ 29 2
/ 49 1)
/ The average value is about 14...
/ Here for 100 simulations
am ({#{p:();while[6>#?p;(p,: 1 ? 6)];p}[]}' !100)
/ Sample result: 14.9
/ Here for 10000 simulations
am ({#{p:();while[6>#?p;(p,: 1 ? 6)];p}[]}' !10000)
/ Sample result: 14.7029
am ({#{p:();while[6>#?p;(p,: 1 ? 6)];p}[]}' !10000)
/ Sample result: 14.6794
/ 100000 runs should be more accurate.
am ({#{p:();while[6>#?p;(p,: 1 ? 6)];p}[]}' !100000)
/ Sample result: 14.70257
/ Some explanations:
/ while[condition; do something]
/ where the condition is false if 0, and true 1
/ The condition is thus:
/ 6>#?p
/
/ ?p
/ is the number of unique values in the vector p.
/
/ #?p
/ is the number of unique values
/
/ p is first assigned to an empty list
/ p:()
/ and is then in the while clause appended with the
/ selected (randomized) number:
/ (p,:1?6)
/
/ In short, we append p until we have got all different values
/ 0..5
/ The last
/ {...} '!100
/ means that we run the function { ... } for 100 times.
/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment