What would happen if you did rejection sampling one bit at a time? Find the largest multiple of your limit which is less than W. We want to find a random numbe

What would happen if you did rejection sampling one bit at a time? Find the largest multiple of your limit which is less than W. We want to find a random number less than this multiple, because then we can just divide down to get an unbiased result. Maybe this is already implied in how these algorithms are set up, not sure. Generate a candidate random number. If it is smaller than the multiplied limit, you are done. If not, double it, and add a random bit. Repeat until success. To supply the random bits, generate a random number, and use it up one bit at a time. If you need more, generate another random number. I suppose this doesn't work, because the second-most-significant bit of a rejected candidate isn't unbiased. If the multiplied limit is 3/4 of W, then we only reject candidates where the top two bits are both 1! Can you rescue this by discarding more than one bit when you reject? Probably not. Think about the case where the multiplied limit is W-1. The only candidate you would reject is all 1s. You'd have to discard all the bits for the next candidate to be unbiased. Oh well.