Lotto simulation

Lotto simulation

[montgrimpulo]

Hi,

this is a placeholder of the task which I am trying to solve in Ada.
As you may know in German Lotto there are 49 numbers 1..49 
from which you have to select 6 numbers to place a bet.

First Round:
By defining a subtype valid for positive numbers from 1 .. 49,
the use of Ada.Discrete_Random, and the definition of an appropriate Generator
you may get a random number in the range of 1 .. 49.

Second Round:
Here does my problem start. Now I have a set of numbers where
one number - which was randomly selected in the first round -
is missing. How do I use the random function to select another 
random number out of the rest ?

Third to the Six's Round:
same problem.

Any ideas to answer that question ?

A workaround would be
to test in each round, if that number has already been selected.
However, the probability would not be the same as with a reduced
set as the selection would be always from the full set.

Re: Lotto simulation

[Stefan.Lucks]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2306 bytes --]

On Sun, 15 Jun 2014, montgrimpulo wrote:

> this is a placeholder of the task which I am trying to solve in Ada.
> As you may know in German Lotto there are 49 numbers 1..49
> from which you have to select 6 numbers to place a bet.
>
> First Round:
> By defining a subtype valid for positive numbers from 1 .. 49,
> the use of Ada.Discrete_Random, and the definition of an appropriate Generator
> you may get a random number in the range of 1 .. 49.

Call that number R_1.

> Second Round:
> Here does my problem start. Now I have a set of numbers where
> one number - which was randomly selected in the first round -
> is missing. How do I use the random function to select another
> random number out of the rest ?

There are a couple of different solutions.

First Solution (in pseudo-code, not in Ada):

repeat choose a random R_2 between 1 and 49 
until R_2 /= R_1.

Third round: Choose a random R_3 between 1 and 49
until R_3 /= R_1 and R_3 /= R_2.

ect.

Second Solution:

choose a random R_2 between 1 and 48
If R_2=R_1 then R_1 := 49

choose a random R_3 between 1 and 47
If R_3=R_1 then R_3 := 48
elsif R_3=R_2 then R_3 := 49

ect.

Now, for the second solution, you need random numbers from different 
intervals. In principle, you can (2a) instantiate a new generator from 
Ada.Numerics.Discrete_Random for each of the R_i. The alternative is to 
(2n) instantiate a single random generator (I've forgotten the package 
name, but it is not A.N.Discrete_Random), which just generates a Float 
F_Rand between 0 and 1. Then set R_I := Truncate(1 + F_Rand * (50-I)).

> A workaround would be
> to test in each round, if that number has already been selected.
> However, the probability would not be the same as with a reduced
> set as the selection would be always from the full set.

That sounds like my first solution. If you repeat the random choice until 
you R_i is different from all the R_(i-1), ..., R_1, the probability is 
exactly the probability you expect. (Well, assuming the random generator 
is good.)



------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
     <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
--Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--

Re: Lotto simulation

[J-P. Rosen]

Le 15/06/2014 20:54, Stefan.Lucks@uni-weimar.de a écrit :
> The alternative is to (2n) instantiate a single random generator (I've
> forgotten the package name, but it is not A.N.Discrete_Random), which
> just generates a Float F_Rand between 0 and 1. Then set R_I :=
> Truncate(1 + F_Rand * (50-I)).
This is not equivalent. I don't remember the details, but in the making
of Ada 95 there was a furious discussion between numericists about
whether it was possible to make a discrete random generator given a
floating point random generator.

After megabytes of E-mail discussion, they concluded that NO, it was not
possible, and therefore that Ada should have both.

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: Lotto simulation

[Stefan.Lucks]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1685 bytes --]

On Sun, 15 Jun 2014, J-P. Rosen wrote:

> Le 15/06/2014 20:54, Stefan.Lucks@uni-weimar.de a écrit :
>> The alternative is to (2n) instantiate a single random generator (I've
>> forgotten the package name, but it is not A.N.Discrete_Random), which
>> just generates a Float F_Rand between 0 and 1. Then set R_I :=
>> Truncate(1 + F_Rand * (50-I)).
> This is not equivalent. I don't remember the details, but in the making
> of Ada 95 there was a furious discussion between numericists about
> whether it was possible to make a discrete random generator given a
> floating point random generator.
>
> After megabytes of E-mail discussion, they concluded that NO, it was not
> possible, and therefore that Ada should have both.

I am not aware of that discussion, but mathematically, given a uniformly 
distributed real number F between 0.0 and 1.0, one can get a uniformly 
distributed discrete D between Low and high: D := Truncate(Low + F * 
(High-Low + 1)).

I guess, the issue that has been raised in that discussion that if F is of 
type float or even double-float, it has a mantissa of limited size, and 
then the distribution of D would significantly deviate from the uniform 
distribution if High-Low happens to be large. In the current case, 
however, High-Low < 50, so the solution using the uniformly distributed 
float should work properly. If D would significantly deviate from the 
uniform distribution, then so would F.



------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
     <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
--Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--

Re: Lotto simulation

[J-P. Rosen]

Le 16/06/2014 07:25, Stefan.Lucks@uni-weimar.de a écrit :
> I am not aware of that discussion, 
AFAIK, it's archived somewhere...

> but mathematically, given a uniformly
> distributed real number F between 0.0 and 1.0, one can get a uniformly
> distributed discrete D between Low and high: D := Truncate(Low + F *
> (High-Low + 1)).
I think it all depends on the definition of "uniformly distributed". If
it is uniformly distributed among all representable floating point
numbers (which you get if you take an integer random number and
unchecked-convert it to Float), you'll get many more values below 0.5
than above (since the range 0.5..1.0 is represented with only one value
of the exponent).

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: Lotto simulation

[Stefan.Lucks]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2730 bytes --]

On Mon, 16 Jun 2014, J-P. Rosen wrote:

>> but mathematically, given a uniformly
>> distributed real number F between 0.0 and 1.0, one can get a uniformly
>> distributed discrete D between Low and high: D := Truncate(Low + F *
>> (High-Low + 1)).
> I think it all depends on the definition of "uniformly distributed". If
> it is uniformly distributed among all representable floating point
> numbers (which you get if you take an integer random number and
> unchecked-convert it to Float), you'll get many more values below 0.5
> than above (since the range 0.5..1.0 is represented with only one value
> of the exponent).

Well, do you think the Annotated Reference Manual 
<http://www.ada-auth.org/standards/12aarm/html/AA-A-5-2.html> needs a 
clarification? It explicitely tells

   A sufficiently long sequence of random numbers obtained by successive
   calls to Random is approximately uniformly distributed over the range of
   the result subtype.

From my point of view, "uniformly distributed over the range of the result 
subtype" would seem to imply values > 0.5 to be as often as values < 0.5.

In fact, I would claim that any random generator, choosing floats between 
0.0 and 1.0 with a significant bias towards 0.0 or 1.0 would be plain 
stupid and worse than useless, and a standard which allows that, would 
need urgent repair!

Fortunately, my Ada compiler (gnat) is not such stupid and behaves as I 
had expected:

with Ada.Text_IO, Ada.Numerics.Float_Random, Ada.Command_Line;

procedure Test_Rnd is

    package ANFR renames Ada.Numerics.Float_Random;
    Gen: ANFR.Generator;

    High: Natural := 0;
    Sample_Size: constant Natural := Natural'Value(Ada.Command_Line.Argument(1));
begin
    ANFR.Reset(Gen);
    for I in 1 .. Sample_Size loop
       if ANFR.Random(Gen) > 0.5 then
 	 High := High + 1;
       end if;
    end loop;

    Ada.Text_IO.Put_Line(Integer'Image(High) &" /"& Integer'Image(Sample_Size));
end Test_Rnd;

Compiling and running the above program indicates an even distribution of 
values > 0.5 and <= 0.5 (i.e., there is no statistically significant 
bias):

$ ./test_rnd 100000000
  49999482 / 100000000
$ ./test_rnd 1000000000
  499991845 / 1000000000

Note that the results are biased towards 0.0, but the bias is 
statistically insignificant. (It would be statistically strange, indeed, 
if *exactly* half of the random values would be below 0.5, and the other 
half would be above.)

So long

------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
     <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
--Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--

Re: Lotto simulation

[J-P. Rosen]

Le 16/06/2014 13:15, Stefan.Lucks@uni-weimar.de a écrit :
> Well, do you think the Annotated Reference Manual
> <http://www.ada-auth.org/standards/12aarm/html/AA-A-5-2.html> needs a
> clarification? It explicitely tells
> 
>   A sufficiently long sequence of random numbers obtained by successive
>   calls to Random is approximately uniformly distributed over the range of
>   the result subtype.

OK, maybe it's another issue, and it's not my domain of knowledge. But I
certainly remember that the decision to provide separate discrete and
floating generators was deliberate and for good reasons. Maybe Randy
remembers where the discussions were archived?

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: Lotto simulation

[Natasha Kerensikova]

On 2014-06-16, J-P. Rosen <rosen@adalog.fr> wrote:
> Le 16/06/2014 13:15, Stefan.Lucks@uni-weimar.de a écrit :
>> Well, do you think the Annotated Reference Manual
>> <http://www.ada-auth.org/standards/12aarm/html/AA-A-5-2.html> needs a
>> clarification? It explicitely tells
>> 
>>   A sufficiently long sequence of random numbers obtained by successive
>>   calls to Random is approximately uniformly distributed over the range of
>>   the result subtype.
>
> OK, maybe it's another issue, and it's not my domain of knowledge. But I
> certainly remember that the decision to provide separate discrete and
> floating generators was deliberate and for good reasons. Maybe Randy
> remembers where the discussions were archived?
>
I would guess this is the same problem as going from a stream of random
bits to a discrete generator: you can use the random stream to fill bits
after a zero integral part and get 2^N uniformly-spread floating point
value.

However if you have a non-power-of-two discrete type, a simple
pigeonhole argument shows that the generator would be skewed towards
some values. For example using 3 random bits and applying a modulus to
choose between a 7-value enumeration would make the first value twice as
likely as the others. Using more random bits would of course lower the
bias, but it would never reach zero.

If random floating-point are generated using the simple algorithm above,
the bias is exactly the same, only distributed among different values.
More elaborate floating-point generator might lead to a different
distribution, or maybe even different total bias values, but you can't
get a zero-bias unless you use specific algorithms that tap directly
into the source random stream.


Hoping this helps,
Natasha

Re: Lotto simulation

[Randy Brukardt]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 794 bytes --]

"J-P. Rosen" <rosen@adalog.fr> wrote in message 
news:lnms40$gqa$1@dont-email.me...
> Le 16/06/2014 13:15, Stefan.Lucks@uni-weimar.de a écrit :
>> Well, do you think the Annotated Reference Manual
>> <http://www.ada-auth.org/standards/12aarm/html/AA-A-5-2.html> needs a
>> clarification? It explicitely tells
>>
>>   A sufficiently long sequence of random numbers obtained by successive
>>   calls to Random is approximately uniformly distributed over the range 
>> of
>>   the result subtype.
>
> OK, maybe it's another issue, and it's not my domain of knowledge. But I
> certainly remember that the decision to provide separate discrete and
> floating generators was deliberate and for good reasons. Maybe Randy
> remembers where the discussions were archived?

No, I don't. Sorry. - Randy.

Re: Lotto simulation

[Denis McMahon]

On Sun, 15 Jun 2014 10:07:59 -0700, montgrimpulo wrote:

> Any ideas to answer that question ?

Object ball has property number.

Create a set of 49 balls with numbers 1..49.

Pick a random ball from the set. The set now contains 48 balls.

Repeat until you have picked 6 balls.

-- 
Denis McMahon, denismfmcmahon@gmail.com

Re: Lotto simulation

[Dirk Heinrichs]

montgrimpulo wrote:

> this is a placeholder of the task which I am trying to solve in Ada.
> As you may know in German Lotto there are 49 numbers 1..49
> from which you have to select 6 numbers to place a bet.
> 
> Second Round:
> Here does my problem start. Now I have a set of numbers where
> one number - which was randomly selected in the first round -
> is missing. How do I use the random function to select another
> random number out of the rest ?
> 
> Any ideas to answer that question ?

Let's look at how it works in reality: A random ball is selected out of a 
set of 49 balls, mixed randomly before the pick, resulting in a new set of 
48 balls, etc.

So you'd need to start with a sorted array of integers 1 to 49, mix it 
randomly and then pick a random index out of 1 to 49. The number at that 
index is then removed from the array.

You'd then create a new array of 48 integers filled with the numbers at 1 to 
picked-1 plus picked+1 to 49 of the former array, mix that array again and 
pick a random index out of 1 to 48. Again remove the number at that index.

Dito for round 3 to 6.

HTH...

	Dirk
-- 
Dirk Heinrichs <dirk.heinrichs@altum.de>
Tel: +49 (0)2471 209385 | Mobil: +49 (0)176 34473913
GPG Public Key CB614542 | Jabber: dirk.heinrichs@altum.de
Sichere Internetkommunikation: http://www.retroshare.org

Re: Lotto simulation

[Simon Wright]

Dirk Heinrichs <dirk.heinrichs@altum.de> writes:

> montgrimpulo wrote:
>
>> this is a placeholder of the task which I am trying to solve in Ada.
>> As you may know in German Lotto there are 49 numbers 1..49
>> from which you have to select 6 numbers to place a bet.
>> 
>> Second Round:
>> Here does my problem start. Now I have a set of numbers where
>> one number - which was randomly selected in the first round -
>> is missing. How do I use the random function to select another
>> random number out of the rest ?
>> 
>> Any ideas to answer that question ?
>
> Let's look at how it works in reality: A random ball is selected out of a 
> set of 49 balls, mixed randomly before the pick, resulting in a new set of 
> 48 balls, etc.
>
> So you'd need to start with a sorted array of integers 1 to 49, mix it 
> randomly and then pick a random index out of 1 to 49. The number at that 
> index is then removed from the array.

Why mix it?

> You'd then create a new array of 48 integers filled with the numbers at 1 to 
> picked-1 plus picked+1 to 49 of the former array, mix that array again and 
> pick a random index out of 1 to 48. Again remove the number at that index.

But Ada.Numerics.Discrete_Random picks a random value of the
Result_Subtype it was instantiated with. So if you want to pick a number
in 1 .. 48 you have to create a new instantiation. And the RNG is going
to start off in some state, unrelated to the present state of the RNG
for 1 .. 49. How are you going to be sure that it's not going to return
1 every time?

Re: Lotto simulation

[Dirk Heinrichs]

Simon Wright wrote:

> Why mix it?

Thought that would be more realistic.

>> You'd then create a new array of 48 integers filled with the numbers at 1
>> to picked-1 plus picked+1 to 49 of the former array, mix that array again
>> and pick a random index out of 1 to 48. Again remove the number at that
>> index.
> 
> But Ada.Numerics.Discrete_Random picks a random value of the
> Result_Subtype it was instantiated with. So if you want to pick a number
> in 1 .. 48 you have to create a new instantiation. And the RNG is going
> to start off in some state, unrelated to the present state of the RNG
> for 1 .. 49. How are you going to be sure that it's not going to return
> 1 every time?

I was just trying to explain how the drawing works in reality w/o having any 
concrete Ada solution in mind. IMHO, once one ball is picked, a new 
situation is created, that's why I thought a new array would be a good idea.

OTOH, when the values in the array are mixed, would it matter if the RNG 
returned 1? It's just the array index.

Bye...

	Dirk
-- 
Dirk Heinrichs <dirk.heinrichs@altum.de>
Tel: +49 (0)2471 209385 | Mobil: +49 (0)176 34473913
GPG Public Key CB614542 | Jabber: dirk.heinrichs@altum.de
Sichere Internetkommunikation: http://www.retroshare.org

Re: Lotto simulation

[Simon Wright]

montgrimpulo <aghte@hotlinemail.com> writes:

> A workaround would be to test in each round, if that number has
> already been selected.  However, the probability would not be the same
> as with a reduced set as the selection would be always from the full
> set.

This seems perfectly reasonable.

If you think of numbered balls like the UK lottery, and after each pick
replace the picked ball by one without a number.  By the time you get to
the last 2 numbered balls, each of them has a 50% chance of being the
one that's eventually picked, no matter how many times you discard
unnumbered balls. Depending on the RNG, of course.

Another possibility: create an array of {ball-number, random-float},
sort by the random-float component, choose the first N entries.

Re: Lotto simulation

[Jeffrey Carter]

On 06/15/2014 10:07 AM, montgrimpulo wrote:
>
> this is a placeholder of the task which I am trying to solve in Ada.
> As you may know in German Lotto there are 49 numbers 1..49
> from which you have to select 6 numbers to place a bet.

I would usually define

type Lotto_List is array (T1_49) of T1_49;

List : Lotto_List;

Then fill List so that it contains (1 => 1, 2 => 2, 3 => 3, ...).

Then, for I in List'range, select a random Index, and swap the values in I and 
Index. Finally, use the values in List (1 .. 6).

That doesn't have the same probabilities as picking 6 balls out of 49. If you 
want that, you have to do

for I in List'First .. List'Last - 1 loop
    select random Index in I + 1 .. List'Last
    swap I and Index
end loop;

which is a little more complex if you use Discrete_Random. The random number 
generators in the PragmAda Reusable Components all come with functions to return 
a value in an integral range, so I generally use one of them rather than one of 
the predefined generators.

http://pragmada.x10hosting.com/pragmarc.htm

-- 
Jeff Carter
"This trial is a travesty. It's a travesty of a mockery of a
sham of a mockery of a travesty of two mockeries of a sham. ...
Do you realize there's not a single homosexual on that jury?"
Bananas
27

Re: Lotto simulation

[Markus Schöpflin]

Am 15.06.2014 19:07, schrieb montgrimpulo:
> Hi,
>
> this is a placeholder of the task which I am trying to solve in Ada.
> As you may know in German Lotto there are 49 numbers 1..49
> from which you have to select 6 numbers to place a bet.

[...]

The easiest way AFAIK is to random shuffle an integer array containing the 
numbers 1 - 49 and then selecting the first six numbers from that array.

Random shuffling can be achieved by filling a second array of the same size 
with random numbers obtained from a generator having a uniform distribution 
and then sorting this second array; moving the numbers from the first array in 
lock-step.

HTH, Markus

Re: Lotto simulation

[Jacob Sparre Andersen]

Markus Schöpflin wrote:

> The easiest way AFAIK is to random shuffle an integer array containing
> the numbers 1 - 49 and then selecting the first six numbers from that
> array.
>
> Random shuffling can be achieved by filling a second array of the same
> size with random numbers obtained from a generator having a uniform
> distribution and then sorting this second array; moving the numbers
> from the first array in lock-step.

Another option could be to fill one array:

      type Balls is range 1 .. 49;
      type Ordered_List_Of_Balls is array (Balls) of Balls;
      Ordered_Balls : Ordered_List_Of_Balls
   begin
      for Ball in Ordered_Balls'Range loop
         Ordered_Balls (Ball) := Ball;
      end loop;

Then shuffle the balls in that array:

      for Primary in Ordered_Balls'Range loop
         Swap (List       => Ordered_Balls,
               Position_1 => Primary,
               Position_2 => Random (Generator));
      end loop;

... where I have assumed "sensible" declarations of Swap and Generator.

Greetings,

Jacob
-- 
Statistics is like a bikini - what it shows is very suggestive,
but the most important stuff is still hidden.

Re: Lotto simulation

[Dmitry A. Kazakov]

On Sun, 15 Jun 2014 10:07:59 -0700 (PDT), montgrimpulo wrote:

> this is a placeholder of the task which I am trying to solve in Ada.
> As you may know in German Lotto there are 49 numbers 1..49 
> from which you have to select 6 numbers to place a bet.

I suppose you want non-repeating [pseudo] random numbers. Here is an
implementation of:

http://www.dmitry-kazakov.de/ada/components.htm#13.1

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de