heatmap
• Posts: 2294
Joined: Feb 12, 2018
May 18th, 2023 at 4:53:23 AM permalink
Can i use a markov chain as a way to generate ANY type of results?
ThatDonGuy
• Posts: 6471
Joined: Jun 22, 2011
Thanked by
May 18th, 2023 at 4:09:49 PM permalink
I don't know about a Markov chain per se, but the "standard" RNG I learned is a chain.

You can generate a "random" set of N different numbers from 0 to N-1 by starting with an arbitrary number R, and then the next R = (aR + b) mod N.
The conditions for choosing a and b under which this works are:
1. The greatest common factor of N and b = 1
2. a - 1 is a multiple of all of the prime factors of N.
3. Either a mod 4 = 1, or N mod 4 = 0.

For example, let N = 8
b can be any odd number
The only prime factor of N is 2, so a - 1 is a multiple of 2;, a can be any odd number (so far)
N mod 4 = 0, so a mod 4 = 1; a can be any number that is 1 more than a multiple of 4
Let a = 5 and b = 3
Start with 0; the sequence is 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, and so on, repeating itself.
heatmap
• Posts: 2294
Joined: Feb 12, 2018
May 18th, 2023 at 6:34:28 PM permalink
Quote: ThatDonGuy

I don't know about a Markov chain per se, but the "standard" RNG I learned is a chain.

You can generate a "random" set of N different numbers from 0 to N-1 by starting with an arbitrary number R, and then the next R = (aR + b) mod N.
The conditions for choosing a and b under which this works are:
1. The greatest common factor of N and b = 1
2. a - 1 is a multiple of all of the prime factors of N.
3. Either a mod 4 = 1, or N mod 4 = 0.

For example, let N = 8
b can be any odd number
The only prime factor of N is 2, so a - 1 is a multiple of 2;, a can be any odd number (so far)
N mod 4 = 0, so a mod 4 = 1; a can be any number that is 1 more than a multiple of 4
Let a = 5 and b = 3
Start with 0; the sequence is 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, and so on, repeating itself.

thanks for your response... i have this feeling that no one answered because its kind of a rhetorical question i would assume because generating random numbers can be aided by markov chains... i think i need to reword the question... ive gotten them to understand what i meant in another thread but this one i feel is a bit different as i didnt really elaborate
Mental
• Posts: 1455
Joined: Dec 10, 2018
Thanked by
May 19th, 2023 at 12:57:39 PM permalink
Most pseudo-RNGs are the most uninteresting sorts of Markov chains. Every state makes a transition to exactly one other state with a probability of one. If there are a finite number of states, the chain eventually comes back to the starting state and then has to repeat the same sequence of states.

"A Markov chain is a mathematical system that experiences transitions from one state to another according to certain probabilistic rules. The defining characteristic of a Markov chain is that no matter how the process arrived at its present state, the possible future states are fixed."

Since there is no possibility of branching, the whole mathematics developed for Markov chains is wasted on such a trivial chain. The probability of being in each state is identical for every state.
This forum is more enjoyable after I learned how to use the 'Block this user' button.
Dobrij