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
or*******@yahoo .com

[SteveE]

David Turner wrote:

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 ?

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]

David Turner wrote:

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
or*******@yahoo .com

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

[Amey Samant]

"David Turner" <or*******@yaho o.com> wrote in message news:<7H******* ************@ne ws4.srv.hcvlny. cv.net>...

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
or*******@yahoo .com

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...]

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" <am*****@yahoo. com> wrote in message
news:66******** *************** ***@posting.goo gle.com...

"David Turner" <or*******@yaho o.com> wrote in message

news:<7H******* ************@ne ws4.srv.hcvlny. cv.net>...

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
or*******@yahoo .com

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

[Amey Samant]

<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]

>

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

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]

SteveE <ea****@btinter net.com_> wrote in message news:<Ai******* **************@ news-text.cableinet. net>...

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

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]

> 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
;)
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.
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

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]

hi Steve
its great to discuss & clear things up ....

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.
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 ?
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 ;)
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 " ;)

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.

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