From: "Mauricio Fernández" Date: 2003-04-19T04:32:38+09:00 Subject: Re: Biased weighted random? On Sat, Apr 19, 2003 at 02:24:36AM +0900, Chris Pine wrote: > 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 > 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