Biased weighted random?

ruby-talk
1

Hi, all…

Just thinking again about randomness.

A few weeks back I asked for a weighted random
algorithm, and several people responded with
nice ones.

Now I’m wanting to modify that problem.

Disclaimer: I’m not any kind of mathematician,
and I’m not sure that “biased” is the right
term here.

Given a set of pairs [item,weight] select an
item with likelihood corresponding to its
weight… but with a twist.

Ensure that (while the overall statistical
properties are as we expect), the likelihood
of the same item appearing twice consecutively
is relatively small. (As small as possible,
i.e., greater entropy or “variety” – think of
"quotation of the day" or some such thing.)

Example:

Given a,5 b,4 c,2

I’d prefer the sequence

a c a b a b c b a b a

to the sequence

a a c b a b b a a b c

Of course, it’s impossible to perfect this…
if your weights are sufficiently skewed, there
will always be some doubled items (or so my
gut tells me).

Thoughts?

Hal

2

Very interesting!

My wife and I have been talking about a “dinner suggestion” program and an
“activity suggestion” program with the same requirements. I never gave much
thought to the math behind it, though; I figured that part would be obvious.
I’m pleased to find that it isn’t!

Hmmm…

I think your gut is right, Hal: under sufficiently skewed weights, items
must repeat consecutively, or the distribution won’t follow your prescribed
probabilities. So just what are the conditions?

Well, (and I’m going to switch to float probabilities for now), if anything
is weighted more than 0.5, it will have to repeat. Assuming we absolutely
want to prevent repeats (which Katy and I do, and I’m supposing you do, too,
since this feels like a rather “psychological” algorithm), then something
with probability 0.5 will have to occur at every other spot. Weird. No
that doesn’t feel right.

Let’s try something else, which I know won’t work, but seeing how it won’t
work might be enlightening. It’s the bone-headed approach. :slight_smile: Let’s say
that at each step, we use the algorithm from your last email (provided by
Tabby or something, right?), but we retry if we get the same thing we got
last time. (This ought to break the distribution requirement.)

So if we have items a => 0.5, b => 0.25, c => 0.25, what happens? (Anyone
remember Markov chains? Let me see if I can look it up… I give up; I’ll
just make it up as I go along…)

So what are the long term probabilities of a, b, and c? We’ll call them pa,
pb, and pc. I will also let pa(c) refer to the probability of getting an
a', given that we just had a c’.

So:

pa = (pa(a) * pa) + (pa(b) * pb) + (pa(c) * pc)
pb =
pc =

But since pa(a) is 0 (we allow no repeats), this simplifies to:

pa = (pb * 0.6667) + (pc * 0.6667)
pb = (pa * 0.5 ) + (pc * 0.3333)
pc = (pa * 0.5 ) + (pb * 0.3333)

Which looks right, since the pa coefficients sum to 1, as with the pb and pc
coefficients. I guess that’s the stochastic matrix:

0, 0.5, 0.5 |
.67, 0, .33 |
.67, .33, 0 |

(Or are the columns supposed to add to 1? I don’t know… I think that if
that matrix is M, then (pa,pb,pc) * M = (pa,pb,pc)… or something. I’ll
just solve it the old-fashioned way. :slight_smile:

pb = pc by symmetry (just like i and -i, Daniel; just like true and false,
Phil :), so…

pa = 1.333 * pb

Since pa + pb + pc = 1,

pa = 0.4
pb = 0.3
pc = 0.3

Well, that wasn’t terribly enlightening, was it? :slight_smile:

Still, if your weights were 4 and 3 and 3, you’d know what to do! Just
apply the bone-headed approach with weights 2 and 1 and 1. So in general,
how do you do what we just did backwards? Probably something about
inverting the stochastic matrix… If you can’t tell, I slept through the
vast majority of linear algebra. (You’d think I’d be kicking myself right
about now, but I really needed that sleep…)

Also, what are the restrictions on the initial weights now?

I’ll hunt around for my old linear algebra book,

Chris

3

Why not just use the same method I wrote before, (call it
‘weighted_random’) but remove the entry that you don’t want to repeat:

Let ‘entries’ be a hash whose keys are the items and whose values
are the weights. Currently we can write:

item = weighted_random(entries)

And that gives you the proper weighted random. Now, how about this:

Pick 10 non-consecutively-repeating items with the appropriate

probability distributions:

item_last = nil
prob_last = nil
item_curr = nil
prob_curr = nil
10.times do
# delete the item we selected last time.
entries.delete(item_curr)

# Put back the item we selected the time before.
entries[item_last] = prob_last unless item_last == nil

# Get the new random item, and rotate.
item_last, prob_last = item_curr.clone, prob_curr.clone
item_curr = weighted_random(entries)
prob_curr = entries[item_2]

# Do something with item_2, prob_2

end

Now they should never repeat.

Does this look right?

Daniel.

···

On Fri, Apr 18, 2003 at 11:09:52PM +0900, Hal E. Fulton wrote:

Hi, all…

Just thinking again about randomness.

A few weeks back I asked for a weighted random
algorithm, and several people responded with
nice ones.

Now I’m wanting to modify that problem.

Disclaimer: I’m not any kind of mathematician,
and I’m not sure that “biased” is the right
term here.

Given a set of pairs [item,weight] select an
item with likelihood corresponding to its
weight… but with a twist.

Ensure that (while the overall statistical
properties are as we expect), the likelihood
of the same item appearing twice consecutively
is relatively small. (As small as possible,
i.e., greater entropy or “variety” – think of
“quotation of the day” or some such thing.)

Example:

Given a,5 b,4 c,2

I’d prefer the sequence

a c a b a b c b a b a

to the sequence

a a c b a b b a a b c

Of course, it’s impossible to perfect this…
if your weights are sufficiently skewed, there
will always be some doubled items (or so my
gut tells me).

Thoughts?

Hal

–
Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137

4

Example:

Given a,5 b,4 c,2

I’d prefer the sequence

a c a b a b c b a b a

to the sequence

a a c b a b b a a b c

Of course, it’s impossible to perfect this…
if your weights are sufficiently skewed, there
will always be some doubled items (or so my
gut tells me).

Track the last result, and lower the probablility of that particular one
– helps eliminate the doubles.

Anything truly random with no state will certainly give dups, but
there’s nothing against keeping a state hash, in theory, that tells what
should come next to “seem” random, or track the stats and re-weight the
remainder accodringly.

5

You know, in talking with my wife about this, I think we have
over-simplified the problem.

Take, for example, the simple weighting:

{a => 1, b => 1, c => 1, d => 1}

Now, if I have so far generated the following:

a, b, c, a, c, b, c, a

Shouldn’t it be heavily weighting a `d’ now? (I’m not sure about Hal’s
uses for this algorithm, but for something like a recipe program, it’s
really about time we had pork chops, you know?) And the larger your sample
size (be these favorite songs, recipes, activities… whatever), the greater
the chances of something “falling through the cracks” so to speak. However,
a large sample size is exactly when this is useful!

It seems like we should be taking into consideration not only which item was
generated last, but how long it has been since that item was last chosen
for all items. (It would be totally unsatisfying to miss going to the Zoo
for a decade, only to go every other weekend for two months.)

When you take into consideration different weightings of events, the problem
gets trickier (but I definitely want to go swimming more often than to the
Zoo). Essentially, you want the probabilities to converge to your
weighting.

My guess is that the best way to do this is to keep track of the current
probabilities and weight based partially upon the differences between
desired and current probabilities. Still, you would also need to look at
time-to-last-occurence for getting the right “feel” in long-term runs (when
individual choosings don’t change the probabilities much).

I’ll think about it,

Chris

6

I believe too the right model is a Markov process (chain), given the
following restrictions:

NOTATION
number of possible outcomes of the associated random var: N
stationary distribution (probability vector): v
transition matrix: P

[given v and the following restrictions, we want to find P]

by definition, the stationary distribution satisfies
vP = v
ie., it is an eigenvector of P, for the corresponding eigenvalue 1.
We will thus have the following restrictions:

P[i,i] = 0 for 0 <= i <= N repetitions not allowed
sum(P[j,i] * v[j], j = 1…N) = v[i] (means sum from j = 1 to j = N)
for 0 <= i <= N
sum(P[i,j], j = 1…N) = 1 “” “”
P[i,j] > 0 0 <= i,j <= N

It is obvious that the conditions cannot always be fulfilled.

The code would look like

class MarkovChain
def initialize(probs, init_state = nil)
@probs = probs
calc_transitions
@state = init_state
@state ||= next_stateless
end

def next
@state = select(@tmatrix.to_a)
end

def next_stateless
select(@probs.to_a)
end

private

def select(arr)
p = rand
arr.each do |value, prob|
return value if p < prob
p -= prob
end
nil # should never happen
end

def calc_transitions
# solve the eigenvalue problem — the other way around :slight_smile:
# set the transition matrix @tmatrix
end
end

Now if somebody were so kind as to fill in MarkovChain#calc_transitions :wink:

···

On Sat, Apr 19, 2003 at 12:46:04AM +0900, Chris Pine wrote:

Very interesting!

My wife and I have been talking about a “dinner suggestion” program and an
“activity suggestion” program with the same requirements. I never gave much
thought to the math behind it, though; I figured that part would be obvious.
I’m pleased to find that it isn’t!

Hmmm…
So if we have items a => 0.5, b => 0.25, c => 0.25, what happens? (Anyone
remember Markov chains? Let me see if I can look it up… I give up; I’ll
just make it up as I go along…)

–
_ _

__ __ | | ___ _ __ ___ __ _ _ __
'_ \ / | __/ __| '_ _ \ / ` | ’ \
) | (| | |__ \ | | | | | (| | | | |
.__/ _,|_|/| || ||_,|| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

The only other people who might benefit from Linux8086 would be owners
of PDP/11’s and other roomsized computers from the same era.
– Alan Cox

7

Now they should never repeat.

Does this look right?

···

----- Original Message -----
From: “Daniel Carrera” dcarrera@math.umd.edu

Nope. :slight_smile:

See my earlier response. You met the “does not repeat” requirement, but
your distribution probabilities have been changed.

Mauricio summed it up well: Given a probability vector (sums to 1), we need
a transition matrix (rows sum to 1) with zeros on the diagonal with the
given vector as an eigenvector of eigenvalue 1. As he notes, it cannot
always be done.

Problems to work on:

  • For which probability vectors does the (or a? (it may not be unique))
    specified transition matrix exist?
  • What’s the matrix?

Working on it,

Chris

8

So, I think I’m close.

The repetition factor is really nice. What is also nice is that I don’t
have to keep track of running probabilities like I thought I would have to.

However, the distribution isn’t quite right (these should all be about
1000):

[973, 982, 988, 983, 954, 1003, 1031, 946, 970]

Not too bad, but look at some more:

[972, 942, 962, 973, 979, 1010, 1027, 939, 988]
[943, 961, 993, 977, 997, 1003, 1020, 990, 999]
[960, 962, 939, 973, 990, 1002, 1035, 961, 972]
[954, 924, 958, 983, 968, 1006, 1030, 960, 992]
[990, 972, 969, 987, 954, 1007, 1028, 938, 968]

These are converging to the wrong numbers; bummer. (Awfully tight
convergence, though, huh? Nice…)

So what do I do? I just weight each choice by the default weight multiplied
by how long it has been since we last saw this choice. Oh, except that I
squared the default weights first. (just seemed to work… )

So it’s really close… any ideas? And why the $@#! am I squaring the
weights??

Chris

···

class PsychoRandom
RESET_WEIGHT = 1 # Pretty sure this should NOT be 0.

def initialize weights
if !weights.kind_of?(Array)
# Sorry, but these need to be ordered; no hashes.
raise 'PsychoRandom needs array of [item, weight] pairs.'
end
@items = weights.map {|item,weight| item}
@w = weights.map {|item,weight| weight**2}
@n = @w.length
@t = Array.new(@n,@n*1000) # Encourage everything to come up once at
the beginning.
end

def currentWeights
(0…@n).map {|idx| @w[idx] * @t[idx]}
end

Tabby’s lovely method.

def getNextIndex
total = 0
pick = nil
currentWeights.each_with_index do |weight, idx|
total += weight
pick = idx if rand(total) < weight
end
# Modify times.
@t.map! {|x| x+1}
@t[pick] = RESET_WEIGHT
# Return chosen index.
pick
end

def getNextItem
@items[getNextIndex]
end
end

weights = [
[‘a’, 2],
[‘b’, 1],
[‘c’, 1],
[‘d’, 3],
[‘e’, 2],
[‘f’, 7],
[‘g’,11],
[‘h’, 1],
[‘i’, 3],
]
sumWeights = weights.inject(0) {|sum,pair| sum + pair[1]}

pr = PsychoRandom.new weights

1000.times {print pr.getNextIndex, ’ '}

puts

puts

timesSelected = weights.map {0}
(sumWeights*1000).times {timesSelected[pr.getNextIndex] += 1}

for i in 0…(timesSelected.length)
timesSelected[i] /= weights[i][1]
end

p timesSelected

9

There may be more than 1 transition matrix which works. For a distribution
of (0.4, 0.3, 0.3), there are at least these two:

0, 0.5, 0.5 |
.67, 0, .33 |
.67, .33, 0 |

0, .25, .75 |
1, 0, 0 |
.33, .67, 0 |

I found a way to find them all given rational probabilities, but it’s SLOW!
Also, I still don’t know when it will and won’t work without trying all
possibilities.

I’ll try to clean it up,

Chris

10

OK, it fails… but not miserably so.

I’ve taken Daniel’s idea and simplified it a little.

Here’s the code and the output. Notice how the ordering
requirement is met perfectly, but the frequencies are
naturally not correct then.

But for a “psychological” selection algorithm as Chris
(?) called it, this might be reasonable.

Then again, there’s probably a way to adjust the weights
dynamically so that things come out right.

Actually, this one is probably good enough for my own
purposes. But I’m still interested in the theory, so if
anyone has any more insights, I’m curious about them.

Cheers,
Hal

···

----- Original Message -----
From: “Chris Pine” nemo@hellotree.com
To: “ruby-talk ML” ruby-talk@ruby-lang.org
Sent: Friday, April 18, 2003 12:07 PM
Subject: Re: Biased weighted random?

----- Original Message -----
From: “Daniel Carrera” dcarrera@math.umd.edu

Now they should never repeat.

Does this look right?

Nope. :slight_smile:

See my earlier response. You met the “does not repeat” requirement, but
your distribution probabilities have been changed.

#---------------------------------
def random_weighted(items)
total = 0
pick = nil
items.each do |item, weight|
pick = item if rand(total += weight) < weight
end
pick
end

def try(trials)
entries = [ [“a”, 8], [“b”,6], [“c”,4], [“d”,2] ]
freq = {“a” => 0, “b” => 0, “c” => 0, “d” => 0}

last = nil
print “\n” if trials < 100
trials.times do
last = entries.find {|x| x[0]==last}
list = (entries-[last])
item = random_weighted(list)
last = item
print item if trials < 100
freq[item] += 1
end
print “\n” if trials < 100
“#{‘%6d’ % trials}: #{freq.inspect}”
end

puts try(20)
puts try(40)
puts try(80)
puts try(200)
puts try(2000)
puts try(20000)
puts try(200000)

--------------------------------

And the output…

acbababcadbabacacaba
20: {“a”=>9, “b”=>6, “c”=>4, “d”=>1}

babcdcacacabcdadcbcadbacbacabdabcadcbaba
40: {“a”=>13, “b”=>10, “c”=>11, “d”=>6}

bdabcadacbcacabcdbacbdabacabadbababcabdadbcabdabacdadcababdbacbdbcbabacacbac
abab
80: {“a”=>27, “b”=>25, “c”=>16, “d”=>12}
200: {“a”=>73, “b”=>61, “c”=>41, “d”=>25}
2000: {“a”=>700, “b”=>608, “c”=>449, “d”=>243}
20000: {“a”=>6842, “b”=>6064, “c”=>4492, “d”=>2602}
200000: {“a”=>68441, “b”=>60009, “c”=>45798, “d”=>25752}

11

So it’s really close… any ideas? And why the $@#! am I squaring the
weights??

···

----- Original Message -----
From: “Chris Pine” nemo@hellotree.com

Well, I think I figured out the squaring. Basically, I shouldn’t be
taking the square numbers, I should be taking the triangular numbers. So
change

weight**2

to

(weight * weight + weight) /2

It’s still not perfect, though. It’s really close, however. (It slightly
favors rare events.)

I must confess that it does allow repetition of an event; however, with a
large selection of events (20 or more, I’d say), it is profoundly
rare. On the upside, this algorithm works with every set of weights, even
something like (1, 20). (Of course, you can’t have both.)

So why the triangular numbers? Because when you consider something with
weight 1 five times in a row, it’s time-of-last-choosing (int the
poorly-named `t’ array) goes from 1 to 5. So it was given 1+2+3+4+5=15
chances. If you have something else which you want to have come up 5 times
as often, it needs a weight of 15 to compete with that… roughly.

So I’m quite pleased with this algorithm with a large number of objects (or,
I should say, with the largest weight being as small a percentage as
possible of the sum of all weights), which is what I want to use it for,
anyway. Could it be improved for smaller numbers of weights? Perhaps by
squaring the times in `t’ and modifying the weights somehow?? I don’t know.

Chris

12

0, 0.5, 0.5 |
.67, 0, .33 |
.67, .33, 0 |

0, .25, .75 |
1, 0, 0 |
.33, .67, 0 |

···

----- Original Message -----
From: “Chris Pine” nemo@hellotree.com

Looking at this again, it seems that the latter matrix is flawed. Not only
is it uglier (a reasonable complaint), but it isn’t “locally random”, so to
speak. The long term probabilities are correct, but every ‘b’ is followed
by an ‘a’.

So, uh… how do we define that “requirement”? Of all the matrices that
work, choose the most… “balanced”? What does that mean? (I love
psychological algorithms!)

Perhaps a matrix is “naturally balanced” if the ratio of any two
probabilities in any row is the same as the ratio of the corresponding
probabilities in your initial vector (ignoring the zeros of the diagonal).

I’m pretty sure such a matrix would be unique.

BTW, is this getting off-topic? Feels more like math than Ruby to me.
(But, if you’re lucky, programming gets that way sometimes!)

Chris

13

There may be more than 1 transition matrix which works. For a distribution
of (0.4, 0.3, 0.3), there are at least these two:

0, 0.5, 0.5 |
.67, 0, .33 |
.67, .33, 0 |

0, .25, .75 |
1, 0, 0 |
.33, .67, 0 |

I found a way to find them all given rational probabilities, but it’s SLOW!
Also, I still don’t know when it will and won’t work without trying all
possibilities.

I have one idea too but I’d need something to solve linear equations
systems. Couldn’t find anything in the RAA, so I guess the solution
would involve using lapack and some extension in C…

  1. given desired stationary prob vector, fill in the state transition
    matrix
    v = [v1, …, vn]
    P = |v1 … vn|

    … … …|
    v1 … vn|

  2. for i = 1 to n, P[i,i] = 0 and modify all other probs on the same
    row doing P[i,j] = P[i,j] / ( 1 - v[i] )
  3. calculate new stationary distribution u, solving uP = u
    ==> this step needs a linear equation system solver
  4. given u, calculate the diff to the desired distribution v - u
    delta = v - u
  5. solve the system
    sum( v[i] * m[i,j], i = 1…j-1, j+1…n) = delta[j] for j = 1…n
    sum( m[i,j], j = 1…n ) = 0 for j = 1…n
    m[i,i] = 0 for i = 1…n
  6. the final state transition matrix is P + m
···

On Sat, Apr 19, 2003 at 02:24:36AM +0900, Chris Pine wrote:

I’ll try to clean it up,

–
_ _

__ __ | | ___ _ __ ___ __ _ _ __
'_ \ / | __/ __| '_ _ \ / ` | ’ \
) | (| | |__ \ | | | | | (| | | | |
.__/ _,|_|/| || ||_,|| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

[…] or some clown changed the chips on a board and not its name.
(Don’t laugh! Look at the SMC etherpower for that.)
– from /usr/src/linux/MAINTAINERS

14

That’s exactly what I was doing!

···

----- Original Message -----
From: “Mauricio Fernández” batsman.geo@yahoo.com

  1. calculate new stationary distribution u, solving uP = u
    ==> this step needs a linear equation system solver

It’s a transition matrix; just square it a few times and grab any row.

:wink:

Chris

15

Here’s my Ruby so far. I’m still working on the second part.

···

require 'rational’
require ‘matrix’

w = [2,1,1] # weights

n = w.length
d = w.inject(0){|sum,x| sum+x} # common denominator

w.map!{|x| Rational.new(x,d)}

Matrix is an array of cols.

cols = Array.new(n){Array.new(n)}
for x in 0…n
for y in 0…n
cols[x][y] = 0
next if x == y
cols[x][y] = w[x]/(1-w[y])
end
end

transitionMatrix = Matrix.columns(cols)

newMatrix = transitionMatrix

5.times {newMatrix = newMatrix * newMatrix}

for i in 0…n
newMatrix.row(i) do |rat|
puts rat.to_f.to_s.ljust(15)
end
puts
puts '***********************'
puts
end

16

All right…

It’s not pretty, but it works and you only have to do it once, right at the
beginning of your endless random shuffle thing.

The idea is to use the “bonehead” algorithm, but not with your target
probabilities as the weights, since that won’t work.

Instead, use this program. Enter in your weights into the weights' array (inside the call tonormalize’ and run it.

Take the new weights to use (the first bunch of numbers) and put them into
your “bonehead” algorithm as the weights (assuming the probabilities shown
(second bunch of numbers) is close enough for you… if not, change the 50' in50.times’ to something bigger).

Should work much of the time…

Chris

···

require ‘matrix’

def normalize vector
d = vector.inject(0.0){|sum,x| sum+x} # common denominator
vector.map{|x| x/d}
end

def realProbVector vector
n = vector.length

Matrix is an array of cols.

cols = Array.new(n){Array.new(n)}
for x in 0…n
for y in 0…n
cols[x][y] = 0
next if x == y
cols[x][y] = vector[x]/(1-vector[y])
end
end

transitionMatrix = Matrix.columns(cols)

newMatrix = transitionMatrix

5.times {newMatrix = newMatrix * newMatrix}

newMatrix.row(0)
end

targets = normalize([2,1,1])
weights = targets.dup
probs = realProbVector(weights)

50.times do
weights.each_with_index do |x,idx|
weights[idx] += targets[idx] - probs[idx]
end
weights = normalize(weights)
probs = realProbVector(weights)
end

weights.to_a.each do |prob|
puts prob.to_s
end
puts
probs.to_a.each do |prob|
puts prob.to_s
end

17

From: “Chris Pine” nemo@hellotree.com

0, 0.5, 0.5 |
.67, 0, .33 |
.67, .33, 0 |

0, .25, .75 |
1, 0, 0 |
.33, .67, 0 |

Looking at this again, it seems that the latter matrix is flawed. Not only
is it uglier (a reasonable complaint), but it isn’t “locally random”, so to
speak. The long term probabilities are correct, but every ‘b’ is followed
by an ‘a’.

My bigger concern is that those columns don’t add up to 1.
These aren’t probability matrices.

Perhaps a matrix is “naturally balanced” if the ratio of any two
probabilities in any row is the same as the ratio of the corresponding
probabilities in your initial vector (ignoring the zeros of the diagonal).

The idea I proposed was based on the objective of keeping the ratios the
same (except for the event that is not supposed to repeat).

···

On Sat, Apr 19, 2003 at 03:03:44AM +0900, Chris Pine wrote:

----- Original Message -----

–
Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137

18

All right…

It’s not pretty, but it works and you only have to do it once, right at
the
beginning of your endless random shuffle thing.

The idea is to use the “bonehead” algorithm, but not with your target
probabilities as the weights, since that won’t work.

Instead, use this program. Enter in your weights into the weights' array (inside the call to normalize’ and run it.

Take the new weights to use (the first bunch of numbers) and put them into
your “bonehead” algorithm as the weights (assuming the probabilities shown
(second bunch of numbers) is close enough for you… if not, change the
50' in 50.times’ to something bigger).

[snip fascinating code]

  1. Are you sure you want to call Daniel’s method
    the bonehead algorithm? :slight_smile:

  2. This reminds me so much of when I studied
    mathematical models of population genetics. (It
    was my first real exposure to matrices… I had
    discrete math and calculus, but never linear
    algebra.)

  3. As I did back then, I can’t help wondering:
    Shouldn’t there be a simple non-iterative solution
    for this? Or at least non-matrix? Something like,
    umm, find the geometric mean and divide each weight
    by that and multiply by the price of tea in China?

Hal

···

----- Original Message -----
From: “Chris Pine” nemo@hellotree.com
To: “ruby-talk ML” ruby-talk@ruby-lang.org
Sent: Friday, April 18, 2003 3:33 PM
Subject: Re: Biased weighted random?

19

From: “Chris Pine” nemo@hellotree.com

0, 0.5, 0.5 |
.67, 0, .33 |
.67, .33, 0 |

0, .25, .75 |
1, 0, 0 |
.33, .67, 0 |

Looking at this again, it seems that the latter matrix is flawed. Not only
is it uglier (a reasonable complaint), but it isn’t “locally random”, so to
speak. The long term probabilities are correct, but every ‘b’ is followed
by an ‘a’.

My bigger concern is that those columns don’t add up to 1.
These aren’t probability matrices.

The rows do. I guess the transposed is OK, then :slight_smile:
We’re doing v’ = vP where you expected u’ = Pu.

Perhaps a matrix is “naturally balanced” if the ratio of any two
probabilities in any row is the same as the ratio of the corresponding
probabilities in your initial vector (ignoring the zeros of the diagonal).

The idea I proposed was based on the objective of keeping the ratios the
same (except for the event that is not supposed to repeat).

But it does change the stationary distribution, doesn’t it?

···

On Sat, Apr 19, 2003 at 05:59:55AM +0900, Daniel Carrera wrote:

On Sat, Apr 19, 2003 at 03:03:44AM +0900, Chris Pine wrote:

----- Original Message -----

–
_ _

__ __ | | ___ _ __ ___ __ _ _ __
'_ \ / | __/ __| '_ _ \ / ` | ’ \
) | (| | |__ \ | | | | | (| | | | |
.__/ _,|_|/| || ||_,|| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

And Bruce is effectively building BruceIX
– Alan Cox

20

The idea I proposed was based on the objective of keeping the ratios the
same (except for the event that is not supposed to repeat).

···

----- Original Message -----
From: “Daniel Carrera” dcarrera@math.umd.edu

But it didn’t.

Look at Hal’s example, with the weights of 2, 4, 6, and 8. The object with
weight 2 came up more than half as much as the object with weight 4. The
ratios (the probabilities) were changed.

Chris