Select an element without uniform distribution with a uniform random without iterations

Question

I have N elements (numbered from 0 to N-1) and I must choose one but without the same probability. For example, I need that the 0 must happen 50% of times, 1 with a 25%, 2 with a 12.5%, etc.

I don't care what happen with the remain probability, it can be assigned to the first element. For example with N=3, I have 0 => 50%+12.5%, 1 => 25%, 2 => 12.5%.

In the context in which I'm doing it I can only generate uniform distribution numbers (the Java Random class). So I need a way to give more probability to low elements. I know that, for example, I can do it iteratively with something like:

i = 0
while (NOT find AND i < N){
  r = Random()
  if (r < 0.5) {
    find = TRUE
    x = i
  } else {
    i = i+1
  }
}
if(NOT find) {
  x = 0
}

Or also with an array filled with the elements in proportions to its probability.

What I want to know is if there is a formula that given the maximun and a random number in the range that is needed can tell me the element selected directly without iterations.

Note: This is more a question by curiosity than utility because in my context isn't needed an extreme optimization of this behaviour so it is ok to do with iteration or wasting memory.

Edit, a little more explanation:

• I want the result to be discrete (although I can convert continuous to discrete with a simple round function).
• With "directly without iterations" main it can use common functions and formulas, etc. but can't do things repeatable. It's ok to do (((N*2/123)%10)/(12-N^2))^-2 then sum N² if N>2 or N³ if N<2 but not generateRandom if > N choose 1 else N=N+1 repeat again.

Answer 1

Pick a random number between 0 and 1, and calculate $\lfloor-\log_2(x)\rfloor$

Answer 2

Could also use a monte carlo approach. Pick two random numbers ($x$ and $y$) and define a function ($f$) that gives you the pdf. If $f(x)\geq y$ then accept the point, otherwise pick again. Then it's just a matter of finding the right scaling for the function you use (I'm not familiar with the Java Random class).