For Markov chains I believe you will need the conjunction Power ^: ,
verbs From { and Roll ? , and matrix multiplication which is (+/ . *) .
Roll ? is a random number generator. For testing, verb ?. produces the
same "random" numbers every time it is called. Read the examples in
Vocabulary pages available at
http://www.jsoftware.com/docs/help701/dictionary/vocabul.htm
Note: Below 1r6 is the fraction 1 over 6 .
Suppose your transition matrix is
]p =: 3 3 $ 1r2 1r6 1r3 1r2 0 1r2 1r3 1r3 1r3
1r2 1r6 1r3
1r2 0 1r2
1r3 1r3 1r3
These are the one-step probabilities for moving from state i to state j
where i and j run from 0 to 2 (subscripts start at 0 in J). For example,
(<0 1) { p
1r6
is the one-step probability of moving from state 0 to state 1, and
1 { p
1r2 0 1r2
are the one-step probabilities of moving from state 1 to states 0, 1,
and 2 respectively.
Let
mm =: +/ . * NB. matrix multiplication
Then
p mm p
4r9 7r36 13r36
5r12 1r4 1r3
4r9 1r6 7r18
are the probabilities for moving from state i to state j in two steps, and
p mm^: 0 1 2 p
1r2 1r6 1r3
1r2 0 1r2
1r3 1r3 1r3
4r9 7r36 13r36
5r12 1r4 1r3
4r9 1r6 7r18
95r216 7r36 79r216
4r9 13r72 3r8
47r108 11r54 13r36
are the probabilities for one- , two- , and three-step transitions.
Check:
p mm p mm p
95r216 7r36 79r216
4r9 13r72 3r8
47r108 11r54 13r36
If your word list is
]w =: 'come';'supper';'to'
+----+------+--+
|come|supper|to|
+----+------+--+
you can do
0 2 1 { w
+----+--+------+
|come|to|supper|
+----+--+------+
You will have to figure out how to use the state probabilities and Roll
to choose the next state. It may be better to work with the decimal
form of p
]dp =: 10 * 0.1 * p NB. one way to get decimal form
0.5 0.166667 0.333333
0.5 0 0.5
0.333333 0.333333 0.333333
dp mm^:_ dp
0.439024 0.195122 0.365854
0.439024 0.195122 0.365854
0.439024 0.195122 0.365854
These are the limiting probabilities for a large-number-of-steps
transition. No matter where you begin, after a large number of steps
the approximate probabilities of being in states 0 1 2 are respectively
0.439 0.195 0.366 .
On 11/12/2011 12:43 AM, Daniel Lyons wrote:
> Hi,
>
> I'm playing with J, just trying to get into the J mindset. A small program I
> wrote recently in another language was a small Markov chain sentence
> generator. This program had essentially two parts: parsing some input into
> some kind of internal representation, and generating sentences randomly using
> that. I'm trying to figure out how one would go about doing this in J.
>
> My first thought is to make a bunch of nested boxed arrays, so given a sample
> input string it would produce a pair of arrays, one with the unique set of
> words, and another with boxed arrays of successor words. But stumbling onto
> the lab that discusses a dice game it seems like it might be more natural to
> write this in terms of some kind of transition table.
>
> I am not looking for a concrete solution so much as clues as to how a J
> programmer would decompose this problem, and what techniques would be
> involved in solving it.
>
> Thanks,
>
> —
> Daniel Lyons
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
