Timothy S. answered • 10/15/13
Tutor
5
(9)
Will help you LOVE math, science, and computing!
To do this analytically, you are going to have to make use of some number theory.
I would first ask for what study is this for?
If your query does not require an analytical solution. It may suffice to write a small program to perform the calculation of T(S,n) many times and construct a histogram of the output. The resulting probability density function is easily normalized, thereby yielding the probability of the output space.
If I understand correctly, your problem is:
given a number
n∈{k:1≤k≤N ∧ k∈Z+}
and a function
T(S) = {[n + rand(0, (c0 % S))] % (c2 - c3) } + (Σs∈{k:1≤k≤S-1 ∧ k∈Z+}T(s))%c3
you would like either a formula, or an algorithm for computing P(T(s) == c4∈{k:0≤k≤20 ∧ k∈Z+})
Effectively asking how many times over your domain a specific element of the range occurs...
Is that correct?
Timothy S.
Okay, let's formalize this a bit--hopefully this framework will help us determine a method for solving the problem.
A markov model is basically just a weighted digraph. Thus, we can adopt a language similar to that used to describe finite state machines.
In your case, since a markov model is a representation of a stochastic phenomenon, this is a non-deterministic finite state automata--as apposed to a deterministic one.
This is represented by a quintuple of sets / variables / mappings as so:
NFA = {Σ,Q,q0,Δ,F}
Where Σ is a set of possible inputs (an "alphabet" if you will)
Q is a set of states in your model
q0 is the initial state
F is a set of final states (improper subset of Q or possibly null)
and Δ is a transition function that maps Σ × Q → P(Q) (the cartesian product of the alphabet Σ and the states Q onto the power set of Q)
In this situation, however, we must adapt the transition function to contain the weights as well.
so now Δ: Σ × Q → P(Q) × C | C ∈ ℜ1 ∧ 0 ≤ C ≤ 1
What we would like to do is to determine the transition function Δ.
The real number C for a given state is a probability. That probability is the weight on the graph, and, by definition, is given by the number of occurrences of the functions range in question divided by the number of occurrences of all elements in the range in one period of the function.
You have a generating function T(S,N,c0,c1,c2) whose domain is the cartesian product of these 5 independent variables, and whose range is some subset of the real numbers.
In order to convert your generating function into a probability, we will need the inverse operation T-1.
The number of solutions for T-1 in S, for some T(S) == k, divided by the total number of solutions for T-1 in S, ∀S, provides the probability of T(S,.,...) = i.
Since your function contains both a summation and modular arithmetic, finding an inverse will be a bit tricky. But with some clever thought to how each of these operations and moduli affect the cardinality of the solution spaces, it should be analytically solvable.
Frankly, for most things like this with a small space, it is going to be faster to write yourself a script in an easy language such as PERL or Python to simply count up all the sets and write out the calculated probabilities. But hopefully that should all get you started with whichever way you choose to solve the problem.
Report
10/16/13
Basma M.
Thank you sir for your help
Report
10/17/13
Basma M.
time to reply to my question, then,
I would like to use this equation to determine one expression
represents the transition probability in a markov chain to different states which
are the range of values generated by this equation. This expression of course
will be used to derive other expressions through the chain.
The given and the function you asked for if they correct or
not are correct. The variables and the chain are discrete and the probability
of having an element of the equation output range should be a general
expression gives the correct output with different S values, this for each n∈{k:1≤k≤N ∧ k∈Z+}.
Respectfully.
10/15/13