Random selection in a circle - Maths Problem Revisited

[THobson]

In my post on this subject on another thread
http://www.ofpec.com/yabbse/index.php?board=8;action=display;threadid=25189
I suggested that one way to select random points within a rectangle centred on (X,Y) was to use:
_Xcoord = X - _Xrange + 2*random _Xrange
_Ycoord = Y - _Yrange + 2*random _Yrange

and for a circle I suggested:
_angle = random 360
_dist = random _radius
_Xcoord = X + _dist*sin(angle)
_Ycoord = Y + _dist*cos(angle)

I have been reflecting on this and the results of those reflections are:
(In all that follows I assume OFP has a good random number generator)

In the above formulae for a rectangle the probability of any one small part of the rectangle being selected is the same as for any other similar sized part of the rectangle.  In other words the probability of selection is spread evenly across the rectangle.

For the circle the probability is not evenly spread, it is concentrated in the centre of the circle.  This is fine if you are simulating the inaccuracy of an artillery shell say, but sometimes this may not be what you want.  (If you are not sure why the probabilities are concentrated in the centre then please read the footnote below.)

If you want to select a random point in a circle and you would like the probability of selection to be spread evenly across the circle then the way to do this is:

_angle = random 360
_dist = _radius *(random 1)^0.5
_Xcoord = X + _dist*sin(angle)
_Ycoord = Y + _dist*cos(angle)

This is approximate, but is good enough.

Footnote:  If _dist is selected at random why do the probabilities concentrate in the centre of a circle?

Imagine a ring of inner radius D and outer radius D+1.  The probability of a random point being selected that lies on the ring is independent of D (in fact it is 1/_radius).
But the area of that ring = Pi*(D+1)^2 - Pi*D^2
                                      = Pi*(2*D + 1)
So although the probability of selecting a point on the ring is independent of D the area over which these points are to be spread increases as D increases.  So that close to the centre of the circle the points are selected more densely than they are further from the centre.

Just a thought.

[Fragorl]

THobson .... nice ;D

[THobson]

Thanks.

[Mikero]

In short, the probability of selecting any position anywhere in the circle is equal, but, the resolution of those values converge the closer to the centre that you get. Your ^0.5 is biasing the value to give a bigger chance of a larger number that wont resolve to a value equal to any other. To 'improve' it, I would have used a tan() [eg] to proportionaly weight the result towards big values rather than the fixed constant. But, the principle is sound.

as far as randomness itself is concerned they _generally_ bias towards the lower values of the range because the simplest method of satisfying a request for a number between say 0 and 6 is to

return real_random mod 7

if the real_random can only produce (say) values between 0 and 8, the the values '0' and '1' will appear more frequently. Ie the final residue is the bias and decreases in importance the huger the scale between real_random and the range wanted. There are ways around this, but it's seldom implemented.

[THobson]

In short, the probability of selecting any position anywhere in the circle is equal, but, the resolution of those values converge the closer to the centre

Without the ^0.5 the probability of picking a particular point in the circle decreases the further that point is from the centre of the circle.  With the ^0.5 the probabilities become equal for any distance from the centre (but see my comment below about close enough).

I would have used a tan() [eg] to proportionaly weight the result towards big values rather than the fixed constant

I am not sure of the theoretic justification for using a tan.  I did the algebra on the circle problem and got it down to two terms that I needed to integrate, one of those integrals resulted in the ^0.5 and the other was so small that is could be discarded.  Hence my comment that it was approximate but good enough.  The fixed constant (_radius) defines the maximum limit of the circle within which the random point is to be selected.

Interesting point on the bias of random number generators.  A couple of comments.  It has been said before, but OFP's random number generator seems to be 'sticky' in that consecutive numbers seem unusually similar.  I have done no statistics on it to test this, it is just an impression.  The example you give would explain a bias to the low end, but I thought most random number generators use a large number of digits so the bias would be less noticable.

[Mikero]

I thought most random number generators use a large number of digits so the bias would be less noticable.

Perversely, not so. It's almost negligble for most applications *except* statistical analysis (for want of a better term). Ie, the more frequently you make use of random numbers for the same evaluation the higher, statistically, you'll get the bias. Picking a card from a pack eg will 'favor' the first 'X' many cards when you 'pick' often enough.

Perversely, the larger range you use, ie a range that comes close to the range of the 'real random', the higher the favoritism. the higher the 'chance' of picking up the unbalanced band. To explain: 0..9 in a spread of 0..15 (real number) means you have an equal chance of hitting the 'biased' band. Values 10..15.

0..3 in the same spread reduces the chance five fold.

0..9 squillion a spread of 0..15 squillion is the same thing. It means, 50% of the time you will NEVER be able to pick the higher values of the range. That should alarm you.

The half answer is to use small ranges relative to the huge real number (to reduce the chance)

The 'correct' method for crapping on this is to reject the 'real random' if it's value is in that upper region.

do a_num = random() while a_num > A_VAL*SOMEBIG_CONSTANT

mynum = a_num mod A_VAL

sophisticated random() functions do this for you. I dont know that answer for ofp because it's highly esoteric and may have escaped their attention.

Bah, thank you for giving me a headache again Thob.

[THobson]

Bah, thank you for giving me a headache again Thob.

Don't mention it.  Anytime  ;D

The half answer is to use small ranges relative to the huge real number (to reduce the chance)

That is what I meant when I said:

I thought most random number generators use a large number of digits so the bias would be less noticable.

My subjective experience of the ofp random number generator is that it might struggle to pass a statistical test for randomness.

I said above that the use of ^0.5 is approximate but close enough.  I now realise that I got that impression by going the long way round to solve the problem.  Taking a more direct route to the solution that by passes the integration stage comes to the result that using the ^0.5 is correct, it is not an approximation

[macguba]

I can't speak for the random number generator but what I can say is that the randomness associated with using markers for a variety of player start positions is not random.     It is very "sticky":  if you start at one of 8 start positions on attempt x, on attempt x+1 you have about a 40% chance (guesstimate) of being at the same place, instead of a 12.5% chance.      

[Mikero]

Getting out of my depth here Mac because I don't know scripting functions all that well but this problem smacks of a bad seed value, ie same or very similar seed used each time every time you start the mission.

Surprisingly, a standard random number generator will produce the same series of values each time every time from a given seed. The numbers appear random because they don't appear to bear any apparrent relationship to each other, but their sequence is not.

Isn't there a randomize() verb available? I never paid much attention to it.

Edit: sorry, I should have said same band of values.

[THobson]

Isn't there a randomize() verb available?

One of the first things I looked for, and no there isn't, well not that I could find  

The seed is stored in the mission.sqm file, so I suspect (I have not investigated it) that this is reset every time the mission is saved.  I have no idea what the engine might do with that seed when it runs the pbo mission.  An internal randimize() would be nice.  It might even happen since as you say, with the same seed a random number generator will generate exactly the sequence of numbers, and that clearly isn't happening.

I interpreted mac's comment differently, based on my subjective experience if random n gives a low number, the next random number is also likely to be low.  Similarly for high values, and mid range values.  I have not investigated it, it is just an impression.  If that impression is correct it tells me it is something about the generator itself not the seed.

But - you must have heard the story about the lady on the bed with a mathematician and an engineer at the door?  Well this is just such a situation. The real life effect of a crap random number generator is that you should be able to predict what will happen in the mission.  I don't think that is the case so for me the generator is good enough (despite normally having more in common with mathematicians than engineers ;D)

[macguba]

Thobson, why don't you remind us of that story?    ;D

I agree that the random functions are good enough to do their job:  you can't useful predict what's going to happen in the mission.

[THobson]

Funny you should ask: ;D

A desirable young lady is on a bed at the end of a room ready to entertain all comers.  At the door are a mathematician and an engineer.  The lady is of the liberated kind not averse to entertained two gentlemen at once - so it is not a competition.  The physics of the room is unusual.  The first step anyone takes into the room will put them half way to the woman, as will the next step.  In fact every step they take will result in them halving the distance to the woman.

Once this is explained to the two individuals the mathematician shrugs his shoulders and begins to walk away just as he sees the engineer begin sprinting into the room.

"What are you doing?" says the mathematician "You must know that the sum of the geometric progression (1/2)^n converges.  You will need to take an infinite number of steps before you get there"

"Yes, I know that" says the engineer "but it won't take me long to get close enough!"

[Mikero]

here's a little code snippet for General Macguba. I'm only supplying to him because he's been unusually nice to people this week.

rnd=random() mod 3

while (rnd--) random()

rnd=random()

this 'breaks' the banding effect most generators exhibit.

[THobson]

If somebody doesn't laugh soon I will delete the joke and solve the thread.

Okay it might be a bit mathematical nerdy, but the point is: close enough is often good enough let's not get hung up over mathematical precision.

Mikro
EDIT:  I am stuck on the second line until I realsied you were relying on a Boolean also being a number.  Then I got it.

[Baddo]

Funny you should ask: ;D

A desirable young lady is on a bed at the end of a room ready to entertain all comers.  At the door are a mathematician and an engineer.  The lady is of the liberated kind not averse to entertained two gentlemen at once - so it is not a competition.  The physics of the room is unusual.  The first step anyone takes into the room will put them half way to the woman, as will the next step.  In fact every step they take will result in them halving the distance to the woman.

Once this is explained to the two individuals the mathematician shrugs his shoulders and begins to walk away just as he sees the engineer begin sprinting into the room.

"What are you doing?" says the mathematician "You must know that the sum of the geometric progression (1/2)^n converges.  You will need to take an infinite number of steps before you get there"

"Yes, I know that" says the engineer "but it won't take me long to get close enough!"

;D ;D ;D ;D ;D ;D ;D ;D ;D ;D

[macguba]

[THobson]

 ;D
Okay that's enough.  It wasn't that funny.

[Triggerhappy]

LOLOMFGROFLMFGDAOLOL

 

[Mr.Peanut]

In my experience the random number generator is not sticky. Generate a large number, say 10000, of random numbers using random 1.  Count the number that fall in the range < 0.5 and the number that fall into range >=0.5

The two counts should be about equal each time you try this.  Now divide the range from 0-1 into 10 bins instead of 2.

With 10 bins I do not see a discernable pattern, no matter how many times I repeat the experiment.  Although the distribution is never perfectly uniform (i.e. 1000 counts for each bin), the distribution seems to have no repeatable pattern.  This is not a rigourous test, but is reassuring.  

I wrote a random number shuffler that is the first improvement on a linear congruent random number generator, and the results are not significantly different.  

These tests were run from within the mission editor.

I will rerun the test tonight with 1000000 random numbers and see what happens.  

[THobson]

Peanut.  I think we might be attributing different meanings to the word 'sticky'.  Your test - which is an excellent one, is checking for randomness of distribution.  By sticky I am really referring to a correlation between consecutive random numbers.  So that if one number is low the likelihood is that the next one will be low also.  That is what I mean by sticky.

I am sure there are many official statistical tests that could be done to check this, but I don't know them.  My gut feel is that if you test a lot of random numbers and don't put the numbers themselves into buckets, instead subtract each number from the one before and put that result into the correct bucket there should be an even spread across all buckets if it is not sticky, but a concentration of numbers close to 0 if the generator is sticky.  The range of answers should go from -1 to +1.

[Mr.Peanut]

Looks like I might have to eat my words...distribution is not great. roughly 5% error....

Trial 1 - 101101,98593,98329,98495,100564,102888,101871,98091,98525,101543

THobson... If you are really concerned about correlation between sequential random numbers, I have written a function that corrects for this to some degree.  Perhaps I should submit it.

Function randomPlus submitted.

[THobson]

I am not concerned, it is just that this is a phenomena I think I have noticed - so if someone was to do some tests I would be very interested in the results

[Mr.Peanut]

Well, try my new function sometime...

[THobson]

I may well do that.  But I would like to investigate the problem, if it is a problem, first.

Well I think this thread has run its course.  It was intended simply to be a guide to selecting  points randomly and evenly within a circle.  It went on to deal with the randomness of random numbers and it is now time to solve it.

Thanks everyone.