1
$\begingroup$

Given function rand7 returns random integer in interval [0, 6]. Your task is to implement function rand5 which should return random integer in interval [0, 4] using function rand7.

This is a question from my book. So, this is how I solved it (the algorithm is written in C):

int rand5(void){
  return (int)(rand7() * 4. / 6. + .5);
}

Basically, I just scaled the interval to [0, 4]. The + .5 part is to properly round to nearest integer (not just to truncate decimals). However, this is not correct solution.

Solution in my book is very weird to me. This is how they did it:

int rand5(void){
  int a;
  while((a = rand7()) > 4);
  return a;
}

The book says that the algorithm I came up with works only when interval is significantly large (so the probability will not change a lot). For smaller intervals (like this one) there is no other solution.

Well, it sounds pretty weird that there is no other solution. What is the time complexity of this algorithm? For my algorithm, time complexity is O(r) where r is time complexity of rand7. But what is the complexity of their algorithm?

The complexity should be O(r * n) where n is, according to the definition of the time complexity, the largest possible number of loop iterations. But what is the largest possible number of iterations? We know nothing about function rand7 and the way it is implemented, so the largest possible number of iterations is infinity. So, the complexity of this algorithm is O(infinity) which doesn't make any sense.

Of course, if rand7 if properly implemented, it will for sure return at lest one time number in interval [0, 4]. But, theoretically, it can return any number of consecutive numbers which belong in interval [5, 6]. Is then complexity indeterminate?

Also, how is that possible that "there is no other solution"? To generalize, is there any algorithm which can give an integer random number (with equal probability for all numbers) from interval [0, k] for given number k using only rand2 (for example), such that the algorithm should work in finite time complexity?

Edit

Ok, if I need to summarize this, the question is as title says, what is the complexity of this algorithm?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You've asked several questions in your post. This is a question and answer site - note that question is singular, not plural. What specific question can we help you with? $\endgroup$ – Ken White Jun 9 '17 at 3:25
  • $\begingroup$ Hmmm, it doesn't seem to require that the distribution of randomness is the same as the original. In your example, there will be a bias based on how round-off works. The problem is probably trying to describe the time complexity of correctly smoothing the distribution within the new range. $\endgroup$ – paddy Jun 9 '17 at 3:31
  • $\begingroup$ The amortized complexity is O(7/5). And since 7/5 is a constant, it would be considered O(1). The idea is that over a sufficient number of runs and assuming that rand7 produces a uniform distribution, it will take seven calls to rand7 to get five numbers in the range [0..4]. $\endgroup$ – Jim Mischel Jun 9 '17 at 4:24
  • 1
    $\begingroup$ Also, @JimMischel, what you describe is expected cost, not to be confused with amortized cost. Amortized cost is the guaranteed worst-case complexity over a series of operations, there is no probability involved in amortized cost. Expected cost is the average over a series of random operations, probability involved. This question might help. $\endgroup$ – ryan Jun 9 '17 at 4:40
  • 1
    $\begingroup$ The proposed solution is called rejection sampling. It has the charme of maintaining the distribution, which doing arithmetics in this or that direction often does not. $\endgroup$ – Raphael♦ Jun 9 '17 at 4:53
3
$\begingroup$

Investigating worst-case cost is rarely useful for randomized algorithms. Here, the worst case is indeed that the loop never stops -- but this event has probability zero!

Instead, perform average-case analysis. What is the probability of the loop running $k$ times?

That means it misses the interval $k-1$ times, and then hits it. Assuming that rand7 has indeed uniform distribution, the probability of the former is $\frac{2}{7}$, and of the latter $\frac{5}{7}$. The result is, assuming that separate calls of rand7 are stochastically independent, $\bigl(\frac{2}{7}\bigr)^{k-1} \cdot \frac{5}{7}$.

Now you compute the expected number of iterations using basic facts from stochastics.

The above weights are those of a geometric distribution. Looking up its properties, we learn that its expected value is $\frac{7}{5}$.

As it turns out, this is not too bad. You can also investigate the standard deviation or compute some probabilities to get a feeling for how unlikely high iteration counts are.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

Regarding complexity of rand5

Hand waving and reasonable assumptions

The procedure (it is not a function in the mathematical sense) rand7 has no arguments to depend on. Therefore, the only thing it can depend on is global state. Since rand7 is a black box (we don't know its implementation), we can only make a reasonable assumption that the complexity is a constant k7.

Therefore, since the complexity function of rand5 is T = k5 * k7, and T \in O(1).

If we know more about rand7, we can do a deeper analysis through solving a recursive cost function where the implicit state becomes an explicit parameter to the algorithm.

Strict analysis

If we are to strictly adhere to the definitions of asymptotic complexity (Big-O), a black box can possibly never terminate. If it never terminates, which is the worst case, the complexity of the procedure is undefined.

The Big-O complexity of a genuinely infinite loop is undefined.

See: https://stackoverflow.com/a/14309914/1063961 for more information.

Empirical analysis

We can not statically analyze the complexity of a black box. But we can do it via empirical analysis. For more details on how accomplish this, see the paper "Automatic Grading of Programming Exercises using Property-Based Testing".

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You said that the complexity is constant? Well, whichever constant k you chose, there may occur a situation when the complexity overflows your estimation. $\endgroup$ – iEI-oigrStiuOMp w Jun 9 '17 at 3:39
  • $\begingroup$ We can not statically analyze the complexity of a black box. That is impossible. At most, you may do it via numerical analysis. See: dl.acm.org/citation.cfm?id=2899443 for more information. If the complexity is not a constant, then it is a function of type () -> Complexity, which we can not analyze. It is a reasonable assumption that the complexity of a black box with no input parameters is constant. $\endgroup$ – Centril Jun 9 '17 at 3:47
  • $\begingroup$ It seems like rand5() could potentially suffer from infinite slowdown (though unlikely). Of course, if rand7() is a random walk, even if much larger say 2^32, it couldn't take long on a ghz machine. 5 and 6 could only be repeated at most 1.2 billion times in a single walk of 4 odd billion. Of course the odds of them all being contiguous is astronomical. $\endgroup$ – ebyrob Jun 9 '17 at 3:55
  • $\begingroup$ @ebyrob Well, in that case, the "complexity" is "infinite" (nonsense), see "The Big-O complexity of a genuinely infinite loop is undefined. " stackoverflow.com/a/14309914/1063961 $\endgroup$ – Centril Jun 9 '17 at 3:58
  • $\begingroup$ @Centril sorry, it appears "random walk" isn't commonly used as I meant it. I simply meant each possible value being visited once before repeating occurs. So if you generated numbers in a 2^32 "walk" you'd hit each number once then repeat. This is pretty typical of many RNG but I think there are other possibilities considering slow add and busy beaver problems. $\endgroup$ – ebyrob Jun 9 '17 at 4:08
1
$\begingroup$

Regarding the distribution:

you solution takes 1 output from rand7 and then maps it to [1, 5],

If it outputs 0 then you output 0
If it outputs 1 then you output 1
If it outputs 2 then you output 1
If it outputs 3 then you output 2
If it outputs 4 then you output 3
If it outputs 5 then you output 3
If it outputs 6 then you output 4

This means that you are twice as likely to get 1 or 3 than a 0, 2 or 4.

The solution is to drop the 5 and 6 output and repeat the sample until you get one that is within the output range.

In the other direction (creating a rand7() from a rand5()) you will need to combine 2 samples to create a rand25 by doing sample1*5 + sample2 and then extract out a rand21() using the same method above and dividing by 3.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.