# 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 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

This is a hard problem, but I think you are going wrong early on. The median of the sum does not equal the sum of the medians for independent variables, even asymptotically. In your example you simulated from a distribution where the median < mean, but both are constant. Since the sum of means is asymptotically correct (central limit theorem), the sum of medians will be an underestimate.

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.

For your actual problem, I doubt there is a general analytic solution without some assumptions about the underlying distributions. If you can approximate your distributions with analytic expression with a tractable formula for the sum of two independent (?) random variables (e.g. Gamma distributions with the same scale parameter), then you can develop explicit solutions.

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$.

I'm not a statistician, so my answer might be a complete parody. Now, after I've warned you, I will make an attempt to answer. If I understand you correctly, it seems to me that you are talking about modeling stochastic processes. In that case, I think that estimating completion time for such processes can be done via survival analysis. The following example paper does just exactly that: http://www.ieor.berkeley.edu/~faridani/papers/csdm2011.pdf. Another paper, link to which follows, describes a somewhat different model and approach, but might be adapted and still applicable to your situation: http://webspn.hit.bme.hu/~arpi/publ/RACZ02h.pdf. Hope this helps.

• Thanks for interesting pointers, I was not aware of those. Unfortunately, they solve a bit different tasks. The first paper models the time for completing one unknown task, from data of completing known tasks. In my case all tasks are known, and there are observations for completing each task. So estimating time for one task is not an issue, its's a median of observations. The challenge is to estimate the time for a set of tasks, the paper does not consider that. The second paper is estimating a distribution given moments. In my case I do not know moments, and I need to estimate a moment.
– inzl
Aug 23 '14 at 15:51
• @inzl: You're welcome! Sorry that I couldn't be of more help, but, at least, we both (me, especially :-) learned something new. What about time series analysis (en.wikipedia.org/wiki/Time_series)? Have you checked that for appropriate approaches and/or methods? Just a guess. Aug 23 '14 at 15:59