Consider we have a dataset of discrete values and want to create a random generator based on them. So we need to divide these values into zones (states). But how do people normally choose the number of states a Markov's chain should have? Generally speaking the more states you have, the less random the process will become. So what should the criteria be?
Stam, i examined the link carefully but it doesn't give an answer to my question.
I will try to rephrase my question.
A first order Markov chain can be represented with a NxN matrix. But what is the proper way to chose N if we are dealing with discrete values (non-integer in the general case)? Why should i prefer for example 10x10 and not 15x15 or 5x5 matrix?
That's the number of independent samples. The way to choose them from among the samples generated relies on the autocorrelation time of the quantity that's being measured. Cf. www.math.nyu.edu/faculty/goodman/teaching/Monte_Carlo/Sokal.ps
In other words: it's necessary to *study* and *learn* how the Monte Carlo method works. There doesn't exist any one line answer.
There seems to be no definite rule for finding out the (optimal?) order of a Markov chain. The order is context-specific; it depends on your model/theory and the nature of the data you have. If your model is about rainy-day-non-rainy-day transition, you have a Markov chain model of order two; denote a rainy day as 1 and a non-rainy day as 0. If you want to go a little deeper, you can have 3 states of nature: no rain, moderate rain and heavy rain. So, the context defines the order.
Theory defines the number of states. You cannot infer them from the data alone.
Thank you for your answers. So one option is statistical, which tells how random the generated samples are. And a second option is theoretical, depending on the expected precision of the generated data.
What about choosing the number of states depending on the frequency distribution of the generated data? Or in other words choosing them so that the frequency distributions of the input and output data are as close as possible? Do people use such approach?
Boris,
Going by frequency distribution has two problems. First the interval size is arbitrary. You can make as many intervals as you like. On what basis do you decide the interval size? Second, this would presume that the process is stationary. Looking at data alone will not reveal such properties.
Number of States should be chosen based on a layman fact that each state should be independent of each other (No matter if it becomes 5*5 or 10*10) but can form a sequence. For example there might be a chance of occurrence of state 3 just after state 2 in a 5 state samples. but state 3 and state 2 represents different meanings in context of your data.
Milind, Aman, nevertheless there are many situations where you would be mainly interested in the frequency distribution and other properties of the initial random sequence.
Consider you are interested in the expected daily solar radiation in a certain region during a certain month of the year. If you use synthetically generated data for the solar radiation it should have the same distribution, because this is what is expected for the investigated region and month. And generally speaking for such situation you aren't really interested if the generated data is truly random or if the states are independent of each other. However you would want to make sure the synthetic data has properties which are similar to that of the original data: frequency distribution, level crossing probabilities (or positive peak probabilities), first derivative distribution, etc.
For example the frequency distribution, combined with the level crossing probabilities define the probability for prolonged repeatable events. So if your random generator maintains the frequency distribution and the level crossing probability for 800 W/m2 it would also maintain the probability to have 5 (or 10 or 20) consecutive days with solar radiation above or below 800 W/m2.
Similar is the situation with the first derivative distribution. It would define the probability for sharp changes in the state.
From this point of view the number of states would greatly depend on the amount of the initial data. If for example you have 100 experimental samples, you can't have too many states. However if you have 10k experimental samples, your Markov chain could have more states (eventually, depending on the data).
- Badges
- Science topic
- Similar topics
- Human-Computer Interaction
- Collaboration