Thanks for this pointer -- I had read a Knuth paper ages ago that talked about this, but I couldn't remember the term of find the paper again, and this led me directly to [1] which led me back to [2]
[2] Knuth, Donald E. and Andrew Chi-Chih Yao. “The complexity of nonuniform random number generation”, in Algorithms and Complexity: New Directions and Recent Results, 1976.
