Saturday, February 26, 2011

math problem

A guy I used to work with is married to a math teacher. Once in a while I would send him a math problem I'd thought of that might be interesting to high school math students.

I noticed he isn't on my facebook friends any more. I guess he deleted his account or just deleted me as a fb friend. oh well he'd been among my first 20 or so friends back in like 2007. If he deleted me then no biggie.

I checked I have 141 fb friends at this moment. Of these I could delete about 30 today and it wouldn't make any difference in my facebook experience. People I don't know, people I don't really like, people I don't care about. But if you're on my fb and you're reading this then you're on my "good" list lol.

Anyway back to the math problem I was going to send. Suppose you have a hardware random number generator call it R. It has the property that it will return a uniformly distributed random number in the range [0, 1).

Suppose you are working on an application of some type such as a game and the design requires a random number in the range of 0.10 to 0.85. How do you get this using the generator R?

As a further constraint let's say that you are in a resource constrained environment such as on a battery operated mobile phone. So for performance and battery life you may only invoke R once for this. Thus the scheme of invoking R, and keep repeating until the value returned by R is between 0.10 - 0.85 is not acceptable. It is unacceptable because 25% of the time you would have to invoke R more than once.

It's not a real difficult problem in my opinion. I'll let it sit for a bit and post a solution I came up with in the comments.


Rob said...

Here's a solution:

1. invoke R and store it in the value k.

2. multiply k by 0.75. This will give you a uniform distribution in the range 0 - 0.75.

3. add 0.10 to the result from step 2. This will give you a uniform distribution in the range 0.10 - 0.85. done

The interesting part was step 2. The observation that a uniform random distribution can be scaled to a larger or smaller space by multiplying it by a constant and it is still random and uniform.

Anonymous said...

That's the same approach I would have taken. That said, you're scaling down, so you're technically going to end up doing some rounding on the least significant digit. You'll lose data in the same way you'd lose pixels if you scaled a non lossy image (gif, png) from a width of 1000px to a width of 750px.

Think of it as your random number generator giving you integers from 0-9, or k. Using n = trunc(k*0.75) your same logic would create a mapping like:
k -> n
0 -> 0
1 -> 0
2 -> 1
3 -> 2
4 -> 3
5 -> 3
6 -> 4
7 -> 5
8 -> 6
9 -> 6

Two zeroes, two threes, two sixes. As you can see, not a uniform distribution. I only point this out as the fewer significant digits your r() function produces, the less uniform your numbers will be. I assume you're probably getting a value to seven or eight decimal places, multiply by 3/4 and then round (or trunc as I did above), in which case it probably won't have much impact on what you're trying to do.

One could also argue that this is moot as a computer can never truly achieve randomness.

Rob said...

Thanks for the feedback. Some interesting points there Anon.

I will point you to the following regarding the availability of true randomness in computers - a separate hardware device. In my OP I did allow a separate source of true random numbers.

If you play cards on a major poker site; these sites use these hardware RNGs to shuffle the deck for each hand dealt.

Anonymous said...

Right you are - I missed the word "hardware" at the start of your math problem. The point I was trying to make at the end of my post is echoed in the PDF you linked:

"A PRNG by itself will be insecure without a TRNG for seeding. Seeding requires a source of
true randomness, since it is impossible to create
true randomness from within a deterministic system."

Basically, they're useless without some sort of outside input. The fact that there are machines looking at their own hardware on a quantum level for a source of entropy is pretty damn cool. I'm guessing this sort of hardware isn't implemented in a mobile phone though. :)