No such thing as a small change PerlMonks

### Re: bracketology was Re^2: making a markovian "mad lib"

by bliako (Prior)
 on Mar 23, 2019 at 11:39 UTC ( #1231592=note: print w/replies, xml ) Need Help??

The "markovian principle" is nothing more than the following simple tenet:

`next state depends (= is influenced) only on current state`

The context is a random process which outputs symbols (or it being in a "state"), one after another. For example, the process is "weather" during a single hour (i.e. 1 hour=1 weather state), with 3 states: "rain", "sunny", "dry-cloudy". And the outcome of this process is something like "rain"->"rain"->"sunny"->"dry-cloudy" ...

If that was a "markovian process" then we could describe it simply by a "transition matrix" which is a convenient way to convey the information of what the probability of "next" state is given "current" state in the form of a 2d array often called a stochastic matrix:

```            rain   sunny   dry-cloudy
rain         0.6    0.2      0.2
sunny        0.3    0.5      0.2
dry-cloudy   0.4    0.3      0.3

In the above array, row represents current state and column the next state, e.g. the probability of rain when now is raining is 0.6, the prob of dry-cloudy when now is sunny is 0.2 etc. The important property of the above matrix is that the probabilities of all the possible events from a current state must sum to 1: all rows sum to 1. Why? If we are now in current state of "rain" we have 3 possible outcomes. And so their probabilities must sum to one because one of them will happen with absolute certainty (as far as our model goes).

Similarly, one can use multi-dimensional arrays in order to model a random process whose next state depends on n-previous states. It will not be "markovian" but we can use the same tools.

So, the most important thing so far, forgetting about markov property etc, is that a random process outputs from a finite set of symbols with a probability depending on n-previous symbols and that can be modeled using a transition matrix as described above. In this matrix all the probabilities of the possible events from a current state must sum to 1.

Another useful tool (equivalent to the transition matrix) in modelling or visualising such random processes (of finite number of events) is a Graph, see the diagram here: Markov_chain.

Graph or transition matrix, once you built one by observing the weather for too long and finally estimating the transition probabilities, you can use it to simulate your random process. And make it produce random symbols.

The Graph or matrix can also be constructed by hand from imagination. Feed that information to your simulator in order to run the random process. That's probably how a computer game would calculate the weather in Mars.

I can not help you with your basketball model because I am not acquainted at all with these "big dances", "east", "west" etc. but perhaps you can rubber-duck it and in more general terms.

bw, bliako

Create A New User
Node Status?
node history
Node Type: note [id://1231592]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2021-01-25 07:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (263 votes). Check out past polls.

Notices?