Playing darts with probability

We were asked to do some exercises with arrays in one of my programming courses and one of the things I wanted to do was create a method (function) to generate a random array.

Some of the exercises involved testing to see if any of the numbers in an array are negative. I could have just created a method to generate a random amount of equally positive and negative numbers. So for example it could have picked random numbers between -10 and 10.
rnum = rand.nextInt(21) - 10; //range of -10 thru 10

But that would have been kind of boring. If some of the exercises involve testing for negative numbers, then I would not want it to be the case that negative numbers occur very frequently. With equal positive and negative numbers, the probability is 50% which seems too high because basically you’re pretty much guaranteed to always have a negative number.

So, I thought about lowering the probability. One way to kind of cheat would be to just clip the range of negative numbers. For example generate random numbers between -5 and 10. That cuts down the probability of negative numbers to 33%.
rnum = rand.nextInt(16) - 10; //range of -5 thru 10. sloppy.

But I did not like this idea. So then I started to think: What is the best way to assign a weight of my choosing to randomly switch the sign within the complete range of any randomly generated number from positive to negative?

This is more clean because first of all I only need to generate positive numbers, and any potential random number that is generated could have the possibility of being negative. Furthermore, by using a weighted random generator, I would be able adjust the frequency with which negative numbers occur.

How to do this?

This is actually really fun to think about. The way I thought of the problem is this: For any particular weight that I want to use, how do I create something that randomly generates a response that can be used to assign a random attribute – in this case negativity – to some other thing?

In other words, let’s say that I choose 20% as my desired weight. How do I do something such that doing it will result in one possibility 20% of the time, and some other possibility the other 80% of the time? I need to generate some kind of thing which will always follow these odds and is able to be tested so that I can use it to assign negativity to a number.

The answer is actually really simple: I just pick a random number in a range which corresponds to the entire range of possibilities, that is 100%. The most logical thing is just a range of numbers which correspond to the complete set of probabilities.

So if I take the range of numbers from 1 – 100 and I randomly select numbers from it, I know that 20% of the time the number will be in the range 1-20 and 80% of the time it will be in the range of 21 – 100 (I think I got this right).

So all I have to do is select a random number in the range 1 – 100 and test: If its below 21 then I say “make the number negative”. Otherwise I leave it alone.

To change the weight I just change the comparison test to another value. For 15% I would test for 15 or below. Etc.
wrand = rand.nextInt(100) + 1; // use for weight
if (wrand <= weight) rnum *= -1; //weight can be set to any value

To give you an idea, here are some random arrays I generated. They consist of 10 elements (numbers).

In these first I have the weight set to 50%. 50% of the numbers should be negative:
[4, 9, -6, 6, -7, -5, 9, -5, 4, -3] (5 negative numbers)
[5, -2, -3, -5, 7, 1, -2, 3, -6, 8] (5 negative numbers)
[-10, 10, -1, -5, -3, 7, 6, 3, -4, -10] (6 negative numbers)

You can see its following the probability weight very closely.
Now I switch the weight to 20%:
[-1, 10, -8, 7, 5, 6, 1, -5, 8, 4] (3 neg.)
[5, 4, -10, 5, 10, -4, 10, -9, 7, 10] (3 neg.)
[3, 1, 10, -2, 10, 3, 7, 5, 1, 3] (1 neg.)

-----

In this case its pretty straightforward. But then I started thinking about doing something more complex. What if I had multiple things each of which has its own weight. For example what if I was dealing with the letters of the alphabet and I wanted to use the rate of frequency of each letter to generate random pseudo-words which follow the actual probabilities of letters in English?

If you look at the list there you will see that the probabilities are given to a level of precision of thousandths of a percent. One thousandth of a percent is one part in 100,000. The frequency rates for all the letters must add up to 100%, or 100,000/100,000. Thus if I were to write an algorithm to do this I would need to select a random number in the range of 1 - 100,000. Each letter's probability would correspond to a sub-range of numbers. I would then have to test each random number against the ranges of letters.

To make it more efficient I would check in order of decreasing frequency starting with the most common letter.

This would of course create only crude pseudo-words because there are a lot of other probabilities that occur with letters. For example some letters occur more frequently as the first letter of a word. Obviously some letters occur more frequently after each other. Etc. Its no doubt very complex and I wonder about people who are involved with cryptographic analysis and all the probabilities they account for with regard to the occurrences of letters in words, and words relative to each other. It must get mind-bogglingly complex.

Anyhow, I was reading some stuff and found an interesting page about what is called Rejection Sampling. In it they use the example of throwing darts at a dart board overlaid with a probability curve which I thought was kind of a neat way to visualize it.

Another possible application of weighted randomness I thought of is a crooked card game. That is a card game that essentially cheats. Based on who the cards are being dealt to, the game could skew the probabilities of cards a player gets. This also gets interesting. Because in cards you have a limited set of items to choose from (a card deck). You would have to be able to weight the random selection of an element in a finite set to favor some elements of the set (i.e. low-value cards and cards different than what the player already has) and disfavor others (high-value cards and cards which the player doesn't already have). This actually seems like it would be really fun to try although I'm not going to do it now because I have homework :-) But think about it: You could try to tweak the amount of cheating to a level that is just below being detectable. Then you could run experiments on people. Hehe. LOL.

Another thing this makes me think about: It goes beyond a card game and could be part of any potential game. For example I was thinking of something like SimCity. You could use random weightedness for a lot of things to create simulations of things. In a way you could be like a god and tweak your own world with whatever probabilities you would like. Does that seem fun? LOL Ok, I'm a geek... LOL

It really does make me wonder though about other things. To what extent is randomness a part of complex modeling systems? For examples there are attempts to model the universe from the moment of the big bang. The distribution of matter in the universe is not uniform, but its not completely random either. This is interesting.

If you thought about it logically for a minute, it almost seems odd that the universe isn't perfectly uniform. Think about it: If you start off with the inflaton and then compute from there, why wouldn't everything be perfect? Why would there be any randomness? It seems odd because you could ask "Where does that randomness come from?" "Was the inflaton itself somehow imperfect?"

References: stackoverflow.com: Generate A Weighted Random Number


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *