How to generate $X$ uniform on $\{0,...9\}$ from $Y$ uniform on $\{0,...,7\}$

Question

Assume I have a random integer in the range form 0 to 7 and I want to generate a random integer from 0 to 9, how would I go about doing so?

I though about doing the following: First I choose a random number from 0 to 7. Then I reduce this number mod 2. Then I can choose one of the sets $\{0,...4\}$ and $\{5,...,9\}$, so the problem is reduced to choosing a random number from 0 to 4. Now one can choose random numbers from 0 to 7 until one lies between 0 an 4.

Unfortunately the above method does not necessarily terminate(although it terminates with prbability 1), so I was wondering about a method that guarantees me to terminate after a finite numer of steps.

Also I was wondering more generally if there is a strategy to transform a random variable that is equally distributed between $0$ and $n$ into a random variable that is equally distributed between $0$ and $m$. I think one can extend the above strategy to reduce the problem to find a random variable equally distributed between $0$ and $(m+1)/gcd(n+1,m+1)-1$ but in generally(for example if $n+1$ and $m+1$ are both prime) this is not really helpfull.

Answer 1

When $|Y|$ has prime factors that aren't prime factors of $|X|$ you can't transform a uniform distribution on $X$ to a uniform distribution of $Y$.

It's a simple fact that many people doesn't realise.

The simplest case, that I have succesfully used to convince people (unfortunately not all) is: Imagine that you have to decide if your new car should be red, green or blue and all you have is a coin - no matter what strategy (that gives an equal distribution) you use for mapping the result of a series of coin flips there will always be a chance that you flip a sequence that doesn't map to any of the choices.

Answer 2

Generating a random variable uniformly distributed on $\mathfrak X=\{0,1,\ldots,9\}$ from a random variable uniformly distributed on $\mathfrak Y=\{0,1,\ldots,7\}$ is obviously impossible since the latter yields $|\mathfrak Y|=8$ cases while one needs $|\mathfrak X|=10$ cases.

Thus, let us assume that the question is actually asking whether there exists some integer $n$ such that one can generate a random variable uniformly distributed on $\mathfrak X$ from an i.i.d. sample of size $n$ uniform on $\mathfrak Y$. Such a sample is equivalent to a single random variable uniformly distributed on $\mathfrak Y^n$, whose size is $|\mathfrak Y^n|=8^n$, hence one is asking for a partition of a set of size $8^n$ into $10$ subsets of equal sizes. But $8^n$ is not a multiple of $10$ hence such a partition does not exist.

---

Edit: To generate several i.i.d. random variables uniformly distributed on $\mathfrak X$ from a random, non bounded, number of i.i.d. random variables uniformly distributed on $\mathfrak Y$, one can exploit the fact that $8^{10}=1073741824$ is only slightly larger than $10^9$, to devise a somewhat efficient rejection sampling algorithm.

Thus, one first simulate a sample $(Y_1,Y_2,\ldots,Y_{10})$ of size $10$ uniform on $\mathfrak Y$, then one encodes it as a single integer $Z=\sum\limits_{k=1}^{10}8^{k-1}Y_k$, uniformly distributed on $\{0,1,\ldots,8^{10}-1\}$.

• If $Z\leqslant10^9-1$, the $9$ digits of $Z$ yield a sample of size $9$ uniformly distributed on $\mathfrak X$.
• If $10^9\leqslant Z\leqslant8^{10}-1$, one forgets $Z$ and one restarts with a new sample of size $10$ uniformly distributed on $\mathfrak Y$.

This produces $9$ values uniformly distributed on $\mathfrak X$ from a sample of $10$ values uniformly distributed on $\mathfrak Y$, with probability of success $p=10^9/8^{10}$, thus, if one repeats the procedure, each random variable uniformly distributed on $\mathfrak X$ uses $10/(9p)$ random variables uniformly distributed on $\mathfrak Y$, for a mean efficiency of $9p/10\approx83.8\%$. Choosing longer strings of $\mathfrak Y$-samples, one can attain every efficiency smaller than the theoretical maximum efficiency $9/10=90\%$.