# Theorem concerning step function

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

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

Then

$$$$\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}$$$$

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

$$$$\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}$$$$

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

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

$$$$\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}$$$$

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?

I think you're misunderstanding the definition of $$\delta$$ (to be fair, it is a bit ambiguous). To make it more clear, $$$$\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}$$$$

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

• So If I am get it right - in my example $u-\phi(u)\to-\infty$ if $u\to \infty$? Mar 18, 2023 at 8:47
• Yeah that’s right. For large $u$, $\phi(u)\sim \phi(t)\cdot u/t$, so in your example, $\phi(u)\sim 2u$. 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$$.

• 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. Mar 14, 2023 at 20:12
• $\phi$ is completely determined by the values in the interval $[0,t]$. In my counterexaple this interval is $[0,1]$. Mar 14, 2023 at 20:25