Meetup summary

2025-06-13 - General Q&A 1

Recommended reading:

None! (But maybe skim chapter I if you want to come with questions about unlabeled combinatorial classes.)

Agenda:

Happy Friday the 13th! This is an auspicious occasion because we first met on such a day. Doubly so because the 13th of the month is most likely¹ to fall on a Friday due to an unfortunate wrinkle in the Gregorian calendar.²³⁴

I don’t have any explicit topics planned for this one. Instead, I encourage people to show up with any questions/problems they have and we can work them out together. The sky’s the limit here, but based on the audience, you’ll probably have better luck with math-/CS-related questions.

If people are interested, we can visit some of the worked examples we skipped over previously from chapter I (Stirling S2 numbers formulated as a regular language counting problem, necklaces, etc.) This will also be a good time to drill into more detail about the Thrill Digger Challenge.

Notes:

• Didn’t touch on any of the queued AC topics.
• We only went into importance sampling (but, as usual, this managed to fill the whole time slot):
  • Whirlwind introduction to probability:
    • Axioms of probability
    • Basics of discrete and continuous RVs and probability distributions
    • Expectation and variance
    • Linearity of expectation
    • Bias and MSE definitions, plus bias/variance trade-off
    • Unbiased and consistent estimators (definitions/examples).
    • Derivation of sample mean as an unbiased and consistent estimator (in the interest of importance sampling).
    • Lots of other tangents I didn’t capture.
  • Rudimentary rejection sampling (e.g., how to simulate an $n$-sided die given just a bitwise binary source, with varying degrees of efficiency).
  • Monte Carlo integration: motivation vis-à-vis naive Riemann numerical integration and related techniques.
  • 2D rejection sampling: sample from an arbitrary black-box distribution $p(x)$ using a proposal distribution $q(x)$. (Sample-inefficient in general.)
  • Importance sampling: estimate $E_{x \sim p}[f(x)] = E_{x \sim q}\left[ [f(x) \frac{p(x)}{q(x)}\right]$ for any “covering distribution” $q$ that you can efficiently sample from.
  • Application: Monte Carlo integration for ray tracing/scene rendering. Use inverse-transform sampling to produce the BRDF input, then use importance sampling to compute the overall luminance integral.
  • To-do for next time:
    • Derive the self-normalizing importance sampling denominator to work efficieintly with unnormalized proposal distributions. (This is only an approximation/limiting case.)
    • Derive effective sample size (ESS, two variants) and variance of importance sampling estimates. (This includes a discussion of heavy-tailed target distributions, light-tailed proposal distributions, infinite variance, and other pathologies.)

Footnotes

1. Extra credit to anybody who can solve this with pen and paper using OGFs. ↩

2. $497 \equiv 0 \pmod 7$, so it cycles every 400 years without striking every weekday/calendar date evenly. ↩

3. Further explanation: leap years are years that are divisble by $4$, unless the year is also divisible by $100$. In that case, the year must also be divisible by $400$ to be a leap year (otherwise, it’s an ordinary year with no extra day inserted). The net effect is that we omit $3$ leap days every $400$ years to counteract the discrepancy between solar years and solar days on earth. In other words, we “should” have a rotation of $100$ days per $400$-year period if not for this correction. Including the correction means that we actually only insert $97$ leap days over the $400$ year span. Finally each normal year causes the weekday residue to shift by $1 \pmod 7$. Accounting for leap years (days), we end up shifting by $400 \cdot 1 + 97 \pmod 7 = 497 \pmod 7 = 0 \pmod 7$. ↩

4. One more fun fact: I was mildly surprised by this at first because $7$— the length of a Gregorian calendar week—being prime implies that it is necessarily coprime to any residue in its quotient class. This would have guaranteed that we actually had a $400 \cdot 7$-year cycle before repeating weekday/date patterns and would necessarily distribute weekdays evenly per calendar date. Of course, that would only work if the effective residue per $400$-year cycle was not divisible by $7$ (a $\frac{6}{7}$ probability assuming a naive uniform random distribution). Turns out we’re in that “lucky” $\frac{1}{7}$. ↩