In "Utility Optimal Scheduling in Processing Networks" by Michael J. Neely et al an example of processing network is provided. There are three queues ($q_1,q_2,q_3$) in the network and two processors ($P_1,P_2$). Both of the processors can be activated simultaneously. The pictorial representation of the network is shown below.
In this figure $R_1(t), R_2(t)$ are the input data streams to queue $q_1$ and $q_2$ respectively and can assume values $1$ or $0$ with equal probabilities at any $t$. Any input value at instant $t$ is admitted to $q_1 (q_2)$ if $D_1 (D_2)$ is $1$ and is rejected if $D_1 (D_2)$ is $0$. The acceptance of one data unit incurs a cost of 1. Processor $P_1$ is activated only when both $q_1$ and $q_2$ are nonempty. If the processor $P_1$ is activated then it receives one unit of data from both $q_1$ and $q_2$ and process it and produce a fused data unit. This fused data unit needs further processing which is done by $P_2$ if it is active. $P_3$ is made active only when $q_3$ is nonempty. After processing, the $P_2$ sends one unit of data at the out put which generates profit of $1$ or $3$ with equal probability. The instantaneous utility of the network is given by following equation $$f(t)=p(t)I_2(t)-D_1(t)R_1(t)-D_2(t)R_2(t)$$ where $I_2(t)$ can take a value of $1 (0)$ depending on the activation of $P_2$ i.e. if at instant $t$ $P_2$ is active then $I_2=1$ at that instant and vice versa. I want to find the average optimal utility of the network given the current state of $q_1,q_2,q_3$. Mathematically, I want to find $$E\{f(t)|q_1(t),q_2(t),q_3(t)\}.$$ The answer provided by the authors is $1/2$. I do not know how to get to this answer. I will be very thankful if somebody can help me in getting there. I have written below my strategy
My Strategy: Find the conditional expectation of $f(t)$ with respect to $p(t)$ first then find the conditional expectation of the answer with respect to other variables namely, $D_1(t), D_2(t), R_1(t), R_2(t)$. As described above the pmf of $R_1(t)$ and $R_2(t)$ are known however I do not know the pmf of $D_1(t), D_2(t)$. Hence I think there is some other way through which we can reach to the above answer.
Thanks in advance.
The notation seems to change somewhat between arxiv versions and journal version. My guess is that the "1/2" is a typo. I agree that example should have been more clearly explained.
The idea is to compare to an optimal randomized stationary algorithm, which is one that makes decisions without using queue backlog. It would have been nice for the paper to say what that randomized algorithm is. Lets assume $p(t) \in \{1, 4\}$ equally likely, as in the journal version. To me, it looks like an optimal algorithm is:
1) Drop nothing. So $D_1(t)=D_2(t)=1$, deterministically.
2) Use $I_1^*(t) \in \{0,1\}$ equally likely, so $E[I_1^*(t)]=1/2$.
3) Use $I_2^*(t)= 1$ if $p(t)=4$, else choose $I_2^*(t)=0$.
Then $E[I_1^*(t)]=E[I_2^*(t)]=1/2$ and $E[p(t)I_2^*(t)]=2$.
So $E[f^*(t)]=2 - 1/2 -1/2 = 1$.
I think this is optimal so $f^*=1$, not $f^*=1/2$ as stated.
Since these randomized stationary algorithms are independent of queue, we get $E[f(t)|Q(t)]=E[f(t)]$.