# Estimating the time for completing a sequence of actions

In short: suppose I have observations for times taken to do some action. I want to estimate, how long will it take to complete a sequence of actions. The estimate should minimize the mean absolute error (L1 norm).

===

Details: I have observations for positive, non-identically distributed RV $x_i$, it can be assumed that RV are independent. I am interested in $y = \sum_{i=1}^n x_i$. For example, $x_i$ can be the time for action $i$, and $y$ the time for completing a sequence of actions. I would like to find an estimate $\hat{y}$ that would minimize the mean absolute error (L1 norm). So I need to estimate $\mathit{median}(y)$.

For $n = 1$ the estimate is straightforward $\hat{y} = \mathit{median}(x_1)$.

For large $n$ I have observed that $\hat{y} = \sum_{i=1}^n \mathit{mean}(x_i)$ gives a reasonably good estimate. I suppose this is explained by the Central Limit Theorem: for large $n$, $y$ approaches the normal distribution, thus $\mathit{median}(y) \approx \mathit{mean}(y)$, and $\mathit{mean}(\sum_{i=1}^n x_i) = \sum_{i=1}^n mean(x_i)$.

Question: Is there any analytical solution for approximating median of the sum of independent non identically distributed RV for small $n$, i.e. for approximating $\mathit{median}(y)$ for small $n$ in this context?

Practically, in the data $n$ is distributed: $n=1$ ($10\%$), $n=2$ ($20\%$), $n=3\ldots 5$ ($20\%$), $n=6\ldots 10$ ($10\%$), and $n>10$ ($40\%$), maximum $n$ is $70$.

===

So far my solution is as follows. I assume that that $\hat{y} = \sum_{i=1}^n \big((1-w)*\mathit{median}(x_i) + w*\mathit{mean}(x_i)\big)$, where $w \in [0,1]$ is a weight. When $n=1$, $w=0$. When $n\rightarrow \infty$, $w \rightarrow 1$. Then I model $w$ as a function of $n$.

I estimate an empirical distribution of all observations (ignoring that the variables are non identically distributed), generate synthetic data from that distribution. On that data I learn $w = f(n)$ using some machine learning approach, e.g. ANN.

The data is generated as follows. I sample $n$ uniformly at random. I compute the true $\mathit{median}(y)$. I let $w$ run from $0$ to $1$ and pick $w$ that gives the minimum absolute deviation of $\hat{y} = \sum_{i=1}^n \big((1-w)*\mathit{median}(x_i) + w*\mathit{mean}(x_i)\big)$ from $\mathit{median}(y)$. This gives me one data point. I generate, say 10000 such data points and learn a function on this data.

This gives a slight improvement over simply using $w=0$ or $w=1$ for all $n$, but not much, and not always.

===

And finally, to illustrate my intuition that there may exist a nice functional form of $w$, here is an example of $w = f(n)$ learned on synthetic data sampled from log-normal distribution $ln {\cal N}(0,s)$. Solid lines denote estimated functions, circles denote out-of-sample test data.

• That's a really clever approach and this is a really interesting problem. Wikipedia has a blurb on median-unbiased estimators, for what it's worth: en.wikipedia.org/wiki/Median#Median-unbiased_estimators – shadowtalker Aug 22 '14 at 4:23
• I am really confused about what the data look like. The problem describes $n$ random variables $x_i$ but later talks about a distribution of $n$, as if the number of random variables were itself a random variable. Could you perhaps provide a small illustration or amplify your description of the data? – whuber Aug 22 '14 at 15:03
• For example, suppose we have tasks A,B,C,D. Person #1 completes tasks A+C+D in 5+6+3 min respectively. Person #2 completes tasks B+A in 7+6 min. Person #3 completes tasks C+D+B in 4+5+4 min. Person #4 completes task A in 4 min. Estimate, how long IN TOTAL will it take for person #5 to complete B+C. – inzl Aug 23 '14 at 15:25

In fact, the independence is a problem for you. If you could assume an underlying "skill" for each subject, so that they always perform in the same percentile of every task, then I think the sum of medians would equal the median of the sum. In practical applications the truth is probably somewhere in-between, so the sum of medians is not horrible, but statistically it is a bad estimate. It is biased (if $n>1$), not consistent (does not converge to the true value even for large $n$), and it is difficult to handle analytically.
You might also consider "learning" the speed of convergence of the sums of your distributions to the normal. You will have to make some assumptions about them: members of a scale or shift family, correlation, etc for the simulations. I think the individual medians are highly misleading, you could just try estimates of the form $w \cdot mean$, with $w \rightarrow 1$.