Is it possible to evenly select from 6 options using an input of 8 values?

Question

If I have a list of 6 options to choose from and a selector that has 8 possible values, can that selector be reduced to evenly select from the 6 options?

I'm using 3 bits, so a value between 0 and 8 exclusive and I need to select from 6 options. My understanding is that I have more information than I need, but I don't know how to construct a map to the lower information state.

My only idea so far is to use the selector value to seed a pseudo-random number, but is there enough information in the seed to assume an even distribution?

Answer 1

Assuming your selector returns a uniform distribution over $8$ values, you can't select one of $6$ uniformly from one result. What you can do is accept values $1$ to $6$ from the selector, reject $7$ and $8$ and ask the selector again. You have $\frac 34$ chance of a selection on each try, so you won't have to try too many times. You might go on forever getting $7$s and $8$s, but the probability converges to zero.

Answer 2

If I understood you right, you want to generate a random uniform variable $Y$ taking 6 values using a variable $X$ that takes 8 values with uniform probability.

One way (and arguably the simpler one) is using a discard-retry method, as in Ross Millikan's answer. True, this way one is throwing away some information.

A slightly more efficient way is to use some extension of the source.

For example, from $8$ uniform bits (256 equally possible values) we can pick the first $243 =3^5$ to code $5$ uniform ternary simbols, and retry (same as the other answer) if we are outside this range. The expected amount of tries is $R=256/243=1.053$. We need $5$ bits more to code $5$ uniform symbols of $Y$ (six values). Hence we need (in average) $(R\times 8 +5)/3$ inputs to generate $5$ values of the output. The rate is $0.8952$, quite near $\log(6)/log(8)=0.8616$.