2
$\begingroup$

This question is about requesting some applicable algorithm rather than mathematical idea and is not part of any homework or study project. The solution may be obvious, but I can't see it by myself.

Suppose you have a data of time and some possible events (stock prices, number of trading assets, volume of liquid through a pipe, number of people somehow -- whatever you wish) represented by a table such that this possible events somehow depend on each other. For example, suppose you a purchaser with some limited amount of money and data on a table represents possible value of offers from supplies. Then it is clear then the more you buy in the beginning the less you will be able to buy in a future because of possibility to run out of money. Or suppose you a trader in a stock market, who buy stock if he has no one and sell otherwise -- the situation is the same.

My question is how can I algorithmically determine an expected mean value from such kind of data when I have no strategy and going to do things randomly? The problem at my point of view is that even for a $50$ rows table there would be $2^{50} = 1125899906842624$ possibilities of my behavior. On the other hand, I believe that this problem may naturally appear in many areas of applied mathematics in industry, so people somehow already solved it for a much bigger amount of data.

I am expecting that anyone will provide and explain for me an algorithm which will avoid considerating $2^n$ possible pathes for $n$ rows table. Any ideas will be very appreciative.

UPDATE: Let me clarify my problem in a simple example. Suppose that you have a list of ten elements, for example, let it be $\{14,15,8,6,7,3,19,25,9,15\}$. You pick the first element and then toss a fair coin: tail corresponds to the case when you pick second, and in case of head you do nothing. The expected value after such two steps is $Ex_2=0.5\cdot(14+0)+0.5\cdot(14+15)=\frac{43}{2}$. You repeat such procedure on each step, namely, after third we obtain $$Ex_3=0.25\cdot(14+0+0)+0.25\cdot(14+0+8)+0.25\cdot(14+15+0)+0.25\cdot(14+15+8)=\frac{51}{2},$$ and so on. $Ex_n$ (expected mean value after $n$ steps) is given by a sum of $2^{n-1}$ summands that increases very quickly with increasing $n$. I'm interested is there a simple way to solve that kind of problem for any reasonable $n$ (say $50$ or $100$) without brute force calculation of all possible cases? This is a very simple explanation in one toy problem what I'm seeking for.

$\endgroup$
2
$\begingroup$

Your goal is unclear; perhaps it is to get a rough idea what a typical value in a non-random sequence might be.

Your observations are not necessarily independent. It seems you may be trying to induce something like independence by choosing at random which of, say $n = 50$ observations to include in your average. You cannot really achieve randomness by haphazard behavior.

The first thing to do might be to check whether there are noticeable autocorrelations among your observations. Given a sequence $X_1, X_2, \dots, X_{50},$ the autocorrelation of lag $k = 2$ is roughly speaking the correlation of the sequences $X_1, X_2, \dots, X_{48}$ and $X_3, X_4, \dots, X_{50}.$

I say roughly speaking because, in computing the autocorrelation $r_k$ the the means of both (partial) sequences are taken to be the sample mean $\bar X$ of all 50 observations, and their standard deviations are taken to be the sample standard deviation $S$ of all 50. [For details of the definition, see this page from NIST, although the application illustrated is different from yours.]

The autocorrelation function (ACF) shows autocorrelations of several different lags. Below is a sequence of 50 observations, along with its ACF from R statistical software. (Numbers in brackets show the index of the first observation on each line.)

x
# [1] 100.0  99.1  98.4  97.3  98.0  98.7  98.8 100.1  99.8  98.0
#[11]  98.0  97.2  96.7  96.1  97.6  96.6  97.4  96.7  96.5  97.7
#[21]  98.2  98.3  98.7  97.7  98.8  98.5  97.3  96.7  96.6  94.6
#[31]  94.4  93.9  94.8  96.3  96.4  95.8  97.5  97.3  95.7  94.3
#[41]  96.1  96.7  95.2  95.3  94.9  95.5  95.7  95.5  97.1  96.2
acf(x)

enter image description here

The first autocorrelation here is of lag $0,$ so it is $r_0 = 1.$ Autocorrelations within the dotted bands are deemed not significant. So for my $X$-sequence of $n=50$ the autocorrelation can be said to "disappear" after four observations in sequence.

Thus, if we 'thin' the data by taking every fifth observations, we should have a nearly independent sequence. It's sample mean is $97.18.$

thin = seq(1,50, by=5);  thin
# [1]  1  6 11 16 21 26 31 36 41 46
xt = x[thin];  xt
# [1] 100.0  98.7  98.0  96.6  98.2  98.5  94.4  95.8  96.1  95.5
mean(xt)
# [1] 97.18

This kind of 'thinning' is used in Markov Chain Monte Carlo (MCMC) simulation, in order to get 'nearly-independent' observations from a simulated sequence that is known not to be independent.

acf(xt)

enter image description here

Notice that the thinned sequence shows no significant autocorrelation for lags $1, 2, \dots, 9.$

Addendum (per Comments): For large samples, if you want to allow for variability (not possible correlation) among your observations, the traditional method would be to look at a confidence interval of the form $\bar X \pm 2S/\sqrt{n},$ where $S$ is the sample standard deviation. This is based on the idea that the data are roughly normally distributed.

Some sort of re-sampling scheme as in bootstrapping could be used if you are unsure of the population distribution, and do not consider the assumption of independence to be too far-fetched. Take a large number of re-samples of size $n$ with replacement from among the $X_i$, and look at the average of the re-sample averages. For data in your example, this can be done in R statistical software as follows:

x = c(14,15,8,6,7,3,19,25,9,15)
n = length(x);  m = 10^6
a = replicate(m,  mean(sample(x, n, repl=T)))
mean(a);  sd(a)  
## 12.09754    # close to sample mean of the X's
## 2.015966    # close to their sample SD.

If you prefer some sort of arbitrary 'thinning' then you could re-sample perhaps a third (shown below) or a fourth of your data without replacement at each step:

x = c(14,15,8,6,7,3,19,25,9,15)
n = round(length(x)/3);  m = 10^6
a = replicate(m,  mean(sample(x, n)))
mean(a);  sd(a)  
## 12.09607
## 3.248168   # a little larger because of smaller re-samples

Overall, my first answer using ACF to decide how to thin is a method that has been used successfully in a vaguely related situation. It is still my recommended method.

By contrast, my two re-sampling schemes are untried methods in this context and you would have to use them with caution until you have tried them on actual data to see their effect. I regret that I cannot see how your proposed method makes sense as an average--or even how it provides a reasonable way to compensate for correlated data.

$\endgroup$
  • 1
    $\begingroup$ Thank you for such a detailed answer! I worked through it and appreciate your effort. I'm going to update my post with one toy problem to clarify my question. $\endgroup$ – Hasek Jul 8 '17 at 21:38
  • $\begingroup$ Thanks for the update: It seems to me you always want to include $X_i$ and then each of the other $X_i$s with probability $1/2.$ For 2 terms you have $14 + 15/2 = 21.5;$ for 3 terms, $15 + (15+8)/2 = 25.5.$ This is not really an 'average' because (for positive $X_i$) the result will increase with the number of terms included. // Maybe it would make more sense to do some kind of re-sampling algorithm: sample at random with replacement from among all $n$ values, then average the values sampled. Something like that is used in bootstrapping. See my addendum to come soon. $\endgroup$ – BruceET Jul 9 '17 at 18:54
1
$\begingroup$

I will assume that you have a stream of data, so you don't know what could come next.

If what you want is to predict things before they even happen relying on past events, then you are looking for an artificial intelligence algorithm.

Or, if you want to maintain the mean value of a stream of data, you can just store its sum and divide it by the corresponding size of the list.

Example:

We have the list: $1, 5, -2, 3, 6, -1$ And compute:

$1 / 1 = 1$

$6 / 2 = 3$

$4 / 3 = 1.333...$

$7 / 4 = 1.75$

$13 / 5 = 2.6$

$12 / 6 = 2$

$\endgroup$
  • 1
    $\begingroup$ Let me clarify my needs on your example with a list $\{1,5,-2,3,6,-1\}$. Suppose that any time you can either pick the next value from the list, or do nothing with it. For example, you definitely choose $1$ and then you are able to choose $5$ again or drop it, then the expected value after two steps is $EX=0.5\cdot(1+5)+0.5\cdot1$, and so on. I'm interested in this case. $\endgroup$ – Hasek Jul 5 '17 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.