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

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 :-)
    # set the transition matrix @tmatrix
  end
end

Now if somebody were so kind as to fill in MarkovChain#calc_transitions ;-)

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	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