Convergence of factory earnings

27 Views Asked by At

Let $0<a<1$, and let $n$ be a positive integer. We have a factory that can process jobs. Each day, a job arrives - the number of days it takes to complete the job is $1\leq i\leq n$ with probability $p_i$, where $\sum_{i=1}^np_i= 1$. Also, the value (per day) of the job is drawn from a distribution $F$ over $[0,1]$ which is independent of the job length.

If the job has value $v\geq a$ and the factory is free when it arrives, the factory takes the job, is busy for the next $i$ days (where $i$ is the job length), and earns $iv$ dollars. If there are $D$ days in total, let $M_D$ denote the expected amount of money earned per day.

Is it true that the sequence $\{M_D\}_{D=1}^N$ converges?

Intuitively, this should be true because we reach a sort of "stable state" when the amount of time is long enough. But how can we show this formally? Does it follow from some general result?

1

There are 1 best solutions below

2
On BEST ANSWER

First consider the average money made over days on which the factory is running. The fraction of the time that the factory spends on jobs of time $i$ is $\frac{i p_i}{\sum_{j=1}^n j p_j}$ (note that the probability that a job will be accepted is not dependent on how long it will take). For each such job the factory earns an average of $E[V \mid V \geq a]$ money, with each value being independent of the rest. So the average earnings per day for jobs of length $i$ is $\frac{E[V \mid V \geq a]}{i}$. Multiplying that by the probability that we are working on a job of length $i$ on a given day gives $\frac{E[V \mid V \geq a] p_i}{\sum_j j p_j}$. We then sum that over $i$ to get $\frac{E[V \mid V \geq a]}{\sum_j j p_j}$.

Now we just multiply that by the probability that the factory is running on any given day. I conjecture that will just be $\frac{\sum_i i p_i}{\left ( \frac{1}{P(V \geq a)} - 1 \right ) + \sum_j j p_j}$, i.e. the average time of a job divided by the average time of a job plus the average time in between jobs. Try to prove or disprove that.

This gives you the "ensemble" average of the earnings per day; you'll need some kind of a strong law of large numbers to ensure that the time average converges to this.