Review Theorem I.1 in AC if you don’t remember the basic constructions.
Appendix A.1 and A.4 in AC. This goes over the cycle construction, but leaves
much to the reader. You don’t necessarily need to follow every step, but it
would be good to have an idea of where this is going.
Neil’s expanded write-up
of the cycle construction derivation.
Agenda:
Coffee roast tasting? Graham and Amy tried some different roasts on the same
green coffee beans. I’ll be making espresso for anybody interested.
Continue deriving the cycle construction, which we skipped when originally
visiting Theorem I.1. (Neil will be doing this one.)
Last time we left off after deriving bivariate Möbius inversion. We’ll do
some review and then continue from there.
We’re planning to wrap up the cycle construction in this session so we can
move on to worked examples (finally)!
For people who missed this series, Neil’s
write-up is a good
starting point. It closely follows the Analytic Combinatorics appendices
while filling in some of the gaps. I might add some dedicated posts covering
this as well.
Review the Thrill Digger challenge and rules for people who missed last time.
Notes:
We finally completed the cycle construction. It’s a doozy. I might eventually
try to condense everything we covered into a series of posts with Neil’s help.
While the individual steps are “easy” to understand once you have the
requisite background, it leans heavily on quite a few tools/results and
requires you to keep them in mind all along the way. This makes it hard to
keep a roadmap in your head as you go. To make matters worse, much of it feels
unmotivated or at least unobvious without working through examples first. (We
spent a lot of time plugging through examples to connect sequences, primitive
sequences, primitive cycles, and cycles; establishing their connections to
bivariate generating functions; and moving between “unconstrained” integer
summation to bivariate Möbius inversion.)
Coffee roast taste-off!
Amy’s roast won by default. Graham’s lightest roast wouldn’t pass thorugh
my grinder without jamming (at a ristretto-fine grind) and the darker one
didn’t quite extract fully (it was around 16% extraction yield). This one
did a bit better under a slighly longer pull (1:1.5, for a “long
ristretto”). Could do well under a more traditional pull.
To be continued?
Thrill Digger
Reviewed the rules for people who missed last time, along with some specific
board state examples.
New competition class proposals:
Function approximation to estimate multinomial distribution of all
gems/bombs over all cells (not just counting the probability of there
being a rupoor/bomb). This is difficult to do efficiently by direct
enumeration. Without such a direct evaluation function, I expect we’ll
grade this by sampling random board positions. You can maximize
evaluations per board by applying random masks to cells, though these may
or may not be realistic positions in “well-played” games. On the other
hand, boards are very cheap to generate and the masking technique
introduces risk of biasing evaluations toward certain boards. We’ll need
to carefully critique the scoring criterion for this one.
Rupee/rate maximization under non-uniform (biased) boards. The idea here
is to implement various janky board generation techniques (which might
plausibly be used by the real game) and see which agents excel where. We
could even use random algorithms to induce dynamic bias. This is extra fun
because it encourages online learning—the other modes are likely best
solved done with offline training and static inference.