Probabilistic Data Structure

[David Turner]

Hi All!,

Does anyone know a link to a website or know the best way to create a data
structure that will pick random elements from itself with assigned
probabilities?

For example, say I created a bag of 3 marbles(red, green, and blue) and the
red marble had a 50% change of being picked while the green and blue marbles
both had 25% chance of being picked. they should be picked randomly, but
picked in such a way that the red marble will be picked half the time and
the other 2 a quarter of the time. What is the best way to do this
algorithmically ?

Thanks,
David
orion7197@yahoo .com

[SteveE]

Re: Probabilistic Data Structure

David Turner wrote:[color=blue]
> Hi All!,
>
> Does anyone know a link to a website or know the best way to create a data
> structure that will pick random elements from itself with assigned
> probabilities?
>
> For example, say I created a bag of 3 marbles(red, green, and blue) and the
> red marble had a 50% change of being picked while the green and blue marbles
> both had 25% chance of being picked. they should be picked randomly, but
> picked in such a way that the red marble will be picked half the time and
> the other 2 a quarter of the time. What is the best way to do this
> algorithmically ?[/color]

The way I would do it, for your example, would be to create an array of
4 elements, with 0 and 1 = 'red', 2 = 'green' and 3 = 'blue', then
randomly select elements 0 to 3 evenly.

SteveE

[Mitch Williams]

Re: Probabilistic Data Structure

David Turner wrote:[color=blue]
> Hi All!,
>
> Does anyone know a link to a website or know the best way to create a data
> structure that will pick random elements from itself with assigned
> probabilities?
>
> For example, say I created a bag of 3 marbles(red, green, and blue) and the
> red marble had a 50% change of being picked while the green and blue marbles
> both had 25% chance of being picked. they should be picked randomly, but
> picked in such a way that the red marble will be picked half the time and
> the other 2 a quarter of the time. What is the best way to do this
> algorithmically ?
>
> Thanks,
> David
> orion7197@yahoo .com
>
>
>
>[/color]

If you only need divisions of two, you might be able to cook up somthing
using a binary tree.

[Amey Samant]

Re: Probabilistic Data Structure

"David Turner" <orion7197@yaho o.com> wrote in message news:<7HJbb.443 6$JM.3813101@ne ws4.srv.hcvlny. cv.net>...[color=blue]
> Hi All!,
>
> Does anyone know a link to a website or know the best way to create a data
> structure that will pick random elements from itself with assigned
> probabilities?
>
> For example, say I created a bag of 3 marbles(red, green, and blue) and the
> red marble had a 50% change of being picked while the green and blue marbles
> both had 25% chance of being picked. they should be picked randomly, but
> picked in such a way that the red marble will be picked half the time and
> the other 2 a quarter of the time. What is the best way to do this
> algorithmically ?
>
> Thanks,
> David
> orion7197@yahoo .com[/color]

hi there
u can maintain array of nodes with their respective probabilities & an
array to maintain how many times the node was chosen till time & then
generate a random number & check if the no of times > no of times it
should have been chosen then generate another no else chose that node
this is it
regards
amey

[Phil...]

Re: Probabilistic Data Structure

How about if you define a set
of intervals that subdivide the
interval [0,1) in proportion to
the probabilities you desire. Then
generate a random number whose
value selects one of the intervals.
e.g. item 1 is 50 percent so interval is [0,0.5)
item 2 is 25 % so [0.5,0.75)
item 3 is 25% so [0.75,1)
random number is 0.67 so item 2 is selected.

Data structure is an array containing the lower and upper
bounds of each interval. Index of the array is the item.

"Amey Samant" <ameyas7@yahoo. com> wrote in message
news:669e50b8.0 309260603.71141 229@posting.goo gle.com...[color=blue]
> "David Turner" <orion7197@yaho o.com> wrote in message[/color]
news:<7HJbb.443 6$JM.3813101@ne ws4.srv.hcvlny. cv.net>...[color=blue][color=green]
> > Hi All!,
> >
> > Does anyone know a link to a website or know the best way to create a[/color][/color]
data[color=blue][color=green]
> > structure that will pick random elements from itself with assigned
> > probabilities?
> >
> > For example, say I created a bag of 3 marbles(red, green, and blue) and[/color][/color]
the[color=blue][color=green]
> > red marble had a 50% change of being picked while the green and blue[/color][/color]
marbles[color=blue][color=green]
> > both had 25% chance of being picked. they should be picked randomly, but
> > picked in such a way that the red marble will be picked half the time[/color][/color]
and[color=blue][color=green]
> > the other 2 a quarter of the time. What is the best way to do this
> > algorithmically ?
> >
> > Thanks,
> > David
> > orion7197@yahoo .com[/color]
>
> hi there
> u can maintain array of nodes with their respective probabilities & an
> array to maintain how many times the node was chosen till time & then
> generate a random number & check if the no of times > no of times it
> should have been chosen then generate another no else chose that node
> this is it
> regards
> amey[/color]

[Amey Samant]

Re: Probabilistic Data Structure

<snip>
The way I would do it, for your example, would be to create an array
of
4 elements, with 0 and 1 = 'red', 2 = 'green' and 3 = 'blue', then
randomly select elements 0 to 3 evenly.

SteveE
</snip>

hi steve
this wont work.
consider if there are around 100 elements
& lets say an element 'red' has 10% prob & you have placed it in 0-9

in this case ... do you guarantee that once the 0-9 numbers have
already been selected randomly once, they are not selected before
other numbers are selected randomly
i mean random generator does not guarantee that the number selected
once is not selected again before all numbers are exhausted
thus in your case though you have provided only space for 10 for 'red'
it might be selected more than 10 times in 100 experiments thus
violating its given prob

hope i made it clear

regards
amey

[SteveE]

Re: Probabilistic Data Structure

>[color=blue]
> hi steve
> this wont work.
> consider if there are around 100 elements
> & lets say an element 'red' has 10% prob & you have placed it in 0-9
>
> in this case ... do you guarantee that once the 0-9 numbers have
> already been selected randomly once, they are not selected before
> other numbers are selected randomly
> i mean random generator does not guarantee that the number selected
> once is not selected again before all numbers are exhausted
> thus in your case though you have provided only space for 10 for 'red'
> it might be selected more than 10 times in 100 experiments thus
> violating its given prob[/color]

OK, it does rely on the random number generator producing an even spread.

If you need guarantee an even distribution then what about shuffling the
100 elements randomly and selecting incrementally, repeating the shuffle
every 100 elements?

SteveE

[Amey Samant]

Re: Probabilistic Data Structure

SteveE <eaborn@btinter net.com_> wrote in message news:<Ai%db.398 6$oH1.33858631@ news-text.cableinet. net>...[color=blue]
> OK, it does rely on the random number generator producing an even spread.
>
> If you need guarantee an even distribution then what about shuffling the
> 100 elements randomly and selecting incrementally, repeating the shuffle
> every 100 elements?
>
> SteveE[/color]

hi StevE
see you agreed that random number generation would cause problem in
first case then again in your answer you are talking about shuffling
elements RANDOMLY :d how would you solve the second RANDOM case then
;)
neways
another issues with this could be COST
if there are 1000 elements , shuffling 1000 elements for every element
would make your program much slower as the complexity increases
TREMENDOUSLY with this logic

regards
amey

[SteveE]

Re: Probabilistic Data Structure

> see you agreed that random number generation would cause problem in[color=blue]
> first case then again in your answer you are talking about shuffling
> elements RANDOMLY :d how would you solve the second RANDOM case then
> ;)[/color]

There will always be restriction of psuedo-random numbers never trully
being random (unless you use some exotic external generator) when using
computers. This method will guarantee an even distribution over the
number of iterations required, you just need to ensure you shuffle
sufficiently to give the 'appearance' of being genuinely random.
[color=blue]
> neways
> another issues with this could be COST
> if there are 1000 elements , shuffling 1000 elements for every element
> would make your program much slower as the complexity increases
> TREMENDOUSLY with this logic[/color]

No, I don't think the complexity changes at all. The actual data
retrieval would be very fast, but you would pay a time cost when
shuffling depending on the distribution, number of elements required and
iterations used. Then again, shuffling data around is what computers are
all about ;)

I think it all boils down to the exact requirements and constraints. For
instance, the original poster's example would only require 4 elements.
You could even factor this up to 40000 elements to defer the shuffling,
depending on the frequency of calls, memory available, etc.

There is another beneficial side-effect of using this method, which is
that the time taken for data retrieval and shuffling is constant (as
much as you can be in Java), whereas a 'hit and miss' approach, where
values are rejected until within the required distribution, is entirely
unpredictable time-wise (well, pseudo-unpredictable at least :)

SteveE

[Amey Samant]

Re: Probabilistic Data Structure

hi Steve
its great to discuss & clear things up ....
[color=blue]
> There will always be restriction of psuedo-random numbers never trully
> being random (unless you use some exotic external generator) when using
> computers. This method will guarantee an even distribution over the
> number of iterations required, you just need to ensure you shuffle
> sufficiently to give the 'appearance' of being genuinely random.[/color]

i tried this code

import java.util.*;
class TestRandom
{
public static void main(String[] args)
{
Random ran =new Random(10);
for(int i=0;i<10;i++)
System.out.prin tln(i+" - "+ran.nextInt(1 0));
}
}

this should generate 10 random numbers. i goes from 0 - 9 & random
number bounds are 0 - 9 as well .

& the results were as follows
OUTPUT :

0 - 3
1 - 0
2 - 3
3 - 0
4 - 6
5 - 6
6 - 7
7 - 8
8 - 1
9 - 4

is this evenly distributed ?
how would you shuffle such that you always get HIT or at least try to
maximize HITs ?
[color=blue]
> No, I don't think the complexity changes at all. The actual data
> retrieval would be very fast, but you would pay a time cost when
> shuffling depending on the distribution, number of elements required and
> iterations used. Then again, shuffling data around is what computers are
> all about ;)[/color]

swapping has always been an expensive task especiaaly when it comes
inside nested loop.
here is a joke (my own creation) "swapping = three variables , three
instructions to swap two values " ;)

[color=blue]
> I think it all boils down to the exact requirements and constraints. For
> instance, the original poster's example would only require 4 elements.
> You could even factor this up to 40000 elements to defer the shuffling,
> depending on the frequency of calls, memory available, etc.[/color]

no, i agree that requirements play role but what when number of values
is known only at runtime?
even if you know that there are 4 elements today, do you assume that
there will not be more than 100 elements in your next version/upgrade
;) ?
this way your entire logic would change with change in quantity which
may not be desirable.
when the no. of elements are FIXED then it is ok to choose by this
way.

regards
amey

[Phil...]

Re: Probabilistic Data Structure

For a long time people wondered how many "shuffles" it takes
to say the cards are now sufficiently mixed for the next deal.
Within the last several years I believe there was a proof that
it takes 5.


"Amey Samant" <ameyas7@yahoo. com> wrote in message
news:669e50b8.0 310032124.626e4 8fe@posting.goo gle.com...[color=blue]
> hi Steve
> its great to discuss & clear things up ....
>[color=green]
> > There will always be restriction of psuedo-random numbers never trully
> > being random (unless you use some exotic external generator) when using
> > computers. This method will guarantee an even distribution over the
> > number of iterations required, you just need to ensure you shuffle
> > sufficiently to give the 'appearance' of being genuinely random.[/color]
>
> i tried this code
>
> import java.util.*;
> class TestRandom
> {
> public static void main(String[] args)
> {
> Random ran =new Random(10);
> for(int i=0;i<10;i++)
> System.out.prin tln(i+" - "+ran.nextInt(1 0));
> }
> }
>
> this should generate 10 random numbers. i goes from 0 - 9 & random
> number bounds are 0 - 9 as well .
>
> & the results were as follows
> OUTPUT :
>
> 0 - 3
> 1 - 0
> 2 - 3
> 3 - 0
> 4 - 6
> 5 - 6
> 6 - 7
> 7 - 8
> 8 - 1
> 9 - 4
>
> is this evenly distributed ?
> how would you shuffle such that you always get HIT or at least try to
> maximize HITs ?
>[color=green]
> > No, I don't think the complexity changes at all. The actual data
> > retrieval would be very fast, but you would pay a time cost when
> > shuffling depending on the distribution, number of elements required and
> > iterations used. Then again, shuffling data around is what computers are
> > all about ;)[/color]
>
> swapping has always been an expensive task especiaaly when it comes
> inside nested loop.
> here is a joke (my own creation) "swapping = three variables , three
> instructions to swap two values " ;)
>
>[color=green]
> > I think it all boils down to the exact requirements and constraints. For
> > instance, the original poster's example would only require 4 elements.
> > You could even factor this up to 40000 elements to defer the shuffling,
> > depending on the frequency of calls, memory available, etc.[/color]
>
> no, i agree that requirements play role but what when number of values
> is known only at runtime?
> even if you know that there are 4 elements today, do you assume that
> there will not be more than 100 elements in your next version/upgrade
> ;) ?
> this way your entire logic would change with change in quantity which
> may not be desirable.
> when the no. of elements are FIXED then it is ok to choose by this
> way.
>
> regards
> amey[/color]

[SteveE]

Re: Probabilistic Data Structure

Amey Samant wrote:[color=blue]
> hi Steve
> its great to discuss & clear things up ....[/color]

Nothing like a good debate :)
[color=blue]
>snipped code<[/color]
[color=blue]
> is this evenly distributed ?
> how would you shuffle such that you always get HIT or at least try to
> maximize HITs ?[/color]

OK, you would probably get a more even distribution over say, 1,000,000
iterations. It also depends on how good the random number generator is :)

I probably didn't explain my second idea very well, so here's some code:

---
import java.util.Colle ctions;
import java.util.Rando m;
import java.util.Vecto r;
public class Distribute {
public static void main(String[] args) {

Random rand = new Random(System.c urrentTimeMilli s());
int red = 0, green = 0, blue = 0;

//Use a Vector so we can use the Collections methods
Vector el = new Vector();
//50% distribution of Red, 25% Green, 25% Blue
el.add("Red");
el.add("Red");
el.add("Green") ;
el.add("Blue");

//main loop, let's try 400 (100*4) iterations
final int ITER = 100;
for (int j = 0; j < ITER; j++) {

//Nice handy method to shuffle the elements :)
//Note that shuffling elements only swaps
//pointers and not the data itself.
Collections.shu ffle(el, rand);

//display the shuffled elements
for (int i = 0; i < el.size(); i++) {

System.out.prin tln(el.get(i));

//let's keep a count of the different values
if (el.get(i).equa ls("Red"))
red++;
else if (el.get(i).equa ls("Green"))
green++;
else
blue++;
}
}

System.out.prin tln("Distributi on:");
System.out.prin tln(" Red " + (float)red / (ITER *
el.size()));
System.out.prin tln(" Green " + (float)green / (ITER *
el.size()));
System.out.prin tln(" Blue " + (float)blue / (ITER *
el.size()));
}
}
---
[color=blue]
> no, i agree that requirements play role but what when number of values
> is known only at runtime?
> even if you know that there are 4 elements today, do you assume that
> there will not be more than 100 elements in your next version/upgrade
> ;) ?
> this way your entire logic would change with change in quantity which
> may not be desirable.
> when the no. of elements are FIXED then it is ok to choose by this
> way.[/color]

The above code could be incorporated into an object where the number of
values and their weighting are assigned at instantiation, with a method
to return the values.

Cheers,
SteveE

[Amey Samant]

Re: Probabilistic Data Structure

SteveE <eaborn@btinter net.com_> wrote in message news:<PRYgb.146 0$0O2.10904763@ news-text.cableinet. net>...[color=blue]
> Amey Samant wrote:[/color]
[color=blue]
> I probably didn't explain my second idea very well, so here's some code:
>[/color]
hi

ye the code really works great
:D

cheers
amey