Iwr-: 03493 RR259

RIA
laboria

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

TWO COUPLED PROCESSORS:
THE REDUCTION TO
A RIEMANN-HILBERT PROBLEM

Guy FAYOLLE
Roudolf IASNOGORODSKI

Rapport de Recherche N° 259

Novembre 1977

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20
TWO COUPLED PROCESSORS : THE REDUCTION TO A
RIEMANN-HILBERT PROBLEM

Guy Fayolle*, Roudolf Iasnogorodski**

Résumé :

Beaucoup de problèmes liés au couplage de processeurs conduisent à des équations fonctionnelles. En général, les fonctions inconnues représentent les fonctions génératrices d'un processus stationnaire. Nous étudions ici un problème particulier, mais la méthode proposée est applicable à des cas très généraux de marches aléatoires à deux dimensions.

Abstract :

Many problems arising from the coupling of processors require the solution of functional equa-
tions. Generally, the unknown functions are the generating functions for a stationary distribution
of the studied process. In this paper, a particular problem is addressed but results lead to a compu-
tationally reasonable solution which applies to very general two dimensional random walks.

<footnote>* IRIA/LABORIA, Rocquencourt (France)</footnote>

<footnote>** Université d'Orléans (France)</footnote>
# TWO COUPLED PROCESSORS: THE REDUCTION TO A RIEMANN-HILBERT PROBLEM

## INTRODUCTION

Many problems arising from the coupling of processors [or, dualistically, from the sharing of one resource by several classes of customers] require the solution of functional equations. Generally, the unknown functions are the generating functions for a stationary distribution of the studied process. In this paper, a particular problem is addressed but results lead to a computationally reasonable solution which applies to very general two-dimensional random walks.

In the first five sections, we describe the problem of coupling and show that the generating function $F(x,y)$ [for the joint distribution of the Markov process associate with the number of jobs in both queues] can be continued as a meromorphic function to the whole complex plane. [we do not need any uniformizing parameter as in [Flatto-MacKean-2] or in [Malyshev-5].

Section VI is devoted to a particular strategy proposed by [Coffman-Mitrani-1]: a processor sharing discipline only among the top jobs in each queue. This strategy is shown to "be complete" [Mitrani-Hine-8]. We reduce the problem to a Dirichlet problem and obtain closed formulas which include elliptic functions of the third kind.

Section VII treats a more general case, equivalent to a Riemann-Hilbert problem. Again, closed formulas are obtained.

In Section VIII, we give conditions under which the preceding procedures are efficient.
# I - PROBLEM FORMULATION AND ASSUMPTIONS

Let us consider two parallel M/M/1 queues with infinite capacities under the following assumptions.

a) The arrivals form two independent Poisson processes with parameters $\lambda_1, \lambda_2$.

b) The servers have exponential service time distributions with means $\frac{1}{S_1}$ and $\frac{1}{S_2}$ where :

i) $S_1 = \mu_1$ if both queues are busy
$S_2 = \mu_2$

ii) $S_1 = \mu_1^*$ if queue 2 is empty

iii) $S_2 = \mu_2^*$ if queue 1 is empty

c) The service discipline is FIFO (first in-first out) in each queue

Let $p_t(m, n)$ be the probability that, at time $t$, there are $m$ jobs in queue 1 and $n$ jobs in queue 2.

$p(m, n) = \lim_{t \to \infty} p_t(m, n)$ will be referred to as the stationary probability of the state $(m, n)$. We study the behaviour of the system at the steady state by means of the generating function $F(x, y)$ (see below).

From now on the terms "stability" or "ergodicity" will be used to mean "there exists a stationary distribution".

The Kolmogoroff forward equations for the $p(m, n)$ are the following

$$ (1.1) \left\{ \begin{array}{ll} (1.a) & (\lambda_1 + \lambda_2 + \mu_1 + \mu_2) p(m, n) = \lambda_1 p(m-1, n) + \lambda_2 p(m, n-1) \\ & \qquad + \mu_1 p(m+1, n) + \mu_2 p(m, n+1) & \quad m, n > 0 \\ (1.b) & (\lambda_1 + \lambda_2 + \mu_2^*) p(0, n) = \lambda_2 p(0, n-1) + \mu_1 p(1, n) + \mu_2^* p(0, n+1) & \quad m = 0, n > 0 \\ (1.c) & (\lambda_1 + \lambda_2 + \mu_1^*) p(m, 0) = \lambda_1 p(m-1, 0) + \mu_1^* p(m+1, 0) + \mu_2 p(m, 1) & \quad m > 0, b = 0 \\ (1.d) & (\lambda_1 + \lambda_2) p(0, 0) = \mu_1^* p(1, 0) + \mu_2^* p(0, 1) & \quad m = n = 0. \end{array} \right. $$
We introduce the generating functions.

$$
\begin{align*}
F(x, y) &= \sum_{m=0}^{\infty} \sum_{n=0}^{\infty} p(m, n) x^n y^n \\
G_n(y) &= \sum_{n=0}^{\infty} p(m, n) y^n \\
H_n(x) &= \sum_{m=0}^{\infty} p(m, n) x^n
\end{align*}
$$

which are analytic with respect to x and y whenever |x|, |y| < 1.

A straightforward but tedious computation

yields to

$$
(1.2) \quad \left[
\begin{aligned}
F(x, y) & [\lambda_1(1-x) + \mu_1(1-\frac{1}{x}) + \lambda_2(1-y) + \mu_2(1-\frac{1}{y})] = \\
F(0, y) & [\mu_1(1-\frac{1}{x}) + \mu_2(1-\frac{1}{y})] + F(x, 0) [\lambda_1(1-\frac{1}{y}) + \mu_1(1-\frac{1}{x})] \\
& \quad +F(0, 0) [\mu_2(1-\frac{1}{x}) + \mu_1(1-\frac{1}{y})]
\end{aligned}
\right]
$$

$$
\begin{align*}
\text{where } p &= \mu_1 - \mu_1^* \\
q &= \mu_2 - \mu_2^*
\end{align*}
$$

The existence of F(x, y) satisfying the functional equation (1.2) with $\sum_{m+n=0}^{\infty} p(m, n) < \infty$
(space $L_1$) is equivalent to stability. Moreover if F(x, y) exists, it is unique
up to a constant multiplier which can be suitable chosen so that all coefficients
in the power series expansion are positive and sum to 1.

A glance at relation (1.2) does not give many information concerning
F(x, y),

However, a further investigation shows that the right side member vanishes
whenever

$$
\lambda_1(1-x) + \mu_1(1-\frac{1}{x}) + \lambda_2(1-y) + \mu_2(1-\frac{1}{y}) = 0, \text{provided } |x|, |y| \le 1
$$
To obtain additional relations between $F(x, 0)$ and $F(0, y)$, it is necessary to
examine carefully the algebraic curve $S$ defined by

$$ (1.3) \qquad R(x,y) \equiv xy[\lambda_1(1-x) + \mu_1(1-\frac{1}{x}) + \lambda_2(1-y) + \mu_2(1-\frac{1}{y})] = 0 $$

in the whole complex plane, what is done in the next section.

$$ \text{II} - R(x, y) = 0 $$

$R(x, y)$ is a polynomial of third degree w.r.t. $x$ and $y$ and of second degree w.r.t. each variable $s$ or $y$.

The curve $S$ has genus 1 and can be identified with the Riemann surface $S$ over either the extended $x$ or $y$ planes (more precisely, the algebraic extension of the field of rational functions of $x$, as defined by $R(x, y) = 0$).

These assertion are well known (see for example [Fuchs-3] and
will not be discussed further.

For curves of genus 1, the introduction of a uniformizing parameter requires elliptic functions and reduces the tractability of the computation if we try to construct the analytic continuation of the functions $F(x, 0)$ and $F(0, y)$ (for an example concerning a curve of genus 0, see [Flatto-Mac Kean-2]).

Solving $R(x, y)$ for $y$, we have

$$ (2.1) \qquad y(x) = \frac{\lambda_2 + \mu_2 + A(x) \mp \sqrt{(\lambda_2 + \mu_2 + A(x))^2 - 4\lambda_2\mu_2}}{2\lambda_2} $$

where

$$ (2.2) \qquad A(x) = \lambda_1(1-x) + \mu_1(1-\frac{1}{x}) $$

We obtain two distinct branches which give a two sheeted covering over the $x$ plane.
**Lemma 2.1** : The algebraic function $y(x)$ defined by $R(x, y)$ has four real branch points $x_1, x_2, x_3, x_4$ with $0 < x_1 < x_2 < 1 < x_3 < x_4$.

**Proof** : From (2.1), it follows that branch points are the roots of the discriminant

$$ \Delta(x) = [\lambda_2 + \mu_2 + A(x)]^2 - 4\lambda_2\mu_2 $$

This can be written

$$ A(x) + (\sqrt{\lambda_2} \mp \sqrt{\mu_2})^2 = 0 $$

or (2.3) $$ \lambda_1 x^2 + \mu_1 = (\Sigma + k)x $$

where $$ \Sigma = \lambda_1 + \lambda_2 + \mu_1 + \mu_2 $$

$$ k = (\sqrt{\lambda_2} \mp \sqrt{\mu_2})^2 $$

Obviously, the roots of (6) are real, positive. Moreover $\lambda_1 + \mu_1 < \Sigma + k$.

It follows that 1 lies between these roots. As $k$ takes two values $(\sqrt{\lambda_2} + \sqrt{\mu_2})^2$ and $(\sqrt{\lambda_2} - \sqrt{\mu_2})^2$, $\Delta(x)$ vanishes for $x = x_1, x_2, x_3, x_4$ with $x_1 < x_2 < 1 < x_3 < x_4$.

Verifying that

$$ x(S) = \frac{\lambda_1 + \mu_1 + S - \sqrt{\lambda_1 + \mu_1 + S})^2 - 4\lambda_1\mu_1}{2\lambda_1} $$

is a decreasing function of $S$ for $S \ge 0$, yields

$$ (2.4) \quad \left\{ \begin{aligned} x_1 &= \frac{\lambda_1 + \mu_1 + (\sqrt{\lambda_2} + \sqrt{\mu_2})^2 - \sqrt{(\lambda_1 + \mu_1 + (\sqrt{\lambda_2} + \sqrt{\mu_2})^2)^2 - 4\lambda_1\mu_1}}{2\lambda_1} \\ x_2 &= \frac{\lambda_1 + \mu_1 + (\sqrt{\lambda_2} - \sqrt{\mu_2})^2 - \sqrt{(\lambda_1 + \mu_1 + (\sqrt{\lambda_2} - \sqrt{\mu_2})^2)^2 - 4\lambda_1\mu_1}}{2\lambda_1} \\ x_3 &= \frac{\mu_1}{\lambda_1 x_2} \\ x_4 &= \frac{\mu_1}{\lambda_1 x_1} \end{aligned} \right. $$
The Lemma II.1 is obviously valid for the branch points $y_1, y_2, y_3, y_4$ of the function $x(y)$.

**Lemma 2.2** : The equation $R(x, y) = 0$ has one root $y(x) = h(x)$ which is an analytic algebraic function of $x$ in the whole complex plane cut along the two segments $[x_1, x_2]$ and $[x_3, x_4]$.

Moreover $|h(x)| \le 1$ if $|x| = 1$

$$|h(x)| \le \sqrt{\frac{\mu_2}{\lambda_2}} \quad \forall x.$$

Similar propositions apply to $x(y)$ : i.e. there exists $k(y)$ such that

$$(k(y), y) = 0$$

$$|k(y)| \le 1 \quad \text{if} \quad |y| = 1$$

$$|k(y)| \le \sqrt{\frac{\mu_1}{\lambda_1}} \quad \forall y$$

**Proof** : The first part of the lemma results from the general theory of polynomials of two complex variables [Fuchs-3].

The second assertion is proved by using Rouché's theorem as follows :

$R(x, y) = 0$ is equivalent to

$$yx[\lambda_2+\mu_2+\lambda_1(1-x) + \mu_1(1-\frac{1}{x})] = [\lambda_2y^2+\mu_2] x$$

$$\text{When } |x| = 1, \quad |\lambda_2+\mu_2+A(x)| > \lambda_2+\mu_2 \\ x \ne 1$$

$A(x)$ given by (2.2).

Hence on the circle $|y| = 1$ we have

$$|xy| |\lambda_2+\mu_2+A(x)| = |\lambda_2+\mu_2+A(x)| > \lambda_2+\mu_2 \ge |x| |\lambda_2y^2+\mu_2|$$
We deduce that $R(x, y) = 0$ has exactly one root $k(x)$ inside the unit circle.

$$x = 1 \text{ yields } \left(\lambda_2 - \frac{\mu_2}{y}\right)(1-y) = 0$$

and $h(1) = \min(1, \frac{\mu_2}{\lambda_2})$.

The curve $H_1 = \{h(x), |x| = 1\}$ is simple and closed.

The region inside the circle $|x| = 1$ cut along the real axis from $x_1$ to $x_2$ is mapped by $h(x)$ onto the ring shaped region between the curve $H_1$ and the circle $|y| = \sqrt{\frac{\mu_2}{\lambda_2}}$.

Observing that $a(y) = \frac{\mu_2}{\lambda_2 y}$ is a conformal map (automorphism) of the Riemann surface onto itself $[R(x, a(y))= R(x, y)]$, we deduce the second root of $R(x, y) = 0$ is $\frac{\mu_2}{\lambda_2 h(x)}$.

The last assertion of the lemma is derived from the "maximum modulus principle" [Fuchs- 3] since

$$i) h(x) = h(\frac{\mu_1}{\lambda_1 x}) = 0 \text{ if } x = \infty$$

ii) $h(x)$ is analytic of $x$ in the whole complex plane cut along $[x_1 x_2] \cup [x_3 x_4]$.

Thus, the maximum modulus of $h(x)$ can be reached only on the boundary $[x_1 x_2] \cup [x_3 x_4]$.

$$\text{But } |h(x)| = \sqrt{\frac{\mu_2}{\lambda_2}} \text{ if } x \in [x_1 x_2] \cup [x_3 x_4].$$

**Remark** : Upon setting $y = \sqrt{\frac{\mu_2}{\lambda_2}} z$, we get $\lambda_2(1-y) + \mu_2(1 - \frac{1}{y}) = \lambda_2 + \mu_2 - \sqrt{\lambda_2 \mu_2}(z + \frac{1}{z})$.

Replacing $z$ by $\frac{1}{z}$, this expression is unaffected.

Therefore $h(x)$ is the root corresponding to $|z| \le 1$ and it follows at once $|h(x)| \le \sqrt{\frac{\mu_2}{\lambda_2}}$.
The proof of Lemma 2.2. is terminated.

$$ \text{Lemma 2.3 :} \qquad (2.5) \qquad \begin{cases} k(h(x)) = \begin{cases} x & \text{if } |x| > \sqrt{\frac{\mu_1}{\lambda_1}} \\ \frac{\mu_1}{\lambda_1} x & \text{if } |x| \le \sqrt{\frac{\mu_1}{\lambda_1}} \end{cases} \\ h(k(y)) = \begin{cases} y & \text{if } |y| > \sqrt{\frac{\mu_2}{\lambda_2}} \\ \frac{\mu_2}{\lambda_2} y & \text{if } |y| \le \sqrt{\frac{\mu_2}{\lambda_2}} \end{cases} \end{cases} $$

The proof is easily entailed by the arguments of Lemma 2.

It is important to note the strict inequalities in (2.5) : for example

$k(h(x)) = \frac{\mu_1}{\lambda_1 x}$ if $|x| > \sqrt{\frac{\mu_1}{\lambda_1}}$ because on the circle of radius $|x| = \sqrt{\frac{\mu_1}{\lambda_1}}$ there are two conjugate roots $k$ and $\bar{k} = \frac{\mu_1}{\lambda_1 k}$, but $k$ is reached from inside.

The proof is concluded.
### III - THE ANALYTIC CONTINUATION OF F(x,0) and F(0,y)

**Convention** : To avoid repetitions, we make the convention that, unless otherwise stated, $C(R)$ must be read "the circle of radius $R$ centered at the origin".

In section II, we have defined two curves

$$H = \{h(z) / |z| = 1\}$$

$$K = \{k(z) / |z| = 1\},$$

which are simple, closed and lie inside $C(1)$. Similarly, let $H$ and $K$ be the curves obtained from $H$ and $K$ under the mappings (automorphisms) $z \to \frac{\mu_2}{\lambda_1 z}$ and $z \to \frac{\mu_1}{\lambda_1 z}$ respectively.

$$H' = \frac{\mu_2}{\lambda_2 H}$$

$$K' = \frac{\mu_1}{\lambda_1 K}$$

$H'$ and $K'$ are also simple, closed and lie outside $C(1)$.

[The point $z=1$ on the positive real axis belongs to $H'$ (resp. $K'$) iff $\frac{\mu_2}{\lambda_2} < 1$) (resp. $\frac{\mu_1}{\lambda_1} < 1$) as shown in section II].

We shall use throughout this paper the functions $h(x)$ and $k(y)$ introduced in II.

### Theorem 3.1 :

1) $F(x,0)$ [resp. $F(0,y)$] can be continued as a meromorphic function to the whole complex plane out along the real axis from $x_3$ to $x_4$ [resp. from $y_3$ to $y_4$].
2) The poles of $F(x,0)$ [resp. $F(0,y)$] are the zeros (if any) of $\mu_2(1 - \frac{1}{h(x)}) + p(1 - \frac{1}{x})$ [resp. $\mu_1(1 - \frac{1}{k(y)}) + q(1 - \frac{1}{y})$] outside $C(1)$.

**Proof** : All the information known about $F(x, 0)$ and $F(0, y)$ is that there are analytic for $|x|, |y| \le 1$.

First of all we establish the

**Lemma 3.1** : All the couples $(x,y)$ which are solutions of the system

$$ (3.1) \quad \left\{ \begin{array}{ll} R(x,y) = 0 \\ |x| \le 1 \\ |y| \le 1 \end{array} \right. $$

have the form $(x, h(x))$ or $(k(y), y)$ where $x \in \mathbb{R}_+$ and $y \in \mathbb{R}_+$.

The demonstration follows at once from section II (assuming $\frac{\mu_1}{\lambda_1} > 1$):

$\mathbb{R}_+$ is the domain which lies between the curves $C(1)$ and $H$. $\mathbb{R}_-$ is the domain which lies

$$ \left\{ \begin{array}{ll} \text{between the curves } C(1) \text{ and } K & \text{if } \frac{\mu_1}{\lambda_1} > 1 \\ \text{inside } C(1) & \text{if } \frac{\mu_1}{\lambda_1} \le 1 \end{array} \right. $$

When $\frac{\mu_2}{\lambda_2} > 1$ there is a bijection between $\mathbb{R}_+$ and $\mathbb{R}_-$.

$$ \mathbb{R}_+ \xrightarrow{h} \mathbb{R}_- \text{ and } \mathbb{R}_- \xrightarrow{k} \mathbb{R}_+ $$

When $\frac{\mu_2}{\lambda_2} < 1$ there is a bijection between $\mathbb{D}_+$ and $\mathbb{D}_-$

where
$$ \left\{ \begin{array}{ll} \mathbb{D}_+ \text{ is the domain between the curves } C(1) \text{ and } K \\ \mathbb{D}_- \text{ is the domain between the curves } C(\sqrt{\frac{\mu_2}{\lambda_2}}) \text{ and } H. \end{array} \right. $$
The case $\frac{\mu_1}{\lambda_1} < 1, \frac{\mu_2}{\lambda_2} < 1$ is rejected : otherwise, as soon as both queues are busy, the queue lengths remain unbounded with positive probabilities $(1 - \frac{\mu_1}{\lambda_1}$ and $1 - \frac{\mu_2}{\lambda_2}$ respectively) [Cohen- 4].

**Remark :** From now on, and in the following sections too, it will be assumed
$\underline{\mu_1 > \lambda_1}$

We are in a position to demonstrate theorem 3.1. Upon setting

$$
(3.2) \quad \left\{
\begin{aligned}
a(x,y) &= \mu_1 \left(1 - \frac{1}{x}\right) + q \left(1 - \frac{1}{y}\right) \\
b(x,y) &= \mu_2 \left(1 - \frac{1}{y}\right) + p \left(1 - \frac{1}{x}\right) \\
c(x,y) &= p \left(\frac{1}{x} - 1\right) + q \left(\frac{1}{y} - 1\right),
\end{aligned}
\right.
$$

System (3.1) entails :

$$
(3.3) \quad \boxed{F(0,y) a(x,y) + F(x,0) b(x,y) + c(x,y) = 0}
$$

In (3.3) either $x = h(y)$ or $y = k(x)$.

$\overline{C(1)}$ will denote the region outside $C(1)$.

We continue the function F(x,0) to $\overline{C(1)}$.

Two cases must be distinguished.

$$
i) \quad \frac{\mu_2}{\lambda_2} < 1.
$$

$$
\text{Then } |h(x)| \le \sqrt{\frac{\mu_2}{\lambda_2}} \le 1 \quad \forall x.
$$
$F(0, h(x), a(x, h(x)))$ and $c(x, h(x))$ are analytic in $\overline{C(1)}$ cut along $[x_3, x_4]$.

The relation (3.3) entails the same property for the product $F(x,0) \cdot b(x, h(x))$. It follows that $F(x,0)$ can be continued as a meromorphic function to $\overline{C(1)} - [x_3, x_4]$, the poles of which are the zeros (if any) of $b(x, h(x)) = 0$ in $\overline{C(1)} - [x_3, x_4]$.

$$ \text{ii)} \quad \frac{\mu_2}{\lambda_2} > 1. $$

Let $\mathcal{K}'$ denote the region inside the curve $K'$, that is

$$ \begin{cases} |x| \ge 1 \\ |h(x)| \ge 1 \end{cases} $$

Note that $x_3$ and $x_4$ are interior points of $\mathcal{K}'$.

In $\overline{C(1)} - \mathcal{K}'$, $|h(x)| \le 1$ : the same argument as in i) holds and the product $F(x,0) \cdot b(x, h(x))$ is analytic.

The analytic continuation of $F(0,x)$ to $\mathcal{K}' - [x_3, x_4]$ is made according to the following procedure :

a) In (3.3), we use the fact that $F(x,0)$ is analytic inside $C(1)$ to continue $F(0,h(x))$ to $C(1) - [x_1, x_2]$ as in the foregoing lines.

b) On account of the automorphism $z \to \frac{\mu_1}{\lambda_1 z}$, we know that

$$ h\left(\frac{\mu_1}{\lambda_1 x}\right) = h(x) $$

$$ [x_3, x_4] = \frac{\lambda_1}{\mu_1 [x_2, x_1]} $$
Hence, $F(0,h(x))$ is continued as a meromorphic function to $\mathcal{K}' - [x_3 x_4]$.

γ) We use (3.3) again and β to obtain the analytic continuation of $F(x,0)$ : the product $F(x,0) \cdot b(x,h(x))$ is analytic everywhere in the complex plane cut along $[x_3 x_4]$.

The poles of $F(x,0)$ coincide with the zeros of $b(x,h(x))$ outside $C(1)$.

Same conclusions can be drawn for $F(0,y)$ and the proof of theorem 3.1 is terminated.

## IV - AN ATTEMPT TO SIMPLIFY THE RELATION (3.3)

We try to reduce (3.3) to an homogeneous equation (i.e. without right member).

An elementary computation shows that

α) $pq - \mu_1 \mu_2 \neq 0$, the transformation (translation)

$$ (4.0) \qquad \left\{ \begin{array}{ll} F(0,y) = \frac{p(q - \mu_2)}{pq - \mu_1 \mu_2} & F(0,0) + H(y) \\ F(x,0) = \frac{q(p - \mu_1)}{pq - \mu_1 \mu_2} & F(0,0) + G(x) \end{array} \right. $$

yields to the system.

$$ (4.1) \qquad \left\{ \begin{array}{l} R(x,y) = 0, \quad |x|, |y| \le 1 \\ H(y) \ a(x,y) + G(x) \ b(x,y) = 0 \end{array} \right. $$

where $a(x, y)$ and $b(x, y)$ are defined by (3.2).
Moreover

$$ (4.2) \quad \left\{ \begin{aligned} H(0) &= \frac{\mu_2 \mu_1^* F(0,0)}{\mu_1 \mu_2 - pq} \\ G(0) &= \frac{\mu_1 \mu_2^* F(0,0)}{\mu_1 \mu_2 - pq} \end{aligned} \right. $$

Section III gives the analytic continuations of $G(x)$ and $H(y)$.

β) $pq = \mu_1 \mu_2$ : The preceding transformation is not valid.

Recalling that $p = \mu_1 - \mu_1^*$
$q = \mu_2 - \mu_2^*$,

$pq - \mu_1 \mu_2 = 0$ can be written, dividing by $\mu_1^* \mu_2^*$

$$ \frac{\mu_1}{\mu_1^*} + \frac{\mu_2}{\mu_2^*} = 1, $$

$$ \text{or} \quad (4.3) \quad \left\{ \begin{array}{l} \mu_1 = \xi \mu_1^* \\ \mu_2 = (1-\xi)\mu_2^* \end{array} \right. \qquad 0 \le \xi \le 1 $$

In the case $\mu_1^* = \mu_2^* = 0$, (4.1) yields to the system

$$ \left\{ \begin{array}{l} R(x,y) = 0, \quad |x|, |y| \le 1 \\ F(0,x) + F(y,0) = F(0,0), \quad (x,y) \ne (1,1) \end{array} \right. $$

which clearly has no admissible solution due to the fact that $F(x,0) + F(0,y) > F(0,0)$
Using (4.3), (4.1) takes the following form :

$$ (4.4) \quad \begin{cases} R(x,y) = 0 \quad |x| \le 1, y \le 1 \\ [\mu_1^*(1-\frac{1}{x}) - \mu_2^*(1-\frac{1}{y})][\xi F(0,y) - (1-\xi)F(x,0)] = \\ \qquad [\mu_1^*(\frac{1}{x}-1)(1-\xi) + \mu_2^*(\frac{1}{y}-1)\xi] F(0,0) \end{cases} $$

$$ V - \text{THE ROOTS OF } h^1(x) = p(1 - \frac{1}{x}) + \mu_2(1 - \frac{1}{h(x)}) = 0 \quad \text{inside } C(\sqrt[3]{\frac{\mu_1}{\lambda_1}}) $$

Section III reveals that a stepping stone towards the solutions of the original problem is the study of the roots of the equation $b^1(x) = 0$. More precisely, we require only the roots inside $C(\sqrt[3]{\frac{\mu_1}{\lambda_1}})$ for reasons given in sections VI and VII. It seems convenient to introduce the following notations (valid until the end of the paper)

$$ (5.1) \quad \left\{ \begin{aligned} b^1(x) &= p\left(1 - \frac{1}{x}\right) + \mu_2\left(1 - \frac{1}{h(x)}\right) \\ a^1(x) &= q\left(1 - \frac{1}{h(x)}\right) + \mu_1\left(1 - \frac{1}{x}\right) \\ b^2(y) &= p\left(1 - \frac{1}{k(y)}\right) + \mu_2\left(1 - \frac{1}{y}\right) \\ a^2(y) &= q\left(1 - \frac{1}{y}\right) + \mu_1\left(1 - \frac{1}{k(y)}\right) \end{aligned} \right. $$

Up to a change of the parameters, the conclusions drawn for $b^1(x) = 0$ will hold for $a^2(y) = 0$.

The term "root" will always design a number different from 1.

**Lemma 5.1.** : Excluding the trivial root $x = 1$, $b^1(x)$ has at most two roots inside $C(\sqrt[3]{\frac{\mu_1}{\lambda_1}})$. Moreover, these roots (if any) are real, positive and belong to the set $[0, x_1] \cup [x_2, \sqrt[3]{\frac{\mu_1}{\lambda_1}}]$.
i) $b^1(x) = 0$ together (1.3) entails

$$ (5.2) \qquad \varphi(x) = \lambda_1(\mu_2 + p) x^2 - x[\mu_1^* \mu_2 + (\lambda_1 + \lambda_2 + \mu_1^*)p] + p\mu_1^* = 0 $$

$\varphi(x) = 0$ has two real roots [see appendix A].

$b^1(x) = 0$ subtracted from (1.3) entails

$\lambda_1(1-x) + \mu_1^*(1 - \frac{1}{x}) + \lambda_2(1 - h(x)) = 0 \quad : \ x \le 0$ would lead to

$h(x) > 1$ : this is impossible when the real part of $x$ is negative

Hence $x$ is positive.

From Section II it is obvious that a root $x$ cannot belong to the cut $[x_1, x_2]$ by checking $h(x)$ is a complex number and $b^1(x)$ does not vanish in this case.

The proof of Lemma 5.1 is concluded.

We make now the assumptions (valid in the whole section V)

$$ \left\{ \begin{array}{l} \displaystyle \frac{\mu_1}{\lambda_1} > 1 \\ \\ \displaystyle |x'| \le \sqrt{\frac{\mu_1}{\lambda_1}} \quad \text{when the range of variation is not explicitly stated.} \end{array} \right. $$

The following system of notations will also be used :

$$ \frac{db^1(x)}{dx} = \frac{p}{x^2} + \frac{\mu_2 h'(x)}{h^2(x)} \qquad (5.3) $$

$$ \frac{dh(x)}{dx} = h'(x) = \frac{\lambda_1 - \frac{\mu_1}{x^2}}{\frac{\mu_2}{h^2(x)} - \lambda_2} $$

$$ \Psi(x) = \frac{\lambda_1 x - \mu_1}{\mu_2 - \lambda_2 h(x)} ; \quad \frac{d\Psi(x)}{dx} = \frac{\lambda_1 (\mu_2 - \lambda_2 h(x)) + \lambda_2 (\lambda_1 x - \mu_1) h'(x)}{[\mu_2 - \lambda_2 h(x)]^2} $$

Thus, $b^1(x)$ can be rewritten at our convenience

$$ (5.4) \qquad b^1(x) = \left(1 - \frac{1}{x}\right) \left[ p + \mu_2 \Psi(x) \right] $$

Two cases are now investigated
1. $p < 0$

$$
(5.3) \quad \text{yields } \frac{db^1(x)}{dx} < 0 \text{ for } x \in [0, x_1] \cup [x_2, \sqrt{\frac{\mu_1}{\lambda_1}}]
$$

$$
\underline{1.a} \quad \mu_2 \geq \lambda_2
$$

Then $\Psi(x) < 0.$

Hence $p + \mu_2 \Psi(x) < 0$ and

there is no root in $C(\sqrt{\frac{\mu_1}{\lambda_1}})$

1.b $\mu_2 < \lambda_2$

Then $b_1(1) = \mu_2 - \lambda_2 < 0$

This implies :

* there is a root (and only one) in $C(\sqrt{\frac{\mu_1}{\lambda_1}})$ if $b^1(x_2) > 0$

Moreover, this root belongs to $[x_2, 1]$

* there is no root in $C(\sqrt{\frac{\mu_1}{\lambda_1}})$ if $b^1(x_2) < 0$

2. $p > 0$

$$
\underline{2.a} \quad \mu_2 \geq \lambda_2
$$

$$
(5.3) \quad \text{yields} \quad \frac{d\Psi(x)}{dx} > 0 \quad \text{for} \ x \in [0, x_1] \cup [x_2, \sqrt{\frac{\mu_1}{\lambda_1}}]
$$

i) If $b^1(x_2) > 0$ then
$$
\begin{cases}
\text{one root in } [x_2, \sqrt{\frac{\mu_1}{\lambda_1}}] & \text{if } b^1(\sqrt{\frac{\mu_1}{\lambda_1}}) > 0 \\
\text{no root in } [x_2, \sqrt{\frac{\mu_1}{\lambda_1}}] & \text{if } b^1(\sqrt{\frac{\mu_1}{\lambda_1}}) < 0 \\
\text{one root in } [0, x_1] & \text{if } b^1(x_1) < 0 \\
\text{no root in } [0, x_1] & \text{if } b^1(x_1) > 0
\end{cases}
$$
ii) If $b^1(x_2) < 0$ then $b^1(x_1) < 0$ (see Appendix B) : we deduce there is only one root in $[0, x_1]$ and no other root in $C(\sqrt{\frac{\mu_1}{\lambda_1}})$.

$$ \underline{2.b} \quad \mu_2 < \lambda_2 $$

As in 2.a, $\frac{d\Psi(x)}{dx} > 0$ for $x \in [0, x_1]$

Thus, there is one root in $[0, x_1]$ iff $b^1(x_1) < 0$

$$ (5.3) \text{ yields } h'(x) < 0 \text{ for } x \in [x_2, \sqrt{\frac{\mu_1}{\lambda_1}}] $$

When $x$ increases from $x_2$ to $\sqrt{\frac{\mu_1}{\lambda_1}}$, $h(x)$ decreases from $\sqrt{\frac{\mu_2}{\lambda_2}}$ to $y_2$. $y_2$ is the second branch point of $k(y)$.

$$ \text{It follows : } \begin{cases} \Psi(x) > 0 & \text{for } x \in [x_2, 1] \\ \frac{d\Psi(x)}{dx} > 0 & \text{for } x \in [1, \sqrt{\frac{\mu_1}{\lambda_1}}] \end{cases} $$

This implies :

* There is one root in $[1, \sqrt{\frac{\mu_1}{\lambda_1}}]$ if $b^1(\sqrt{\frac{\mu_1}{\lambda_1}}) > 0$

* There is no root in $C(\sqrt{\frac{\mu_1}{\lambda_1}}) - [0, x_1]$ if $b^1(\sqrt{\frac{\mu_1}{\lambda_1}}) < 0$

Similar conclusions can be drawn for $a^2(y)$ as follows:

- When $\mu_2 \ge \lambda_2$, it suffices to change the name of the parameters.

- When $\mu_2 < \lambda_2$, let us set

$$ a^2(y) = \left(1 - \frac{1}{y}\right) \left[q + \mu_1 \Phi(y)\right] \text{ where } \Phi(y) \stackrel{\text{def}}{=} \frac{\lambda_2 y - \mu_2}{\mu_1 - \lambda_1 k(y)} $$ 

$\Phi(y)$ increases on $[\sqrt{\frac{\mu_2}{\lambda_2}}, 1]$

i) $\underline{q < 0}$: $a^2(y)$ decreases on $[y_2, \sqrt{\frac{\mu_2}{\lambda_2}}]$

There is no root on $[\sqrt{\frac{\mu_2}{\lambda_2}}, \sqrt{\frac{\mu_2}{\lambda_2}}]$ if $q + \mu_1 \Phi(1) < 0$.
If $q + \mu_1 \Phi(1) > 0$, then

$$ \text{there is one root} \quad \left\{ \begin{array}{ll} \text{in } [\sqrt{\frac{\mu_2}{\lambda_2}}, 1] & \text{if } a^2(\sqrt{\frac{\mu_2}{\lambda_2}}) > 0 \\ \text{in } [\frac{\mu_2}{\lambda_2}, \sqrt{\frac{\mu_2}{\lambda_2}}] & \text{if } a^2(\sqrt{\frac{\mu_2}{\lambda_2}}) < 0 \end{array} \right. $$

ii) $q > 0$:

* no root in $[\frac{\mu_2}{\lambda_2}, 1]$

* one root in $[y_2, \frac{\mu_2}{\lambda_2}]$ iff $a^2(y_2) > 0$.

* one root in $[0, y_1]$ iff $a^2(y_1) < 0$.
VI - THE CASE pq = $\mu_1\mu_2$: DETERMINATION OF F(x,0) AND F(0,y) BY SOLVING A DIRICHLET
PROBLEM FOR A CIRCLE

From now on, let $J_m(z)$ and $R_e(z)$ denote respectively the imaginary
and the real part of the complex number $z$.

From section I, we know that

$J_m F(0,y) = 0$ for $y \in [y_1, y_2]$, since $F(0,y)$ is analytic in $C(1)$ and its
power series expansion has positive coefficients.

Hence, by using system (4.4) and section III, it follows :

$$
(6.1) \quad J_m(1-\xi) F(x,0) = J_m \frac{\mu_2^* \left( \frac{1}{h(x)} - 1 \right) F(0,0)}{-\mu_1^* \left(1 - \frac{1}{x}\right) + \mu_2^* \left(1 - \frac{1}{h(x)}\right)} \quad \text{for } |x| = \sqrt{\frac{\mu_1}{\lambda_1}}
$$

provided that $b^1(x)$ has no root in $C(\sqrt{\frac{\mu_1}{\lambda_1}})$; this is
**a Dirichlet problem for a circle.**

F(x,0) is determined from (5.1), inside C(√(μ₁/λ₁)), up to a constant, by
Schwarz's formula as follows:

$$
(6.2) \quad F\left(\sqrt{\frac{\mu_1}{\lambda_1}}, 0\right) = \frac{i}{2\pi} \int_{-\pi}^{\pi} u(\rho) \frac{e^{i\rho} + z}{e^{i\rho} - z} d\rho + D, \quad |z| < 1
$$

where D is a real constant

$$
\text{and} \quad u(\rho) = \frac{1}{1-\xi} J_m \frac{\mu_2^*(1 - \frac{1}{h(x)}) F(0,0)}{\mu_1^*(1 - \frac{1}{x}) - \mu_2^*(1 - \frac{1}{h(x)})}
$$
$$ \text{with } x = \sqrt{\frac{\mu_1}{\lambda_1}} e^{i\rho} $$

$u(\rho)$ is an odd function of $\rho$. This implies

$$ (6.3) \qquad F\left(\sqrt{\frac{\mu_1}{\lambda_1}} z, 0\right) = \frac{1}{\pi} \int_0^\pi \frac{z \sin \rho \, u(\rho) d\rho}{1 + z^2 - 2z \cos \rho} + F(0, 0) \quad z < 1 $$

$$ (6.4) \quad u(\rho) = \frac{-\lambda_1 \sin \rho H(\rho)}{[ \rho_2^*(\mu_1^* - \mu_2^*) H^2(\rho) + (\mu_2^* - \mu_1^* + \lambda_1 + \lambda_2) H(\rho) - \mu_2^* ] (1-\xi)} $$

$$ \text{where} \quad H(\rho) = h\left(\sqrt{\frac{\mu_1}{\lambda_1}} e^{i\rho}\right) \\ = \frac{\lambda_2 + \mu_2 + \alpha - \sqrt{[(\sqrt{\lambda_2} + \sqrt{\mu_2})^2 + \alpha][(\sqrt{\lambda_2} - \sqrt{\mu_2})^2 + \alpha]}}{2\lambda_2} $$

$$ \text{and } \alpha = \lambda_1 + \mu_1 - 2\sqrt{\lambda_1} \frac{\mu_1}{\lambda_1} \cos \rho. $$

Note that $H(\rho)$ is real.

The expression of $F(\sqrt{\frac{\mu_1}{\lambda_1}} z, 0)$ in terms of elliptic functions of the third kind which are given in Appendix A.
1) If $\mu_2 \ge \lambda_2$, we have seen in section V that $b^1(x)$ has no zeros inside $C(\sqrt{\mu_2}/\lambda_2)$.

In that case, $a^2(y)$ has no zeros inside $C(\sqrt{\mu_2}/\lambda_2)$ and

$$ (6.5) \qquad F(0, \sqrt{\mu_2}/\lambda_2 z) = \frac{1}{\pi} \int_0^\pi \frac{z \sin\theta v(\theta) d\theta}{1+z^2-2z \cos\theta} + F(0,0) |z| < 1 $$

$$ (6.6) \qquad v(\theta) = \frac{- \lambda_2 \sin\theta K(\theta)}{[\rho_1^*(\mu_2^* - \mu_1^*)K^2(\theta) + (\mu_1^* - \mu_2^* + \lambda_1 + \lambda_2)K(\theta) - \mu_1^*]} \xi $$

where $K(\theta) = k(\sqrt{\mu_1}/\lambda_1 e^{i\theta})$

$$ = \frac{\lambda_1 + \mu_1 + \beta - \sqrt{[(\sqrt{\lambda_2} + \sqrt{\mu_2})^2 + \beta][(\sqrt{\lambda_2} - \sqrt{\mu_2})^2 + \beta]}}{2\lambda_1} $$

$$ \text{and } \beta = \lambda_2 + \mu_2 - 2\sqrt{\lambda_2\mu_2} \cos\theta $$

Note that $K(\theta)$ is real.

2) If $\mu_2 < \lambda_2$, $b^1(x)$ may have a zero on $[x_2, 1]$

which is equivalent to

"$a^2(y)$ may have a zero on $[\frac{\mu_2}{\lambda_2}, \sqrt{\frac{\mu_2}{\lambda_2}}]$"

But equation (4.4) and section III entail that the system is ergodic iff

$$ (6.7) \qquad a^2(y) \neq 0 \text{ in } C(\mathbb{T}) $$

Indeed, (6.5) determines $F(0,y)$ inside $C(\sqrt{\frac{\mu_2}{\lambda_2}})$ and the same formula (6.5) holds for $\frac{\mu_2}{\lambda_2} \le y \le 1$ iff (6.7) is satisfied.
The ergodicity condition (6.7).

From Section V we deduce immediately that (6.7) is satisfied iff

$q + \mu_1 \Phi(1) < 0$, which yields:

$$q + \mu_1 \frac{\lambda_2 - \mu_2}{\mu_1 - \lambda_1} < 0 \quad \text{or, using } \mu_1 = \xi \mu_1^* \text{ and } \mu_2 = (1 - \xi) \mu_2^*$$

(6.8)

$$1 - \rho_1^* - \rho_2^* > 0$$

$F(0,0)$ is easily obtained from (1.2) : it is sufficient to couple x and y

by the relation $\mu_1^*(1-\frac{1}{x}) = \mu_2^*(1-\frac{1}{y})$ and to write $F(1,1) = 1$.

It follows $F(0,0) = 1 - \rho_1^* - \rho_2^*$ and (6.8) yields $F(0,0) > 0$
VII - THE CASE pq ≠ µ₁µ₂ : DETERMINATION OF F(x,o) AND F(o,y) BY SOLVING AN HOMOGENEOUS RIEMANN-HILBERT PROBLEM FOR A CIRCLE.

In that section we use intensively the procedure given in [Muskhelishvili-6],
Chapter 5, pp. 39-40.

Theorem 7.1. :

Our problem is a particular case of a famous general problem due to Riemann and
first studied by Hilbert.

This problem is as follows :

Let $S^+$ be a finite or infinite region, bounded by a single simple contour L.

It is required : to find a function Ω(z) = u+iv, holomorpic in S⁺ and continuous in S⁺ + L, satisfying the boundary condition

$$
(7.1) \quad \mathcal{R}_e U(z) \cdot \Omega(z) = V(z) \quad \text{on } L,
$$

where U(z), V(z) are continuous functions given on L. The homogeneous problem
is obtained by putting

$$
V(z) \equiv 0 \quad \text{in} \ (7.1)
$$

Demonstration :

Lemma 7.1 :

$$
(7.2) \quad G(z) = \frac{[z - k(\alpha_2)]^i [z - k(\beta_2)]^{i_2} \tilde{G}(z)}{[z - \gamma_1]^{i_3} z^3}, \quad |z| < \sqrt{\frac{\mu_1}{\lambda_1}}
$$

where $i_j, j = 1, 2, 3$ take the values 0 or 1 and

i) $\gamma_1$ is the eventual root of $b^1(x)$ in $[1, \sqrt{\frac{\mu_1}{\lambda_1}}]$

ii) $\alpha_2, \beta_2$ are the eventual zeros of $a^2(y)$ in $[0, y_1] \cup [y_2, 1]$

iii) $\tilde{G}(z)$ is analytic inside $C(\sqrt{\frac{\mu_1}{\lambda_1}})$
### Proof of lemma 7.1 :

#### Proof of i) :

System (4.1) entails (with the notations of section V)

$$ (7.3) \qquad H(h(x)) a^1(x) + b^1(x) G(x) = 0 $$

$G(x)$ is meromorphic for $x \in [1, \sqrt{\frac{\mu_1}{\lambda_1}}]$

Section V shows that, in $C(\sqrt{\frac{\mu_1}{\lambda_1}})$ - $C(1)$, $b^1(x)$ has at most one root ($\neq 1$) denoted here by $\gamma_1$.

Moreover it is a matter of fact to see that $a^1(x)$ and $b^1(x)$ have no common root ($\neq 1$). Hence, $\gamma_1$ is a pole of $G(x)$ if $H(h(\gamma_1)) \neq 0$. But, $h(\gamma_1) \in [y_2, 1]$. It suffices to show $H(y) \neq 0$ for $y \in [y_2, 1]$, which is a consequence of equation (4.2) as follows :

* if $\mu_1\mu_2 > pq$, then $H(0) > 0$: $H(y)$, $y \in [0,1]$ has a power series expansion with real positive coefficients and this, in turn, implies $H(y) > 0$ for $y \in [0,1]$.

* if $\mu_1\mu_2 < pq$, then $p < 0$ and $q < 0$: in that case $b^1(x) \neq 0$, $x \in [1, \sqrt{\frac{\mu_1}{\lambda_1}}]$ and $\gamma_1$ does not exists.

The proof of i) is terminated.

#### Proof of ii) :

We use again system (4.1) to derive

$$ (7.4) \qquad H(y) a^2(y) + G(k(y)) b^2(y) = 0 $$

$H(y)$ must be analytic in $C(1)$ : this entails the zeros of $a^2(y)$ in $C(1)$ are zeros of $G(k(y))$.

Observing that $a^2(y)$ has no negative roots (see section V), point ii) follows readily.

Finally, using i) and ii), formula (7.2) holds and the proof of lemma 7.1 is concluded.
How, we are in a position to demonstrate theorem 7.1 as in section VI,
$J_m H(y) = 0$ for $y \in [y_1, y_2]$, since $H(y)$ is analytic in $C(1)$ and its power
series expansion has positive coefficients.

Hence, upon setting

$$
(7.5) \quad U(z) = \frac{b^1(z)}{a^1(z)} \cdot \frac{[z - k(\alpha_2)]^1 [z - k(\beta_2)]^2}{(z - \gamma_1)^3}
$$

we obtain

$$
(7.6) \quad \mathcal{R}_e i U(z) \tilde{G}(z) = 0 \quad \text{for } |x| = \sqrt{\frac{\mu}{\lambda_1}}
$$

The boundary condition (7.6) is a particular case of (7.1), putting $V(z) \equiv 0$.

This terminates the proof of theorem 7.1.

From [6] formula (40-10) - § 40, $\tilde{G}(z)$ is given by :

$$
(7.7) \quad \tilde{G}(z) = D e^{\Gamma(z)} \quad \text{for } |z| < \sqrt{\frac{\mu}{\lambda_1}}
$$

where D is a constant, non zero, and :

$$
(7.8) \quad \Gamma(z) = \frac{1}{2i\pi} \int_C \left( \sqrt{\frac{\mu z}{\lambda_1}} \right) \frac{\log \left[ \frac{t^{-\chi} J(t)}{t-z} \right]}{t-z} dt
$$

$$
\text{where: } J(t) = \frac{iU(t)}{iU(t) + U(t)} = - \frac{\bar{U}(t)}{U(t)}, \quad \text{and}
$$

$$
\chi - \frac{1}{2i\pi} \log \left[ \frac{\bar{U}(t)}{U(t)} \right] \quad \text{or}
$$

$$
(7.9) \quad \chi = - \frac{1}{\pi} [\arg U(t)] \quad \text{, denoting by } \arg(z) \text{ the function} \\
\qquad \qquad c\left(\sqrt{\frac{\mu z}{\lambda_1}}\right)
$$

"argument of z".
**Lemma 7.2:**

$$ \chi = 2[N_p \cdot \operatorname{sgn}(\mu_2 - \lambda_2) - N_z] + \frac{1}{\pi} \arg \frac{b^1(x)}{a^1(x)} \xrightarrow[x_1 \ x_2]{\xrightarrow[x_1 \ x_2]{\longrightarrow}} $$

[denoting by sgn(x) the function "sign of x" with sgn(0) = 0]

where

* $N_p$ is the number of zeros of $a^2(y)$ on $[1, \sqrt{\frac{\mu_2}{\lambda_2}}]$

* $N_z$ is the number of zeros of $b^1(x)$ on $[0, x_1] \cup [x_2, 1]$

* $\arg\left[\frac{b^1(x)}{a^1(x)}\right] \xrightarrow[x_1 \ x_2]{\xrightarrow[x_1 \ x_2]{\longrightarrow}}$ is the variation of the argument of $\frac{b^1(x)}{a^1(x)}$ along the

* "contour" $[x_1, x_2]$, starting from $x_1$ above $[x_1 x_2]$; going to $x_2$ and coming back to $x_1$ below $[x_1 x_2]$.

**Demonstration**

Using formulas (7.5), (7.9) and the principle of the argument [Fuchs-3],

we obtain:

$$ \chi = - \frac{1}{\pi} \arg [U] = 2(l - N_z) + \frac{1}{\pi} \arg [U] \xrightarrow[x_1 \ x_2]{\xrightarrow[x_1 \ x_2]{\longrightarrow}} $$

[the positive direction on $C(\sqrt{\frac{\mu_1}{\lambda_1}})$ is counter clockwise]

where

i) $N_z$ = number of zeros of $b^1(x)$ in $C(\sqrt{\frac{\mu_1}{\lambda_1}})$ - number of zeros of $b^1(x)$ in $[1, \sqrt{\frac{\mu_1}{\lambda_1}}]$, that is

$N_z$ = number of zeros of $b^1(x)$ in $[0,1]$

ii) $l = l_1 - l_2$, with

$l_1$ = number of zeros of $a^1(x)$ in $C(\sqrt{\frac{\mu_1}{\lambda_1}})$

$l_2$ = number of zeros of $a^2(y)$ in $[0,1]$ [$l_2$ is due to $\alpha_2$ and $\beta_2$ in formula (7.5)].
Using the mapping $h(x) = [-\sqrt{\frac{\mu_1}{\lambda_1}}, \sqrt{\frac{\mu_1}{\lambda_1}}] \xrightarrow{h(x)} [-\sqrt{\frac{\sqrt{\frac{\mu_2}{\lambda_2}}}{\lambda_2}}, \sqrt{\frac{\sqrt{\frac{\mu_2}{\lambda_2}}}{\lambda_2}}]$

[there is a bijection between the two intervals], we can express $\ell_1$ as the number of zeros of $a^2(y)$ in $[-\sqrt{\frac{\mu_2}{\lambda_2}}, \sqrt{\frac{\mu_2}{\lambda_2}}]$. From Section V we deduce

$$ \ell = \begin{cases} N_z & \text{if } \mu_2 > \lambda_2 \\ -N_z & \text{if } \mu_2 < \lambda_2 \\ 0 & \text{if } \mu_2 = \lambda_2 \end{cases} $$

In 7.5, $k(\alpha_2)$, $k(\beta_2)$ and $\gamma_1$ are real numbers outside $[x_1, x_2]$: Hence

$$ \arg \left[ \frac{[z-k(\alpha_2)]^{i_1} [z-k(\beta_2)]^{i_2}}{[z-\gamma_1]^{i_3}} \right] = 0 \quad \text{and} $$

$$ \text{we have } \frac{1}{\pi} \arg [U] \underset{x_1 x_2}{\overset{x_1 x_2}{\rightleftharpoons}} = \frac{1}{\pi} \arg \left[ \frac{b^1(x)}{a^1(x)} \right] \underset{x_1 x_2}{\overset{x_1 x_2}{\rightleftharpoons}} $$

The proof of Lemma 7.2 is concluded

**Lemma 7.3**

$$ (7.11) \quad \frac{1}{\pi} \arg \frac{b^1(x)}{a^1(x)} \underset{x_1 x_2}{\overset{x_1 x_2}{\rightleftharpoons}} = \operatorname{Sgn}(\mu_1 \mu_2 - pq) \left[ \operatorname{sgn} \frac{b^1(x_1)}{a^1(x_1)} - \operatorname{sgn} \frac{b^1(x_2)}{a^1(x_2)} \right] $$

**Demonstration:**

$$ h(x_1) = -\sqrt{\frac{\mu_2}{\lambda_2}} \quad \text{and} \quad h(x_2) = \sqrt{\frac{\mu_2}{\lambda_2}} \quad \text{are real.} $$

When $x$ reaches $[x_1, x_2]$ from above, $h(x)$ has a negative imaginary part [referring to the mapping $x \to h(x)$, $[x_1, x_2] \to x(\sqrt{\frac{\mu_2}{\lambda_2}})$ and the upper limit of $[x_1, x_2]$]
corresponds to the inferior half circle of radius $\sqrt{\frac{\mu_2}{\lambda_2}}$. Then it is easy to derive $\operatorname{sgn} \int_m \frac{b^1(x)}{a^1(x)} = \operatorname{sgn} [\mu_1 \mu_2 - pq]$ for $x \in [x_1, x_2]$, which yields (7.11). The

Lemma 7.3 is proved.

$$ (7.12) \quad \frac{1}{\pi} \left[ \arg \frac{b^1(x)}{a^1(x)} \right] \underset{x_1 x_2}{\longrightarrow} \operatorname{sgn} (pq - \mu_1 \mu_2) \left[ \operatorname{sgn} \frac{b^1(x_2)}{a^2(\sqrt{\frac{\mu_2}{\lambda_2}})} + \operatorname{sgn} b^1(x_1) \right] $$

$$ \text{remarking that } a^1(x_1) = a^2(-\sqrt{\frac{\mu_2}{\lambda_2}}) < 0. $$

### Lemma 7.4

1) For $\chi \le -2$, the homogeneous Riemann-Hilbert problem has no solutions different from zero.

2) For $\chi \ge 0$, the homogeneous Riemann-Hilbert problem has exactly $\chi + 1$ linearly independent solutions; the general solution is given by

$$ \Theta(z) = G(z)(c_0 z^\chi + c_1 z^{\chi-1} + \dots + c_\chi) \quad \text{where} $$
$c_0, c_1, \dots, c_\chi$ are constants subject to $c_\chi = \bar{c}_{\chi-k}$, $k = \alpha, 1, \dots, \chi$ but

otherwise arbitrary

### Demonstration

See [Muskhelishvili-6] § 40-p.100.
### Theorem 7.2

1) The homogeneous Hilbert problem satisfying the boundary condition (7.6) has, at most, one solution. In other words, $\chi \le 0$.

2) The system is ergodic iff $\chi = 0$, which is equivalent to

$$ (7.13) \quad \left\{ \begin{array}{l} \frac{db_1^1(x)}{dx} \Big|_{x=1} < 0 \iff \mu_1^* > \frac{\mu_2^1 \lambda_1 - \mu_1^1 \lambda_2}{\mu_2^1 - \lambda_2} \\ \\ \frac{da_1^2(y)}{dy} \Big|_{y=1} < 0 \iff \mu_2^* > \frac{\mu_1^1 \lambda_2 - \mu_2^1 \lambda_1}{\mu_1^1 - \lambda_1} \end{array} \right\} \quad \text{if } \mu_2 \ge \lambda_2 $$

$$ (7.14) \quad \frac{da_2^2(y)}{dy} \Big|_{y=1} < 0 \iff \mu_2^* > \frac{\mu_1^1 \lambda_2 - \mu_2^1 \lambda_1}{\mu_1^1 - \lambda_1} \quad \text{if } \mu_2 \le \lambda_2 $$

### Proof

We build a table for all possible values of $\chi$ using formulas (7.10), (7.12) and section V. It is convenient to introduce the variables $T_p, T_q, F_p, F_q$ where

$$ T_p \equiv [p + \mu_2 \Psi(1) < 0] $$

$$ F_p \equiv [p + \mu_2 \Psi(1) > 0] $$

$$ T_q \equiv [q + \mu_1 \Phi(1) < 0] $$

$$ F_q \equiv [q + \mu_1 \Phi(1) > 0] $$

$\Phi(y)$ and $\Psi(a)$ have been defined in section V and, in the tables " if $\chi$" means " if $\chi$ is true".

$i) \mu_2 \le \lambda_2$

<table><thead><tr><th>N<sub>z</sub> / N<sub>q</sub></th><th>0</th><th>1</th><th>2</th></tr></thead><tbody><tr><th>0</th><td>$\chi = \begin{cases} -2 & \text{if } F_q \\ 0 & \text{if } T_q \end{cases}$</td><td>$\chi = \begin{cases} -2 & \text{if } (F_p \text{ or } F_q) \\ 0 & \text{if } T_p \cdot T_q \end{cases}$</td><td>$\chi = -2$</td></tr><tr><th>1</th><td>$\chi = 0$</td><td>$\chi = \begin{cases} 0 & \text{if } T_p \\ -2 & \text{if } F_p \end{cases}$</td><td>$\chi = -2$</td></tr></tbody></table>
ii) $\mu_2 \ge \lambda_2$

<table><thead><tr><th>N<sub>Z</sub> / N<sub>P</sub></th><th>0</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>$\chi = \begin{cases} -2 & \text{if } F_q \\ 0 & \text{if } T_q \end{cases}$</td><td></td></tr><tr><th>1</th><td>$T_q$ and $\chi = -2$</td><td></td></tr></tbody></table>

These tables show that

$$ \chi = 0 \text{ iff } \begin{cases} (7.13) \text{ when } \mu_2 \ge \lambda_2 \\ (7.14) \text{ when } \mu_2 < \lambda_2 \end{cases} . \quad \text{Then } i_2 = 0 \text{ in (7.2)} $$

## Remarks

a) To obtain Table i), the reader will notice that certain inequalities cannot hold simultaneously, as for example

$$ \begin{cases} a^2 \left(\sqrt{\frac{\mu_2}{\lambda_2}}\right) > 0 \\ b^1(x_2) < 0 \end{cases} \quad \text{or} \quad \begin{cases} p + \mu_2 \Psi(1) > 0 \\ q + \mu_1 \Phi(1) > 0 \end{cases} \quad \text{which would yield} \\ \mu_1^* \mu_2^* < 0. $$

b) In table ii), the values of $\chi$ do not rely on the values of $N_Z$. Moreover, the ergodicity condition (7.14) can be derived from (7.4) and is the same as condition (6.7) [section VI]. This concludes the proof of theorem 7.2.

## Theorem 7.3

Assuming (7.13) or (7.14), $F(z,0)$ is given by

$$ (7.15) \qquad \frac{F(z,0)}{F(0,0)} = \frac{q \mu_1^*}{\mu_1 \mu_2 - pq} + \frac{\mu_1 \mu_2^*}{\mu_1 \mu_2 - pq} \quad \frac{G(z)}{G(0)}, \quad |z| < \sqrt{\frac{\mu_1}{\lambda_1}} $$
$$ \text{Where } * \quad F(0,0) = \left[ \frac{\mu_2 \lambda_1 - \mu_1 \lambda_2 + \mu_2^* (\mu_1 - \lambda_1)}{\mu_1 \mu_2^*} \right] \cdot \frac{G(0)}{G(1)} $$

* G(z) is derived from (7.2) and (7.7) using

$$ \Gamma(z) = \frac{1}{2\pi} \int_C \sqrt{\frac{\mu_1}{\lambda_1}} \frac{\Delta(t)dt}{t-z} \quad \text{and} \quad \Delta(t) = \arg \left[ \frac{-\overline{U(t)}}{U(t)} \right] $$

### Proof

(7.15) is implied readily by (7.8) and Theorem 7.2. $\Gamma(z)$ can be expressed by means of elliptic functions of the third kind.

The reader may verify that the "elliptic part" of the integral (7.15) vanishes iff $p + q = 0$. Then

$$ (7.16) \quad \begin{cases} F(x,0) = \frac{F(0,0)}{1-\alpha x} \\ F(x,y) = \frac{F(0,0)}{(1-\alpha x)(1-\beta y)} \end{cases} , \quad \alpha, \beta \text{ being obtained from (7.13) or (7.14)} $$

As can be seen, this is a product form solution. In fact, a necessary and sufficient condition for a product form solution in equation (1.2) is

$$ (7.17) \qquad p + q = 0 \qquad \text{i.e.,} \qquad \boxed{\mu_1 + \mu_2 = \mu_1^* + \mu_2^*} $$

Hence, $\mu_1^* > \mu_1$ leads to $\mu_2^* < \mu_2$. The physical explanation is not obvious. We would like to call this a "power steal": one class of customers (or one processor) steals power from the other one. $\Gamma(z)$ in (7.15) will not be explicitly computed. The complexity is equivalent to that of the previous section VI.
The method used in section VI and VII can be applied in a more
general context. Let us assume that a t.d.r.w. has a stationary distri-
bution if and only if there exists a function $F(x,y) = \sum_{i,j} p_{ij} x_i y_j$
satisfying

$\Sigma |p_{ij}| < \infty$ (space $L_1$) and the following functional equation

$$
R(x,y) \cdot F(x,y) = A \text{ (or } y) \cdot F(x,0) + B(x,y) \cdot F(0,y) + C(x,y)
$$
where $A(x,y)$, $B(x,y)$ and $C(x,y)$ are known and continuous. Then the
determination of $F(x,y)$ reduces to the solution of a Riemann-Hilbert
problem whenever the following four conditions are met (the notation
is the same as before):

1) The continuous function k(y) [resp. h(x)] such that
|k(y)| ≤ 1 [resp. |h(x)| ≤ 1] if |y| = 1 [resp |x| = 1

2) $k(y)$ [resp. $h(x)$] has two branch points inside $C(1)$, $y_1$ and $y_2$ [resp. $x_1$ and $x_2$] which are the ends of a "cut" [$y_1, y_2$] (resp. [$x_1, x_2$]).

3) The cut [$y_1y_2$] (resp. [$x_1x_2$]) is mapped onto a simple closed curve $C_k$ [resp. $C_h$] under the mapping $y \to k(y)$ [resp. $x \to h(x)$].

4) Moreover, the regions inside $C(1)$ and $C_k$ (resp. $C_h$) must have a non-empty intersection $D_k$ (resp. $D_h$) such that $|k(y)| \le 1$ [resp. $|h(x)| \le 1$] for $y \in D_k$ [resp $x \in D_h$].

Up to a conformal transformation, condition 3) says it is
possible to reduce the general case to that of a circular region.
Specifically, the four preceding conditions hold in the problem of
t.d.r.w. studied by Malyshev [5]. It is worthwhile to note the
possibility of solving the Hilbert problem for arcs by using the
analytic continuation of F(x,0) to the whole complex plane (see
Section III) and the arc [x<sub>3</sub>x<sub>4</sub>].
When the genus of R(x,y) is greater than 1, some of the conditions
1 to 4 may be not satisfied. Then, the method is still valid, (an example
will be given in a future paper) but the complexity of the computations
is greater.
REFERENCES

[1] Coffman, E. G. and Mitrani, I., *Selecting a Scheduling Rule that Meets Pre-Specified Response Time Demands*, Proceedings, 5th Symposium on Operating Systems Principles, Austin, 1975.

[2] Flatto, L. and MacKean, H. *Two Parallel Queues with Equal Servicing Rates*, IBM Research Center Watson, Report RC 5916, March 1976.

[3] Fuchs, B. A. and Shabat, B. V., *Functions of a Complex Variable and Some of Their Applications*, Volume I, Pergamon Press, 1964.

[4] Cohen, J. W., *The Single-Server Queue*, North-Holland Publishing Co., 1969.

[5] Malyshev. V. A., *An Analytical Method in the Theory of Two-Dimensional Positive Ramdon Walks*, translated from Sibirskii Mathematicheskii Zhurnal, Vol. 13, No. 6, pp. 1314-1329, November-December 1972.

[6] Mushkhelishvili, N. I., *Singular Integral Equations*, P. Noordhoff N.V. - Groningen, Holland-Moscow, 1946.

[7] Gradshteyn, I. S. and Ryzhik, I. M., *Tables of Integral Series Products*, Academic Press, New York and London, 1965.

[8] Mitrani, I. and Hine, J. H., *Complete Parameterized Families of Job Scheduling Strategies*, Technical Report Series, University of Newcastle upon Tyre, Number 81, October 1975.
# APPENDIX A

When $\lambda_1 \le \mu_1$ and $\lambda_2 \le \mu_2$,

$b^1(x_2) < 0$ entails $b^1(x_1) \le 0$.

The notation is the same as in Section V.

## Proof

$$b^1(x_2) = \left(1 - \frac{1}{x_2}\right) [p + \mu_2 \Psi(x_2)]$$

$$b^1(x_1) = \left(1 - \frac{1}{x_1}\right) [p + \mu_2 \Psi(x_1)]$$

It suffices to show that $\Psi(x_1) > \Psi(x_2)$.

Formula (2.4), Section II leads us to introduce the function

$$f(s) = \frac{\lambda_1 - \mu_1 + s^2 \sqrt{(\lambda_1 + \mu_1 + s^2)^2 - 4\lambda_1\mu_1}}{2s}$$

Upon setting $s_1 = \sqrt{\mu_2} + \sqrt{\lambda_2}$ and $s_2 = \sqrt{\mu_2} - \sqrt{\lambda_2}$, we get

$$\Psi(x_2) = \frac{1}{\sqrt{\mu_2}} f(s_2)$$

$$\Psi(x_1) = \frac{1}{\sqrt{\mu_2}} f(s_1)$$

$$\frac{df}{ds} = \frac{1}{2s^2} g(s)$$

$$\text{where } g(s) = s^2 [q(s) - s^2] + (\mu_1 - \lambda_1) q(s) + (\mu_1 - \lambda_1)^2$$

$$\text{and } q(s) = \sqrt{(\lambda_1 + \mu_1 + s^2)^2 - 4\lambda_1\mu_1}$$

Obviously $g(s) > 0$.

Hence, $f(s)$ is an increasing function of $s_1$ for $s > 0$ and $f(s_1) > f(s_2)$.

This terminates the proof.
Expression of the Integral in Formula (6.3)

Upon setting

$$
t = \frac{z^2+1}{2z}, \quad u = \cos \rho, \quad \Sigma = \lambda_1 + \lambda_2 + \mu_1 + \mu_2,
$$

$$
\alpha = \frac{\Sigma + 2\sqrt{\mu_2\lambda_2}}{2\sqrt{\mu_1\lambda_1}}, \quad \beta = \frac{\Sigma - 2\sqrt{\mu_2\lambda_2}}{2\sqrt{\mu_1\lambda_1}}
$$

it follows

$$
(A.1) \quad I(z) = \frac{(1-\xi)\pi}{\lambda_1 F(0,0)} \cdot \left[ F\left(\sqrt{\frac{\mu}{\lambda_1}}|z,0\right) - F(0,0) \right] = \int_{-1}^{1} \frac{\sqrt{1-u^2} \, du}{(t-u) [a+bu+cR]}
$$

$$
\text{where } a = \frac{\Sigma}{2} \left[ \frac{\xi}{1-\xi} - \frac{\mu_1^*}{\mu_2^*} \right] - 2\mu_1^*
$$

$$
b = \sqrt{\lambda_1 \mu_1^* \xi} \left[ \frac{\mu_1^*}{\mu_2^*} - \frac{2-\xi}{1-\xi} \right]
$$

$$
c = \frac{1}{2} \left[ \frac{\mu_1^*}{\mu_2^*} + \frac{\xi}{1-\xi} \right]
$$

$$
R = 2\sqrt{\mu_1\lambda_1} \cdot \sqrt{(\alpha-\mu)(\beta-\mu)}
$$

Formula (A.1) yields

$$
(A.2) \quad I(z) = I_{1}(z) + I_{2}(z)
$$

$I_1(z)$ [resp. $I_2(z)$] is the "rational" [resp. "elliptic"] part of $I(z)$. We
proceed now to derive $I_1(z)$ and $I_2(z)$.

$$
1) \quad I_1(z) = \int_0^\pi \frac{[a+b \cosh \rho] \sin^2 \rho d\rho}{(t-\cosh \rho)(\alpha_1 - \cosh \rho)(\alpha_2 - \cosh \rho)(b^2 - 4\lambda_1 \mu_1 c^2)}
$$

$$
\text{where } \alpha_i = \frac{1+\delta_i^2}{2\delta_i}, \quad |\alpha_i| > 1, \ |\delta_i| < 1, \ i = 1, 2
$$
$\delta_i$ being real numbers. [This results from Section V].

But, $\frac{a+b \cos \rho}{(t-\cos \rho)(\alpha_1-\cos \rho)(\alpha_2-\cos \rho)} = \frac{A}{t-\cos \rho} + \frac{B_1}{\alpha_1-\cos \rho} + \frac{B_2}{\alpha_2-\cos \rho}$

$$\text{where } A = \frac{a+bt}{(t-\alpha_1)(t-\alpha_2)}$$

$$B_1 = \frac{a+b\alpha_1}{(t-\alpha_1)(\alpha_2-\alpha_1)}$$

$$B_2 = \frac{a+b\alpha_2}{(t-\alpha_2)(\alpha_1-\alpha_2)}$$

Using Gradshteyn [ ], p. 366 formula 3.613-3, we get

$$I_1(z) = \frac{\pi}{(z^2 - 4\lambda_1 \mu_1 c^2)} [zA + \delta_1 B_1 + \delta_2 B_2]$$

and, after a somewhat lengthy computation,

$$I_1(z) = \frac{2\delta_1\delta_2\pi}{b^2 - 4\lambda_1\mu_1c^2} \left[ bz + \frac{2a(\delta_1 + \delta_2)}{1 - \delta_1\delta_2} \right] \cdot \frac{z}{(1 - z\delta_1)(1 - z\delta_2)}$$

$$2) \quad I_1(z) = \frac{2c\sqrt{\lambda_1\mu_1}}{b^2 - 4\lambda_1\mu_1c^2} \int_{-1}^{1} \frac{(1-u^2)(\beta-u)(\alpha-u)du}{(t-u)(u-\alpha_1)(u-\alpha_2)\sqrt{(1+u)(1-u)(\beta-u)(\alpha-u)}}$$

Repeatedly applying Gradshteyn [ ], formulas 3.147-3, 3.148-3, and 3.151-3, we obtain

$$I_2(z) = K \left[ \frac{(t-\alpha)(t+1)}{(t-\alpha_1)(t-\alpha_2)} \cdot \Pi\left(\frac{\pi}{2}, \frac{2(t-\beta)}{(\beta+1)(t-1)}, r\right) + \frac{L}{t-\alpha_1} + \frac{M}{t-\alpha_2} + N \right], \text{ where}$$
$$ * K = \frac{4c\sqrt{\lambda_1\mu_1} (\beta-1)}{(b^2-4\lambda_1\mu_1c^2)\sqrt{(\alpha-1)(\beta+1)}}, $$

* $\Pi(\rho, n, k)$ is the elliptic integral of the third kind:

$$ \Pi(\rho, n, k) = \int_{0}^{\sin\rho} \frac{dx}{(1+nx^2)^2 \sqrt{(1-x^2)(1-k^2x^2)}} $$

$$ * r = \sqrt{\frac{2(\alpha-\beta)}{(\alpha-1)(\beta+1)}} $$

$$ * L = \frac{(1+\alpha_1)(\alpha-\alpha_1)}{\alpha_1-\alpha_2} \quad \Pi\left(\frac{\pi}{2}, \frac{2(\alpha_1-\beta)}{(\beta+1)(\alpha_1-1)}, r\right) $$

$$ * M = \frac{(1+\alpha_2)(\alpha-\alpha_2)}{\alpha_2-\alpha_1} \quad \Pi\left(\frac{\pi}{2}, \frac{2(\alpha_2-\beta)}{(\beta+1)(\alpha_2-1)}, r\right) $$

$$ * N = -\Pi\left(\frac{\pi}{2}, \frac{2}{\beta+1}, r\right) $$