Following theorem is the first theorem in Lajos Takacs article "On Combinatorial methods in the theory of stochastic processes"

Theorem 1: Let $\phi(u), 0\leq u<\infty$, be a nondecreasing step function satisfying the conditions $\phi(0)=0$ and $\phi(t+u)=\phi(t)+\phi(u)$ for $u \geqslant 0$ where $t$ is a finite positive number. Define

\begin{equation} \delta(u)= \begin{cases} 1 & \text{if } v-\phi(v)\geq u-\phi(u)\text{ for }v\geq u,\\ 0 & \text{otherwise. } \end{cases} \end{equation}


\begin{equation} \int_{0}^{t}\delta(u)du= \begin{cases} t-\phi(t) & \text{if } 0\leq \phi(t)\leq t,\\ 0 & \text{if } \phi(t)\geq t. \end{cases} \end{equation}

The proof of this theorem starts with the following statement: "If $\phi(t)>t$ then $\delta(u)=0$ for every $u$ and thus the theorem is obviously true."

I disagree with this statement and the counterexample is: Let $t=1$ and

\begin{equation} \phi(u)= \begin{cases} 0 & \text{if } 0\leq u < \frac{1}{3},\\ 2 & \text{if } \frac{1}{3}\leq u\leq 1.\\ \end{cases} \end{equation}

\begin{equation} u - \phi(u)= \begin{cases} u & \text{if } 0\leq u < \frac{1}{3},\\ u - 2 & \text{if } \frac{1}{3}\leq u\leq 1.\\ \end{cases} \end{equation}

Obviously $t-\phi(t)=1-\phi(1)<0.$ and $\min_{0\leq u \leq 1}(u-\phi(u))=\frac{1}{3}-\phi(\frac{1}{3})=-\frac{5}{3}$. Moreover

\begin{equation} \delta(u)= \begin{cases} 0 & \text{if } 0\leq u< \frac{1}{3},\\ 1 & \text{if } \frac{1}{3}\leq u\leq 1.\\ \end{cases} \end{equation}

which is a contradiction with the fact that $\delta(u)=0$ for every $u$.

I have done a lot of drawings. To be more precise - if I draw the $u-\phi(u)$ function I obtained function which is negative and increasing in the interval $[\frac{1}{3},1]$. The most important is the fact, that at $u=\frac{1}{3}$ function $u-\phi(u)$ attains its global minimum. From this and the definition of $\delta$ function it should be the case that $\delta=1$ in this interval.

Please explain to me this statement and find where my reasoning in wrong?


2 Answers 2


I think you're misunderstanding the definition of $\delta$ (to be fair, it is a bit ambiguous). To make it more clear, $\begin{equation} \delta(u)= \begin{cases} 1 & \text{if } v-\phi(v)\geq u-\phi(u)\text{ for }\mathbf{all\,} v\geq u,\\ 0 & \text{otherwise. } \end{cases} \end{equation} $

Your example then isn't a counter-example since with $v=u+1$, you have $v-\phi(v)=u+1-\phi(1+u)=(u-\phi(u))+(1-\phi(1))<u-\phi(u)$. So with $v=u+1\ge u$, you can see that $\delta(u)=0$.

As to how I found this out, I looked at the second paragraph of the proof in the Takacs paper (not relevant for this case, but it offers illumination on the definition):

Now consider the case $0 \le \phi(t) \le t$. For $u \ge 0$ define $\psi(u)=\inf\{v-\phi(v)\text{ for }v\ge u\}$. We have $\psi(u)\le u-\phi(u)$, and $\psi(u)=u-\phi(u)$ if and only if $\delta(u)=1$.

There's no reason for $\psi(u)=u-\phi(u)\iff \delta(u)=1$ unless the definition of $\delta(u)$ had the "for all" $v\ge u$ (not just "for some" $v\ge u$).

  • $\begingroup$ So If I am get it right - in my example $u-\phi(u)\to-\infty$ if $u\to \infty$? $\endgroup$
    – Darek
    Mar 18, 2023 at 8:47
  • $\begingroup$ Yeah that’s right. For large $u$, $\phi(u)\sim \phi(t)\cdot u/t$, so in your example, $\phi(u)\sim 2u$. $\endgroup$ Mar 19, 2023 at 16:36

Your counterexample does not satisfy the constraint $\phi(u+v) = \phi(u) + \phi(v)$. Take $u = 0.4, v = 0.5$. Then in our counterexample, $\phi(0.9) = 2 \neq \phi(0.4) + \phi(0.5) = 4$.

  • 1
    $\begingroup$ Not for all $u$ i $v$. Look at the statement of the theorem: $\phi(t+u)=\phi(t)+\phi(u)$. In my counterexample $\phi(1+u)=\phi(1)+\phi(u)$ and everything works fine. $\endgroup$
    – Darek
    Mar 14, 2023 at 20:12
  • 1
    $\begingroup$ $\phi$ is completely determined by the values in the interval $[0,t]$. In my counterexaple this interval is $[0,1]$. $\endgroup$
    – Darek
    Mar 14, 2023 at 20:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .