Uniform discrete distribution - time to draw

Question

I have a question about the basic definition of discrete normal distribution.

Let's assume I have a machine that draws a number ranging from 1 to 3 from a uniform discrete distribution (the probability to get 1, 2 and 3 is equal and equals to 1/3).

If I want to use that machine to create another machine that yields from the set {1,2} in a uniform manner, can I use the first machine in the following way:

draw a number -> if the number is 3, draw again. if not, return the number.

on one hand, it does seem like the new machine draws uniformly from {1,2}, as the two numbers have an equal probability of being drawn.

on the other hand, it's not a classic uniform distribution, as it might take a long time to draw the number (if the numbers being drawn is 3 in many trials).

So, can I say my new machine draws uniformly from the set {1,2}? thank you!

Answer 1

Yes you can. There is nothing in the definition of the uniform distribution that says anything about how it might be implemented or arrived at.

Answer 2

Your new machine generates uniform distribution. With small probability it may require many steps of your inner machine to do it, but it doesn't matter. Important part is that there is exactly zero probability of your new machine to not even terminate.

If you want to create a new machine that makes at most $n$ uses of old machine - it's not possible. Probability of new machine giving $1$ will then be of form $\frac{m}{3^n}$ where $m$ is integer, and $\frac{1}{2}$ can't be represented in such form.