Estimating result of an iterative operation involving random number

[jarhead70]

Hi,

Suppose there's an operation like the following:

x(t) = x(t-1) + rand(m..n)

with
x(t) = current value
x(t-1) = previous value
rand(m..n) = equally distributed random real number in the range of m and n

is there a way to estimate the value of x(t) after Y iteration without actually doing the iteration Y times, assuming Y is larger than 1000?

Thanks

 

[MarkFL]

l would think that for a large number of iterations, we could reasonably approximate the solution with:

\(\displaystyle x(t)\approx x(0)+t\frac{m+n}{2}\)

In other words, there should be about as many values above the arithmetic mean of the range of random numbers as below.

edit: I ran some simulations, with $x(0)=0,\,m=1,\,n=9$:

$Y$	Estimate	Actual
1000	5000	4952.42945031
10000	50000	50297.7891738
100000	500000	499801.102515
1000000	5000000	5000437.34467

 

[jarhead70]

l would think that for a large number of iterations, we could reasonably approximate the solution with:

\(\displaystyle x(t)\approx x(0)+t\frac{m+n}{2}\)

In other words, there should be about as many values above the arithmetic mean of the range of random numbers as below.

edit: I ran some simulations, with $x(0)=0,\,m=1,\,n=9$:
...

Thanks for your reply.

However, your solution fails when the range of the random variable is $-m \le r \le m$

Sample simulations:
$x(0)=0,\,m=-1,\,n=1$

$Y$	Estimate	Actual
1000	0.0	-12.91132354196654
10000	0.0	88.76996209606638
100000	0.0	-214.62703168619245
1000000	0.0	158.93316829030073

$x(0)=0,\,m=-9,\,n=9$

$Y$	Estimate	Actual
1000	0.0	-28.623493620088897
10000	0.0	-504.7370383329392
100000	0.0	412.8417707372953
1000000	0.0	2313.431324375944

For other random variable ranges, your solution does give an acceptable estimate. Are there a way to make the solution more general, or does the above case require special handling?

Thanks

 

[MarkFL]

I think the absolute difference between the estimate and actual values will be comparable, it just looks worse when the estimate is small.

 

[jarhead70]

I think the absolute difference between the estimate and actual values will be comparable, it just looks worse when the estimate is small.

Just making sure I'm getting it right, if error is defined as the absolute difference between the estimate value and the actual value (the result of doing the actual iterations), the error will become larger as the estimate value become smaller, or put it another way, error is inversely related to estimate value. Is this right?

And from my sample simulation, is it also safe to say that in addition to error being inversely related to estimate value, it is also linearly related to the number of iterations?

Thanks for your illuminating post, but unfortunately after re-examining the codes it seemed that I slightly misunderstood the problem. While the underlying operation is still the same, there's another detail of the operation that I miss.

The actual code for each iteration is the following:

$n = x_{t-1} \times k, (k \in real, 0 \le k \le 1)$
$m = -n$
$x_t = x_{t-1} + rand(m..n)$

The only thing immutable in each iteration is $k$. As you can see, the random value range change in each iteration, cos $x_t$ from previous iteration become $x_{t-1}$ in the current one.

Does the estimate solution still hold in this case?

Thanks
PS: the sample simulation I posted earlier was using the original operation, the one without variable $k$ introduced

 

[MarkFL]

The error should only vary linearly with the number of iterations, and with the difference between $m$ and $n$, and not depend on the estimate. I have run a series of simulations with 100000 iterations each, where in one we have $(m,n)=(1,9)$ and another where $(m,n)=(-4,4)$. So, in the first case, our estimate is 500000, while in the second case our estimate is 0:

Trial	Value 1	Error 1	Value 2	Error 2
1	499400.521646	599.478354153	478.231223299	478.231223299
2	500512.517299	512.517299246	184.730949398	184.730949398
3	499101.401411	898.598589477	382.213193408	382.213193408
4	499573.912897	426.087102908	1750.90938973	1750.90938973
5	499045.029516	954.970484013	-36.4236090278	36.4236090278
6	499662.20499	337.795009887	-1261.48426344	1261.48426344
7	499133.838544	866.16145649	-337.858854127	337.858854127
8	499269.888445	730.111554581	-2670.99289262	2670.99289262
9	500014.594257	14.5942568078	78.3711088367	78.3711088367
10	499827.472268	172.527732044	-948.894046287	948.894046287

In the new recursion, because the mean of $m$ and $n$ is always the same (zero), I would say a good estimate would be:

\(\displaystyle x(t)\approx x(0)\)

 

[jarhead70]

The error should only vary linearly with the number of iterations, and with the difference between $m$ and $n$, and not depend on the estimate. I have run a series of simulations with 100000 iterations each, where in one we have $(m,n)=(1,9)$ and another where $(m,n)=(-4,4)$. So, in the first case, our estimate is 500000, while in the second case our estimate is 0:
...
In the new recursion, because the mean of $m$ and $n$ is always the same (zero), I would say a good estimate would be:

\(\displaystyle x(t)\approx x(0)\)

Thanks very much for your help in this.

The original purpose of my question is to optimize a hobbyist simulation engine I'm tweaking. The original engine has several hundred of such iterative operations done in each frame, each with their own set of parameters. I am trying to reduce the workload of each frame.

I figure, if there's a way to simulate the result of the iterative with one operation, then instead of doing millions of iterations per frame, I can get away with doing several hundred instead.

On average, the number of iterations of each operations in one frame is roughly 10000. Seeing the simulation result, the error can get very large. So I'm considering these steps to "improve" the estimate:

1. Run simulations using your equation a large number of times for one set of parameters, then calculate the mean and standard deviation of the absolute error
2. Run #1 for another set of parameters, differ incrementally from the one used in #1, and again calculate the mean and standard deviation. This will give a set of mean and standard deviation
3. Calculate linear regression parameters for mean and standard deviation data from #2

After getting the regression parameters for mean and standard deviation of the errors, the engine will estimate the operation at runtime by

1. Get the estimate for a parameter set using your equation
2. Use the same parameters to choose a mean and standard deviation using the regression parameters calculated before
3. Use the mean and standard deviation calculated in #2 to generate a number using a random number generator with gaussian distribution
4. Add the result from #1 with the result from #3 to give the final estimate

Please tell me what you think of such approach.

Thanks

 

[MarkFL]

Just off the top of my head, it would seem that you could simply use for your estimate a random number (with gaussian or normal distribution) where the mean is the estimate we have been using and make it so that 6 sigmas above and below this mean are the bounds.

I would encourage you to try your method first, see what you get, and let us know if this works well for you. :)