Rodolphe Garbit
email: rodolphe.garbit@univ-angers.fr

Kilian Raschel
email: raschel@math.cnrs.fr

RANDOM WALKS WITH DRIFT INSIDE A PYRAMID: CONVERGENCE RATE FOR THE SURVIVAL PROBABILITY

Keywords: 2020 Mathematics Subject Classification. 60G50,60G40,60E10,52B11 Random walks in cones, Survival probabilities, Laplace transform, Pyramids, Overshoots

We consider multidimensional random walks in pyramids, which by definition are cones formed by finite intersections of half-spaces. The main object of interest is the survival probability P(τ > n), τ denoting the first exit time from a fixed pyramid. When the drift belongs to the interior of the cone, the survival probability sequence converges to the non-exit probability P(τ = ∞), which is positive. In this note, we quantify the speed of convergence, and prove that the exponential rate of convergence may be computed by means of a certain min-max of the Laplace transform of the random walk increments. We illustrate our results with various examples.

Introduction and main results

A glimpse of our results. For a d-dimensional random walk (S n ) n⩾0 with integrable and independent increments X n = S n -S n-1 having common distribution µ, we consider the survival probabilities (1)

P x (τ > n),
where τ denotes the first exit time from a given cone K, i.e. τ = inf{n > 0|S n / ∈ K}, and P x is a probability distribution under which the random walk starts at S 0 = x, with x ∈ K.

When the drift m = EX 1 belongs to the interior K o of the cone K, the non-exit probability P x (τ = ∞), which is the limit of the sequence [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], is positive (see [START_REF] Garbit | The generating function of the survival probabilities in a cone is not rational[END_REF]Lem. 8] for example). In this note, our main result quantifies the speed of convergence in the following way:

(2)

P x (τ > n) = P x (τ = ∞) + ρ n B n ,
where the exponential rate ρ ∈ (0, 1), and B n satisfies n √ B n → 1 and B n → 0. The precise statement is given in Theorem 1 below. The rate ρ is computed in terms of a certain min-max of the Laplace transform of µ.

In the special case of small step walks in Z d (i.e. when the support of µ is a subset of {-1, 0, 1} d ) in the orthant Z d + , this result was previously obtained in [START_REF] Garbit | The generating function of the survival probabilities in a cone is not rational[END_REF]Thm 4].

K K * Figure 1.
A cone K (in red) and its dual cone K * (in blue)

In the present paper, we consider general probability distributions µ with all exponential moments and polyhedral convex cones, i.e. finite intersection of half-spaces, which for short we will call pyramids; see examples on Figures 1 and2.

One initial motivation to obtain formula [START_REF] Boyd | Convex Optimization[END_REF] is the following consequence on the generating function [START_REF] Feller | An Introduction to Probability Theory and Its Applications[END_REF] ϕ(z) =

∞ n=0 P x (τ > n)z n .
If the survival probabilities behave as in [START_REF] Boyd | Convex Optimization[END_REF], then the generating function [START_REF] Feller | An Introduction to Probability Theory and Its Applications[END_REF] can not be a rational function, as shown in [START_REF] Garbit | The generating function of the survival probabilities in a cone is not rational[END_REF] using singularity analysis. The question of proving rationality (and various refinements, such as algebraicity) of generating functions as above is inspired by the combinatorial work [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], where the rational nature of series as in ( 3) is used to measure the complexity of the associated combinatorial problem.

Technical assumptions. In order to present the hypotheses under which we shall prove our main results, we introduce two objects, through which the exponential rate ρ in (2) will be determined:

• the Laplace transform L of the increment distribution µ:

L(t) = E e ⟨t,X 1 ⟩ = R d
e ⟨t,y⟩ µ(dy),

• the dual cone K * associated with K (see Figure 1 for an example):

K * = {x ∈ R d |⟨x, y⟩ ⩾ 0 for all y ∈ K}.
Obviously, K * is a closed convex cone.

We will also use extensively the notation D u for the closed half-space with inner normal u ∈ S d-1 , i.e. D u = {y ∈ R d |⟨y, u⟩ ⩾ 0}. (A3) [Adaptation to the cone] The random walk started at zero can reach the interior K o of the cone: there exists k > 0 such that P 0 (τ > k, S k ∈ K o ) > 0. (A4) [Exponential moments] The random walk increments have all exponential moments. In other words, the Laplace transform is finite everywhere on R d . (A5) [Non-triviality] The random walk is not trapped in the cone: P(X 1 ∈ K) < 1. (If P(X 1 ∈ K) = 1, then P x (τ > n) = 1 for all n and there is nothing more to say.)

We call m = EX 1 = yµ(dy) the drift.

Precise statements. Our main result is the following:

Theorem 1. Assume hypotheses (A1)-(A5) above, K = ∩ u∈S D u , and m ∈ K o . The subset S ′ ⊂ S of directions u such that the equation L(su) = 1 has a solution s = s u < 0 is non-empty, and

P x (τ > n) = P x (τ = ∞) + ρ n B n , with (4) ρ = max u∈S ′ min z∈K * L(t u + z) ∈ (0, 1), where t u = s u u and B n satisfies n √ B n → 1 together with B n → 0.
Remark 2. Under the hypotheses of Theorem 1, the set S ′ is also characterized as being the subset of all u in S such that P(X 1 ∈ D u ) < 1. See Lemma 6 for a proof.

Remark 3. It might not be clear at first sight why the expression (4) for ρ doesn't depend on the set S as long as K = ∩ u∈S D u . The reason is that one set S 0 among such S is minimal with respect to inclusion, and any vector in S can be written as a non-negative linear combination of vectors in S 0 . This combined with further basic properties of the convex function t → min z∈K * L(t + z) makes it possible to deduce that the maximum on {t u |u ∈ S ′ } is reached on {t u |u ∈ S ′ 0 }. The set S 0 can be characterized as the set of extremal directions of K * . This is explained in Appendix A; its reading is not necessary for the understanding of the proof of Theorem 1.

Using similar singularity analysis technniques as in [START_REF] Garbit | The generating function of the survival probabilities in a cone is not rational[END_REF], the estimate obtained in Theorem 1 yields the following: Although we are not able to extend Theorem 1 to the case of cones which are not pyramids, we conjecture that the same conclusion holds, provided the formula (4) for ρ be replaced by

ρ = max t∈M min z∈K * L(t + z), where M = (-K * ) ∩ {L = 1} \ {0}.
The case of a drift m / ∈ K o is considered in [START_REF] Garbit | The generating function of the survival probabilities in a cone is not rational[END_REF], and our proof of Theorem 1 is based on that previous result, which we now state for convenience:

Theorem 5 (Theorem 3 in [START_REF] Garbit | The generating function of the survival probabilities in a cone is not rational[END_REF]). Assume hypotheses (A1)-(A4) above and that L is coercive on

K * . If m / ∈ K o , then P x (τ > n) = ρ n B n ,
where ρ = min z∈K * L(z) ∈ (0, 1], and B n satisfies n √ B n → 1 and B n → 0. Moreover ρ < 1 if and only if m / ∈ ∂K.

In Theorem 5 and throughout the manuscript, a non-negative, convex function f : R d → R is said to be coercive on a cone C if f (x) → +∞ as ∥x∥ → +∞, x ∈ C.

Examples of application of Theorem 1

In this section, we give various illustrations of Theorem 1. 1 below are small step walks in the plane, confined to the cone K = R 2 + , with uniform distribution. By definition, two-dimensional small step models have a support included in the set of the eight nearest neighbors {-1, 0, 1} 2 \ {(0, 0)}.

Small step examples with uniform distribution. All examples presented in Table

In Table 1, we use the notation of Theorem 1; for example, s (1,0) denotes the unique negative point such that L(s (1,0) , 0) = 1. We further introduce [START_REF] Garbit | The generating function of the survival probabilities in a cone is not rational[END_REF] ρ (1,0) = min

z∈R 2 + L(t (1,0) + z),
with t (1,0) = (s (1,0) , 0). The quantities s (0,1) and ρ (0,1) are defined similarly. The rate ρ is as in (4) and satisfies ρ = max{ρ (1,0) , ρ (0,1) }.

In the list of 79 intrinsically different models of walks in the quarter plane established in [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], exactly 12 of them have a drift inside of the quadrant. For each of these 12 models, we compute s (1,0) , ρ (1,0) , s (0,1) , ρ (0,1) , and finally the rate ρ appearing in Theorem 1. For the first model, the rate ρ is already computed in [START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF]Prop. 9]. The second, third and fourth rates are obtained in [START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF]Thm 3.1].

Among these 12 models, four of them have a support included in a half-plane. These models are considered in the four first rows of Table 1. Notice that the first column of Table 1 represents the steps of the random walk; it is implicitly assumed that the transition probabilities are uniform. For example, the first model has jump probabilities 1 3 in the directions (-1, 1), (1, 1) and (1, -1). The remaining 8 models have simultaneously a drift in the cone and a support which is not included in any half-plane. These models are represented on Table 1 as well. 1). We represent the level set {t ∈ R 2 |L(t) = 1} (red color), the drift (red), the translated cones t (1,0) + R 2 + (yellow) and t (0,1) + R 2 + (blue); the intersection of the two previous translated quadrants is the positive quarter plane (green). On the left display, the two points stand for the global minima in t (1,0) + R 2 + and t (0,1) + R 2 + . On the right display, the same minima points are drawn, as well as the global minimum on R 2 .

A weighted small step example.

We now look at a two-dimensional example with Laplace transform

(6) L(x, y) = p -1,1 e -x+y + p 0,1 e y + p 1,1 e x+y + p 1,0 e x + p 1,-1 e x-y ,
which is just a weighted version of the third step set on Table 1. We assume that the drift is in the interior of the quadrant, i.e.

(

) p -1,1 < p 1,1 + p 1,0 + p 1,-1 and p 1,-1 < p -1,1 + p 0,1 + p 1,1 7
and that p 0,1 + p 1,1 + p 1,0 > 0, so that the walk be truly 2-dimensional (hypothesis (A2)). If p -1,1 = p 1,-1 = 0, then the walk is trapped in the cone and

τ = ∞ almost surely. If both of Model s (1,0) ρ (1,0) s (0,1) ρ (0,1) ρ -log 2 2 √ 2 3 -log 2 √ 8 3 √ 3 [7] -log 2 1+2 √ 2 4 -log 2 1+2 √ 2 4 1+2 √ 2 [6]
-log 3

1+2 √ 3 5 -log 3 1+2 √ 3 5 1+2 √ 3 [6] -log 2 1+2 √ 2 4 -log 3 √ 3 2 1+2 √ 2 [6] -log 2 √ 8 3 -log 2 √ 8 3 √ 3 -log 2 1+2 √ 2 4 -log 2 1+2 √ 2 4 1+2 √ 2 -log 2 2+2 √ 2 5 -log 3 1+2 √ 3 5 2+2 √ 2 -log 2 2+2 √ 2 5
log( 23 )

2 √ 6 5 2 √ 5 -log 2 2+2 √ 2 5 -log 2 2+2 √ 2 5 2+2 √ 2 log( 2 3 ) 1+2 √ 6 6
-log 3

1+ √ 3 3 1+2 √ 6 log( 2 3 ) 1+2 √ 6 6
log( 23 )

1+2 √ 6 6 1+2 √ 6 log( 2 3 ) 2+2 √ 6 7 log( 2 3 ) 2+2 √ 6 7 2+2 √ 6
Table 1. Some important quadrant walk models considered in [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF][START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF][START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF] 6 + e -y 2 + e x+2y 3 .

p -1,1 , p 1,-1 are non-zero, then applying Theorem 1, we shall prove that

(8) ρ = max p 0,1 + 2 p -1,1 (p 1,1 + p 1,0 + p 1,-1 ), p 1,0 + 2 p 1,-1 (p -1,1 + p 0,1 + p 1,1
) .

The formula ( 8) is a generalization of [6, Thm 3.1] to weighted, non-symmetric step sets with Laplace transform [START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF]. If one of p -1,1 , p 1,-1 is zero (say p -1,1 ) and the other one is non-zero, then

ρ = p 1,0 + 2 p 1,-1 (p 0,1 + p 1,1 ). (9)
Proof of [START_REF] Studený | Convex cones in finite-dimensional real vector spaces[END_REF]. Applying Theorem 1 yields ρ = max ρ (1,0) , ρ (0,1) , with ρ (1,0) given by ( 5), and ρ (0,1) computed symmetrically. In order to derive [START_REF] Studený | Convex cones in finite-dimensional real vector spaces[END_REF], it is sufficient to show that

ρ (1,0) = p 0,1 + 2 p -1,1 (p 1,1 + p 1,0 + p 1,-1
). We first observe that ρ (1,0) is necessarily reached at some boundary point of t (1,0) +R 2 + . Indeed, if ρ (1,0) were reached at an interior point of t (1,0) +R 2 + , then it would be a global minimum of L on R 2 , which does not exist due to the fact that the step set is included in a half-space. Hence it is enough to compute

α = min{L(s (1,0) , y)|y ⩾ 0} and β = min{L(x, 0)|x ∈ [s (1,0) , ∞)}. The equation L(x, 0) = 1 writes (10) p -1,1 e -x + p 0,1 + (p 1,1 + p 1,0 + p 1,-1 ) e x = 1,
and is solved by

x = 0 and x = s (1,0) = ln p -1,1 p 1,1 + p 1,0 + p 1,-1 < 0.
Now we compute the partial derivative:

∂L ∂y (s (1,0) , 0) = p -1,1 e -s (1,0) + p 0,1 + p 1,1 e s (1,0) -p 1,-1 e s (1,0) = 1 -(p 0,1 + 2p 1,-1 )e s (1,0) ,
where the last equality is obtained thanks to (10). Because of (7), we have

p 0,1 + 2p 1,-1 < p 0,1 + p 1,-1 + p -1,1 + p 0,1 + p 1,1 = 1,
and e s (1,0) < 1. Therefore ∂L ∂y (s (1,0) , 0) > 0 and by convexity the partial function y → L(s (1,0) , y) is non-decreasing for y ⩾ 0. By consequence α = 1. Accordingly,

ρ (1,0) = β = min{L(x, 0)|x ∈ R}.
A straightforward computation then shows that the global minimum of a function of the form ae -x + b + ce x is reached at e x = a c and takes the value b + 2

√

ac. The proof of ( 8) is completed.

The formula ( 9) would be proved similarly, using that S ′ = {(0, 1)}. □

Irrelevance of the location of the drift.

In this paragraph, we would like to illustrate the following fact: the position of the drift (in particular its distance to the boundary) does not in general determine which point in S ′ will give the rate ρ.

Let us take three examples in the case of the quarter plane. For the first model in Table 1, the model is symmetric (about the first diagonal), with drift

( 1 3 , 1
3 ), and one has ρ = ρ (1,0) = ρ (0,1) . Consider now the fourth model in Table 1. Its drift is ( 1 4 , 1 2 ), closer to the vertical axis. The rate is given by ρ (1,0) , as shown in Table 1. Finally, look at the model represented on Figure 4, which has a drift of the form ( 1 6 , 1 6 ). Easy computations show that ρ (1,0) ≈ 0.97, which turns out to be the global minimum of L on R 2 , while ρ (0,1) ≈ 0.99. By continuity w.r.t. the parameters, this last example could be modified to get an example with a drift slightly directed to the vertical axis, but for which the rate ρ would be actually equal to ρ (0,1) .

Normal distribution.

Here we consider the case where the step distribution µ is a standard normal distribution on R d with mean m. The Laplace transform is then given by ( 11)

L(t) = exp ⟨t, m⟩ + ∥t∥ 2 2 = exp ∥t + m∥ 2 -∥m∥ 2 2 .
Let us first recall an explicit expression for the minimum of L on the closed convex cone K * . It is clearly reached when t is the projection of -m on K * , and then

∥t + m∥ = d(-m, K * ) = d(m, K ♯ ),
where 11), we see that Γ is the circle C(-m, ∥m∥) with center at -m and radius ∥m∥, see Figure 5. For t ∈ Γ, we have

K ♯ = -K * is the polar cone of K. By Moreau's decomposition theorem d(m, K ♯ ) 2 + d(m, K) 2 = ∥m∥ 2 , therefore the minimum of L on K * is exp -1 2 d(m, K) 2 . Now consider the set Γ = {t ∈ R 2 |L(t) = 1}. From (
L(t + z) = exp ∥z + t + m∥ 2 -∥t + m∥ 2 2
min z∈K * L(t + z) = exp - 1 2 d(t + m, K) 2 .
For a closed pyramid K = ∩ u∈S D u containing m in its interior, the set S ′ is equal to S (see Remark 2) and the rate ρ is given by

ρ = max u∈S exp - 1 2 d(t u + m, K) 2 = exp - 1 2 min u∈S d(z u , K) 2 ,
where z u = t u + m is characterized as being the unique intersection point of the circle C(0, ∥m∥) and the half-line {su + m|s < 0}.

For example, consider the cone K = {ρ(cos θ, sin θ)|ρ ⩾ 0, θ ∈ [0, α]} in the plane and m = r(cos β, sin β), with 0 < β < α ⩽ π. Then K = D u ∩ D v with u = (0, 1) and v = (sin α, -cos α). Some computations show that z u = r(cos β, -sin β) and z v = r(cos(2α -β), sin(2α -β)). From this, we obtain ρ = e -d 2 /2 with d = r min sin β, sin(α -β) . Note that in this example, d equals the distance between m and ∂K.

Proof of Theorem 1

3.1. Sketch of the proof. Let K = ∩ u∈S D u be a closed pyramid. We want to estimate

∆ n = P x (τ > n) -P x (τ = ∞) = P x (n < τ < ∞).
By the geometry of K, we have {τ < ∞} = ∪ u∈S {σ u < ∞}, where σ u denotes the first exit time from the half-space D u , therefore

max u∈S P x (n < τ, σ u < ∞) ⩽ ∆ n ⩽ u∈S P x (n < τ, σ u < ∞).
If u is such that P(X 1 ∈ D u ) = 1, then the random walk can not leave the half-space D u and P x (n < τ, σ u < ∞) = 0. So we can rewrite the preceding relation as

max u∈S ′ P x (n < τ, σ u < ∞) ⩽ ∆ n ⩽ u∈S ′ P x (n < τ, σ u < ∞),
where S ′ is the subset of all u ∈ S satisfying P(X 1 ∈ D u ) < 1. We shall see that those simple bounds are sufficient to obtain our estimate on ∆ n . Estimates of each term P x (n < τ, σ u < ∞) are obtained in Lemma 9. Theorem 1 then follows immediately. Lemmas 6 and 8 are preparatory material.

3.2.

Turning the drit inside out. The Laplace transform of a vector X = (X (1) , . . . , X (d) ) ∈ R d with probability distribution µ is the function L defined for t ∈ R d by

L(t) = E e ⟨t,X⟩ = R d e ⟨t,y⟩ µ(dy).
It is finite in some neighborhood of the origin if and only if E e α∥X∥ is finite for some α > 0. If L is finite in a neighborhood of the origin, say B(0, r), then L is infinitely differentiable in B(0, r) and its partial derivatives are given there by ∂L(t) ∂t i = E X (i) e ⟨t,X⟩ .

Therefore, the expectation EX = (EX (1) , . . . , EX (d) ) is the gradient of L at the origin ∇L(0). Notice that X is centered (i.e. EX = 0) if and only if 0 is a critical point of L. Since L is a convex function, this means that 0 is a minimum point of L in B(0, r). Now suppose that L is finite in some ball B(t 0 , r) and define a new probability measure µ * by (12) µ * (dy) = e ⟨t 0 ,y⟩ L(t 0 ) µ(dy).

We will say that µ * is the t 0 -changed measure. The Laplace transform L * of µ * is linked to that of µ by the relation L * (t) = L(t 0 + t)/L(t 0 ), and therefore L * is finite in some neighborhood of the origin. As a consequence, applying the results above shows that any random vector X * with distribution µ * satisfies:

• E e α∥X * ∥ < ∞ for some α > 0;

• EX * = ∇L(t 0 )/L(t 0 ).

For specific points t 0 satisfying the equation L(t 0 ) = 1, we obtain additional information on the new drift: Lemma 6. Assume hypotheses (A1), (A2), (A4), (A5) above, K = ∩ u∈S D u , and m ∈ K o . Then the subset S ′ ⊂ S of directions u such that the equation L(su) = 1 has a solution s = s u < 0 is non-empty and equal to the set of all u ∈ S such that P(X 1 ∈ D u ) < 1. In addition, for any u ∈ S ′ , the gradient of L at the point t u = s u u satisfies ⟨∇L(t u ), u⟩ < 0.

Remark 7.

In other words, under the t u -changed measure, the new drift does not belong to the half-space

D u = {z ∈ R d |⟨z, u⟩ ⩾ 0}.
Proof. First, we note that ⟨m, u⟩ > 0 for all non-zero u ∈ K * . Indeed, if C is a closed cone, the interior of its dual cone has the following description: [START_REF] Boyd | Convex Optimization[END_REF] for example. Since K is a closed convex cone, it is well known that (K * ) * = K (see Consequence 1 in [START_REF] Studený | Convex cones in finite-dimensional real vector spaces[END_REF] or Theorem 14.1 in [START_REF] Rockafellar | Convex Analysis[END_REF]). Applying this to C = K * , we see that the interior of K can be expressed as

(C * ) o = y ∈ R d |⟨y, u⟩ > 0 for all u ∈ C \ {0} , see Exercise 2.31(d) in
K o = y ∈ R d |⟨y, u⟩ > 0 for all u ∈ K * \ {0} .
This proves the first assertion. Let u ∈ S. By definition one has K ⊂ D u , thus u ∈ K * . Consider the partial function of a real variable ϕ(s) = L(su). This function is C ∞ and strictly convex, since the Laplace transform is C ∞ thanks to (A2) and strictly convex thanks to (A4). Its derivative is given by ϕ ′ (s) = ⟨∇L(su), u⟩, hence ϕ ′ (0) = ⟨m, u⟩ > 0. Based on [START_REF] Garbit | On the exit time from a cone for random walks with drift[END_REF]Lem. 6], the following dichotomy holds:

• If P(X 1 ∈ D u ) < 1, then lim s→-∞ ϕ(s) = ∞.
Since ϕ is strictly convex and satisfies ϕ(0) = 1 and ϕ ′ (0) > 0, there exists a unique s < 0 such that ϕ(s) = 1. Moreover, at this point, the derivative ϕ ′ (s) must be negative. Hence L(su) = 1 and ⟨∇L(su), u⟩ < 0.

• If P(X 1 ∈ D u ) = 1, then lim s→-∞ ϕ(s) = P(⟨X 1 , u⟩ = 0) < 1.
In this case, the equation ϕ(s) = 1 has no solution s < 0.

Since P(X 1 ∈ K) < 1 by (A5) and K = ∩ u∈S D u with S finite, there is at least one u ∈ S such that P(X 1 ∈ D u ) < 1. Therefore S ′ is non-empty. □ 3.3. Change of measure. Let t 0 be given and consider the t 0 -changed measure (12). We shall denote by P x * a probability distribution under which (S n ) n⩾0 is a random walk with increment distribution µ * and started at S 0 = x. It is easily checked that (13)

E x f (S 1 , S 2 , . . . , S k ) = L(t 0 ) k e ⟨t 0 ,x⟩ E x * f (S 1 , S 2 , . . . , S k )e -⟨t 0 ,S k ⟩ ,
for any non-negative measurable function f : R k → [0, ∞).

Lemma 8. Assume L(t 0 ) = 1, and let τ and σ be two stopping times w.r.t. the natural filtration associated with (S n ) n⩾0 . Then

(14) P x (n < τ ⩽ σ < ∞) = e ⟨t 0 ,x⟩ E x * n < τ ⩽ σ < ∞, e -⟨t 0 ,Sσ⟩ .
Proof. For all k > n, applying (13) gives

P x (n < τ ⩽ σ = k) = e ⟨t 0 ,x⟩ E x * n < τ ⩽ σ = k, e -⟨t 0 ,S k ⟩ = e ⟨t 0 ,x⟩ E x * n < τ ⩽ σ = k, e -⟨t 0 ,Sσ⟩ .
By summing over k > n, we obtain (14). □

• Finally, it remains to check that L * is coercive on the dual cone K * . Fix v ∈ K * and recall from [START_REF] Garbit | On the exit time from a cone for random walks with drift[END_REF]Lem. 6] that lim t→∞ L * (tv) = ∞ if and only if the support of µ * is not included in -D v . But µ and µ * have the same support which is not included in -D v , for else the original drift m would also be in -D v . This is impossible since m ∈ K o and

-D v ∩ K o = ∅.
It follows from Theorem 5 that

P x * (τ > n) = ρ n u B n , where B n satisfies n √ B n → 1 and B n → 0, and
ρ u = min z∈K * L(t u + z) ∈ (0, 1). (ρ u < 1 since m * ̸ ∈ K, see Theorem 5.
) This concludes the proof of the lemma. □

We end this section with a result on overshoots of a random walk that is uniform w.r.t. the starting point.

Lemma 10 (Overshoot). Let (Z n ) n⩾0 be a one-dimensional random walk with integrable i.i.d. increments Y k satisfying EY k > 0. Let T denote the first exit time from the half-line (-∞, 0]. For any continuous, non-increasing function f : [0, ∞) → (0, ∞), we have

0 < inf x⩽0 E x f (Z T ) ⩽ sup x⩽0 E x f (Z T ) < ∞.
Proof. Since the random walk has positive drift, the exit time T is almost surely finite, furthermore E x T < ∞ for all x ⩽ 0. Since Z T > 0 and f is non-increasing, we have E x f (Z T ) ⩽ f (0) for all x ⩽ 0. This proves the rightmost inequality of Lemma 10.

We now turn to the leftmost inequality side, which is the difficult part. Since

E x f (Z T ) ⩾ E x (f (Z T ), Z T ⩽ a) ⩾ f (a)P x (Z T ⩽ a), it suffices to find a > 0 such that inf x⩽0 P x (Z T ⩽ a) > 0.
We shall first exhibit a lower bound when x remains in a bounded interval [b, 0], b < 0. To do this, simply write

P x (Z T > a) = n⩾1 P x (Z n > a, T = n) ⩽ n⩾1 P x (Y n > a, T > n -1) = P(Y 1 > a)E x T.
Let b be an arbitrary negative number. Since E x T is non-increasing as x ↑ 0, we have

sup b⩽x⩽0 P x (Z T > a) ⩽ P(Y 1 > a)E b T.
Choosing a > 0 such that P(Y 1 > a)E b T < 1, we obtain inf b⩽x⩽0 P x (Z T ⩽ a) > 0.

It remains to lower bound E x f (Z T ) for large negative x. To do this, we use a well-known consequence of the renewal theorem, which asserts that the overshoot Z T above 0 converges in distribution as the initial state x goes to -∞. To state this result precisely, let us introduce the ladder epochs (T k ) k⩾0 defined by

T 0 = 0 and T k+1 = inf{n > T k |Z n > Z T k }, k ⩾ 0,
and the corresponding ladder heights H k = Z T k . It is clear that our exit time T must occur at one of the ladder epochs, hence Z T = H τ + , where τ + = inf{n > 0|H n > 0}. Now

H n = Z 0 + n k=1 (Z T k -Z T k-1 ),
where the random variables Z T k -Z T k-1 are i.i.d. and positive. According to [3, XI.4, Eq. (4.10), p. 370], the overshoot H τ + above 0 of the renewal process (H n ) n⩾0 converges in distribution as x → -∞. More precisely, if the distribution of the ladder heights increments Z T k -Z T k-1 is non-arithmetic1, then for any bounded and continuous function f

: [0, ∞) → R, lim x→-∞ E x f (H τ + ) = 1 ν ∞ 0 f (t)G(t)dt,
where G is the survival function of Z T k -Z T k-1 and ν is its expectation. Since the variable Z T k -Z T k-1 is positive and our function f is also positive, the integral above is positive.

In case the distribution of

Z T k -Z T k-1 is arithmetic with span λ > 0, then lim n→-∞ E nλ f (H τ + ) = λ ν ∞ k=0 f ((k + 1)λ)G(kλ).
The proof is exactly as that of [3, XI.4, Eq. (4.10), p. 370], when specialized to the case of arithmetic distributions, see [3, XI.1, Eq. (1.19), p. 362]2. Here again the limit is positive, since at least G(0) > 0. So, there exists n 0 < 0 such that inf n<n 0 E nλ f (H τ + ) > 0. Now, for n < 0 and x ∈ ((n -1)λ, nλ], the exit time τ + when the process is started at x is identical to that when started at nλ, hence

E x f (H τ + ) = E nλ f (H τ + -(nλ -x)) ⩾ E nλ f (H τ + ).
Therefore inf x<n 0 λ E x f (H τ + ) > 0. □ Appendix A. Properties of pyramids and proof of Remark 3

The main objective of the appendix is to prove that the value of ρ in Theorem 1 doesn't depend on the set S as long as K = ∩ u∈S D u , as mentioned in Remark 3. Along the way of showing this, we shall recall several statements on pyramids. To make the paper self-contained and for the convenience of the reader, we will briefly prove these technical results.

Recall that a subset K of R d is a closed pyramid if there is a finite subset S of the sphere S d-1 such that K = ∩ u∈S D u , where D u stands for the closed half-space {y ∈ R d |⟨y, u⟩ ⩾ 0}, see Figure 2. In other words, K is a finite intersection of homogeneous closed half-spaces. A closed pyramid is clearly a closed convex cone.

1A probability distribution is arithmetic if it is concentrated on λZ for some λ > 0. In this case, the largest λ with this property is called the span.

2Note that there is a misprint in [3, XI.1, Eq. (1.19), p. 362]: for x ∈ [0, λ), the indices j should start at 0.

In this section, we will show (Lemma 12) the following straightforward-looking result: if K is a closed pyramid with non-empty interior3, there is a finite set S 0 such that K = ∩ u∈S 0 D u and S 0 is minimal w.r.t. inclusion, i.e.

K = ∩ u∈S D u ⇒ S 0 ⊂ S.
From this, we will deduce (Lemma 13) that (15)

max u∈S ′ min z∈K * L(t u + z) = max u∈S ′ 0 min z∈K * L(t u + z),
thus explaining why the expression for ρ in Theorem 1 doesn't depend on the particular choice of the set S, provided that K = ∩ u∈S D u .

A.1. Some facts about pyramids. To begin, let K be any non-empty closed convex cone. It is well known that K is the intersection of the homogeneous closed half-spaces D u which contain it (see [START_REF] Rockafellar | Convex Analysis[END_REF]Cor. 11.7.1]). Since the condition K ⊂ D u is clearly equivalent to u ∈ K * , it follows that

K = u∈K * D u .
From now on, we will assume K has a non-empty interior and focus on the structure of the dual cone K * . Since K contains a ball B(x 0 , r), any non-zero y ∈ K * satisfies ⟨y, x 0 + ru⟩ ⩾ 0 for all u ∈ S d-1 , and this condition is equivalent to ⟨y, x 0 ⟩ ⩾ r∥y∥. This implies that the cone C = K * is salient, i.e. there exists v ∈ S d-1 such that ⟨y, v⟩ > 0 for all y ∈ C \ {0}.

Salient convex cones have the following property: Take H as in the lemma above and denote by E the set of extreme points of the convex set C ∩ H (see Figure 6). Since C ∩ H is compact, it follows from Minkowski-Steinitz Theorem (see [START_REF] Rockafellar | Convex Analysis[END_REF]Cor. 18.5.1]) that any of its points a can be written as a convex combination of extreme points:

a = p i=1 λ i a i , with a i ∈ E, λ i ⩾ 0 and p i=1 λ i = 1.
From this we define the set of extremal directions of C as

E d (C) = a/∥a∥ | a ∈ E .
It can be seen that this set does not depend on the particular choice of H, and has the following intrisic characterisation: u ∈ S d-1 is an extremal direction of C if and only if it can not be written 3The result is not true in general if the interior of K is empty. Consider for example the cone

K = {0} × [0, ∞) in R 2 .
It can be written as ∩u∈SDu, with S = {(1, 0), (-1, 0), (0, 1)}, and this S is minimal w.r.t. cardinality, but S = {(1, 0), (-1, 0), (1/ √ 2, 1/ √ 2)} is adapted to K as well.

µ i u i , with u i ∈ E d (C) and µ i ⩾ 0. This implies D u ⊃ D u 1 ∩ D u 2 ∩ • • • ∩ D up .
Applying this to the salient cone K * , we obtain the following representation for K:

(16) K = u∈K * D u = u∈E d (K * ) D u . Lemma
D u i = K.
Since A is a closed convex cone, A = (A * ) * = K * , see Consequence 1 in [START_REF] Studený | Convex cones in finite-dimensional real vector spaces[END_REF] or [START_REF] Rockafellar | Convex Analysis[END_REF]Thm 14.1]. Now, it is easily seen, using the intrisic characterisation of an extremal direction together with the minimality of the set T , that any extremal direction of A must be one of the u i 's. Therefore E d (K * ) is a subset of T , hence finite. (In fact, by minimality T = E d (K * ).) Any vector in S is a non-negative linear combination of vectors of E d (K * ), as S is necessarily a subset of K * . □ A.2. Proof of Remark 3. We first prove a technical result, which exactly captures the situation encountered in Theorem 1.

Lemma 13. Let K be a closed pyramid with non-empty interior and F, G : K * → R two convex functions such that:

• F (0) = 1 and for all u ∈ K * \ {0}, either the equation F (su) = 1 with s > 0 has exactly one solution or F (su) < 1 for all s > 0; • G is non-increasing along the rays of the cone K * . Let M = K * ∩ {F = 1} \ {0}. If M is non-empty, the maximum of G on M is reached at some point z in M such that u = z/∥z∥ is an extremal direction of K * .

Proof. Let A be the collection of u ∈ E d (K * ) such that the equation L(su) = 1 with s > 0 has exactly one solution, and let B = E d (K * ) \ A. By hypothesis, if u belongs to B, then L(su) < 1 for all s > 0. We first show that A is non-empty, so that there exists at least one point z = su in M such that z/∥z∥ ∈ E d (K * ). To see this, let x be any point in M . As an element of K * , it can be written as a linear combination This contradicts with F (x) = 1, hence A is non-empty.

For each u ∈ A, denote by x u the unique point such that F (x u ) = 1 and x u = su with s > 0. Starting from (17), we can decompose x as follows:

x = u∈A µ u x u + u∈B λ u u,
where µ u ⩾ 0 and λ u ⩾ 0. Set µ = u∈A µ u , λ = u∈B λ u and c ε = µ + ελ, for a parameter ε > 0. Repeating the argument above shows that at least one of the µ u is positive, hence µ > 0 and c ε > 0. By convexity of F , we have

F (x/c ε ) = F u∈A µ u c ε x u + u∈B ελ u c ε (u/ε) ⩽ u∈A µ u c ε F (x u ) + u∈B ελ u c ε F (u/ε) ⩽ 1.
But, by hypothesis, the function ϕ(s) = F (sx) is convex and the equation ϕ(s) = 1 has only two non-negative solutions, namely s = 0 and s = 1, thus ϕ(s) > 1 for all s > 1. Therefore c ε must be larger than one. So, since G is non-increasing along the rays of K * , the value G(x) is less than

Figure 2 .

 2 Figure 2. Examples of (truncated) pyramids in dimension 3

Corollary 4 .

 4 Assume hypotheses (A1)-(A5) above, K = ∩ u∈S D u , and m ∈ K o . Then the generating function (3) is not rational.

Figure 3 .

 3 Figure 3. On the left (right), the first example ofTable1(the nineth example of Table1). We represent the level set {t ∈ R 2 |L(t) = 1} (red color), the drift (red), the translated cones t (1,0) + R 2 + (yellow) and t (0,1) + R 2 + (blue); the intersection of the two previous translated quadrants is the positive quarter plane (green). On the left display, the two points stand for the global minima in t (1,0) + R 2 + and t (0,1) + R 2 + . On the right display, the same minima points are drawn, as well as the global minimum on R 2 .

Figure 4 .

 4 Figure 4. This figure contains two examples, which are complementary to those of Figure 3. On the left, a model with step set included in a half-space. The Laplace transform does not admit a minimum in the direction (1, 0), so according to Theorem 1, S ′ = {(0, 1)} and ρ is computed as the global minimum on t (0,1) + R 2 + . On the right, the model with Laplace transform L(x, y) = e -x

Figure 5 .

 5 Figure 5. This figure summarizes the results presented in Subsection 2.4. The equation L(t) = 1 describes a circle with center at c = -m and radius r = ∥m∥. The cone K is represented in blue and the polar cone in green. In pink, we have represented one of the two domains t u + K * .

Lemma 11 .

 11 If a closed convex cone C is salient, then there exists an affine hyperplane H, not containing the origin, such that C ∩ H is compact and generates C, i.e. C = {λy|λ ⩾ 0, y ∈ C ∩ H}). Proof. The set C ∩S d-1 is compact and generates C. Consider the affine hyperplane H = v+[v] ⊥ , where v is as in the definition of a salient cone. The mapping ϕ : C ∩ S d-1 → C ∩ H given by ϕ(y) = y/⟨y, v⟩ is continuous and onto, therefore C ∩ S d-1 is compact. Moreover C ∩ H generates C, since any non-zero y in C can be written as y = λϕ(y) with λ = ⟨y, v⟩. □

Figure 6 .

 6 Figure 6. A salient cone C and the extreme points (in red) of C ∩ H

FF

  d (K * ) λ u u with λ u ⩾ 0. Assume A is empty and let n denote the cardinality of B. Then, by convexity of F , (nλ u u) < 1.

Table 1 (the nineth example of Table

 1

Acknowledgments

We would like to thank Marc Peigné for interesting discussions on overshoots of random walks. We warmly thank an anonymous referee for their thorough reading and their interesting comments and suggestions.

of random walksThis work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under the Grant Agreement No. 759702, from Centre Henri Lebesgue, programme ANR-11-LABX-0020-0 and from the project DeRerumNatura, programme ANR-19-CE40-0018.

By specializing this relation to the exit time τ from the cone K = ∩ u∈S D u and the exit time σ u from one half-space D u , we shall obtain the following: Lemma 9. Assume hypotheses (A1)-(A5), K = ∩ u∈S D u , and m ∈ K o . For all u ∈ S ′ ,

where B n satisfies n √ B n → 1 and B n → 0, and

where t u = su is the unique solution to L(su) = 1 with s < 0.

Proof. Fix u ∈ S ′ and let t u be as in the statement of Lemma 6. Then the drift m * = ∇L(t u ) of the random walk under P x * satisfies ⟨u, m * ⟩ < 0, so that σ u is almost surely finite and the relation (14) of Lemma 8 gives

where we have set

Let us focus on ϕ(y) for y ∈ K. Under P y * , the projected random walk Z n = ⟨-u, S n ⟩ is started at y = ⟨-u, y⟩ ⩽ 0 and has a positive drift ⟨-u, m * ⟩ > 0. The random time σ u corresponds to its first exit time T from the negative half-line (-∞, 0] and therefore ϕ(y) is the expectation of f (Z T ) when the random walk is started at y ⩽ 0, where f (t) = e sut is continuous and non-increasing. So, it follows from Lemma 10 below that the function ϕ(y) is bounded from above and below on the cone K by two positive constants 0 < c < C. Therefore

As a last step, we apply Theorem 5 to estimate P x * (τ > n). Let us see why the hypotheses of this theorem are satisfied under P * , i.e. by our new random walk with increment distribution µ * (dy) = e ⟨tu,y⟩ µ(dy) and Laplace transform L * (t) = L(t u + t):

(A1) The cone hasn't changed. (A2) The random walk is truly d-dimensional, since this condition depends only on the support of µ * (it should not be included in any linear hyperplane) and its support is exactly the same as that of µ. (A3) For the same reason, the new random walk inherits from the original random walk the property that it can reach the interior of the cone. This can be seen via ( 13). (A4) The Laplace transform L * (t) = L(t u +t) is finite everywhere, since L is finite everywhere.

• The new drift m * is not in K, since ⟨m * , u⟩ < 0 and K ⊂ D u .

G(x/c ε ), and using the convexity exactly as above we obtain

As ε goes to 0, c ε goes to µ and max u∈B G(u/ε) remains bounded (by max u∈B G(u) for ε < 1 for example). Therefore, letting ε → 0 in the inequality above leads to

This proves the lemma. □

As an application, let K = ∩ u∈S D u be a closed pyramid with non-empty interior and L be the Laplace transform of the distribution µ satisfying the hypotheses of Theorem 1. Set

The proof of Lemma 6 shows that the function F satisfies the first hypothesis of Lemma 13 and that M is non-empty. Now G is also a convex function (because L is convex). To see why it is non-increasing along the rays of K * , fix v ∈ K * and a < b. Since K * is a convex cone, it is also a semi-group, therefore (b -a)v + K * ⊂ K * , and adding -bv on each side leads to

Now define T as the set of all u in K * such that the equation F (su) = 1 with s > 0 has exactly one solution, which we write -α u with α u < 0. Then t u = α u u denotes the same point as in Theorem 1 because L(α u u) = F (-α u u) = 1. The set M in Lemma 13 is equal to {-t u |u ∈ T } and the lemma asserts that max{G(-t u )|u ∈ T } = max{G(-t u )|u ∈ T ∩ E d (K * )}. But the set S ′ in Theorem 1 satisfies

More explicitly, max

This explains (15).


Photios A Stavrou
email: fotios.stavrou@eurecom.fr

Marios Kountouris
email: marios.kountouris@eurecom.fr

Goal-Oriented Single-Letter Codes for Lossy Joint Source-Channel Coding

A new variation of the classical point-to-point joint source-channel coding (JSCC) is studied here, which is relevant for identifying goal-oriented semantic aspects of a transmitted source message over a noisy channel. For this new formulation, coined goal-oriented JSCC, we first introduce optimality criteria followed by necessary and sufficient conditions for global optimality. The focus of our main theoretical results is on investigating the implications of a special subclass of block codes, namely, the single-letter codes, via a theorem in which we provide necessary and sufficient conditions for the probabilistic matching of a goal-oriented source message with a noisy channel. We corroborate our theoretical results with two examples, in which goal-oriented single-letter codes and uncoded transmission perform optimally. Our results further highlight the important role of multiple fidelity constraints in goal-oriented communications.

I. INTRODUCTION

Goal-oriented semantic communication has recently received a growing interest from various research communities spanning from information and communication theory [START_REF] Kountouris | Semantics-empowered communication for networked intelligent systems[END_REF], [START_REF] Gündüz | Beyond transmitting bits: Context, semantics, and task-oriented communications[END_REF], game theory [START_REF] Güler | The semantic communication game[END_REF], control theory [START_REF] Wang | Value of information in networked control systems subject to delay[END_REF] to networking [START_REF] Popovski | Semantic-effectiveness filtering and control for post-5G wireless connectivity[END_REF]. The main motivation behind this in the vast majority of the literature, at least in the area of information and communication theory, can be found in Shannon's seminal work [START_REF] Shannon | A mathematical theory of communication[END_REF]. A key claim therein is that the fundamental problem of communication ought to deliberately disregard the semantic aspects of a message and its impact. Although this argument is valid and relevant in general, a goal-oriented semantic theory of information transmission with tangible applications to communication systems is still an open quest.

In this work, we consider a variant of the classical pointto-point JSCC model in which a remote semantic source is indirectly observed by a transmitter via an observable message and conveyed across a noisy channel whereas at the destination, the goal is for both the remote and observable messages to be received as accurate as possible depending on some fidelity constraints. Here we furnish the semantic and observations sources with single-letter distortion constraints responsible to penalize their transmission rates. Our setup possess goal-oriented attributes and intrinsic representation of information (e.g., features, structural and qualitative properties, embedding) because the presence of fidelity constraints, dictates whether it makes sense to recover the remote or observable messages or both.

The fundamental study of JSCC dates back to [START_REF] Shannon | A mathematical theory of communication[END_REF]. Although a general definite solution to this problem appears to be elusive, the convenient result of source-channel separation principle for point-to-point stationary and ergodic systems enables for modularity between the source and channel coding schemes without any loss of optimality [START_REF] Shannon | A mathematical theory of communication[END_REF]- [START_REF] Csiszár | Information Theory: Coding Theorems for Discrete Memoryless Systems[END_REF]. Unfortunately, this result does not scale to networks without loss of optimality. In practice, a tandem source-channel coding necessitates non-causal knowledge of all the message signals hence entailing large coding delays and very complex coders. Surprisingly, the tandem scheme of Shannon is not unique for the fundamental communication problem. In fact, as two counterexamples suggest in [START_REF] Goblick | Theoretical limitations on the transmission of data from analog sources[END_REF], [START_REF] Jelinek | Probabilistic Information Theory: discrete and memoryless models[END_REF], single-letter codes and uncoded transmission, may provide significant gains to the end-to-end communication system in terms of coding delays, complexity and robustness. For a detailed analysis on necessary and sufficient conditions that need to be satisfied for any discrete-time memoryless point-to-point communication system to be optimal we refer to [START_REF] Gastpar | To code, or not to code: lossy source-channel communication revisited[END_REF] (and the references therein). Contributions. The goal-oriented lossy JSCC setup proposed herein is new and can be seen as a non-trivial generalization of the goal-oriented lossy source coding setup proposed in [START_REF] Liu | A rate-distortion framework for characterizing semantic information[END_REF], [START_REF] Stavrou | A rate distortion approach to goaloriented communication[END_REF]. Compared to that setup, communication takes place here over noisy instead of noiseless channels. We also define a variant of source-channel codes, which we refer to as goal-oriented codes. Additionally, we derive necessary and sufficient conditions for global optimality of the specific goaloriented JSCC scheme (Lemma 2). More importantly, we study the criteria needed for the optimality of goal-oriented single-letter codes using a known lower bound on the so called semantic rate distortion function (SRDF) (Lemma 1). Provided that SRDF is a tight bound, we derive necessary and sufficient conditions for optimality of our JSCC scheme (Theorem 1, Corollary 1). Our theoretical findings are corroborated with two application examples, in which single-letter codes and uncoded transmission perform optimally (Section V). These examples are extensions to the celebrated ones introduced for binary sources and binary symmetric channels (BSC) [START_REF] Jelinek | Probabilistic Information Theory: discrete and memoryless models[END_REF] and Gaussian i.i.d sources and additive white Gaussian noise (AWGN) channels [START_REF] Goblick | Theoretical limitations on the transmission of data from analog sources[END_REF]. The key takeaway is that in goal-oriented communications, selecting the type of individual distortion measures according to the application/task requirements can significantly affect the choice of the recovered message over noisy channels.

II. PROBLEM STATEMENT

We consider a memoryless source described by the tuple (x, z) with probability distribution p(x, z) in the product space X × Z. The semantic or intrinsic information of the source is in x, which can only be indirectly observed, whereas z is the noisy observation of the source at the encoder side. We also consider a memoryless noisy channel described by the conditional probability distribution p(b|a) where (a, b) ∈ A × B.

Formally, the generic source-channel communication model is illustrated in Fig. 1. According to this setup, we can model the information source as a sequence of n-length i.i.d random variables (x n , z n ) and we assume that we know p(x) and the transition probability distribution p(z|x). The noisy channel is assumed to be given, with known capacity and capacity achieving distribution p(a m ). Since the source and channel have different cardinality to their respective alphabets, this means that the sequence of m-length random variables (a m , b m ) and the reproduction sequence of n-length random variables ( x n , z n ) need not be i.i.d, in general. Definition 1. (Goal-oriented block source-channel codes) The source-channel encoder (E) and decoder (D), are modeled by the mappings

f E : Z n → A m g D o : B m → Z n , g D s : B m → X n (1)
where (g D o , g D s ) denote the observations and the semantic information decoder, respectively. The coding rate κ is the number of source symbols that have to be transmitted per channel use and is given by κ = n m . We consider two per-letter distortion measures responsible to penalize the semantic and observation information source given by d

Source/Channel Encoder

s : X × X → [0, ∞) and d o : Z × Z → [0, ∞),
respectively, a cost to possibly penalize the channel given by c : A → [0, ∞), and their corresponding average per-letter distortions and cost by

d n s (x n , x n ) = 1 n n t=1 d s (x i , x i ) (2)
d n o (z n , z n ) = 1 n n t=1 d o (z i , z i ) (3) c m (a m ) = 1 m m t=1 c(a i ). (4)
The average distortion for the semantic information and the observations is defined as

∆ s ≜ E {d n s (x n , x n )} , ∆ o ≜ E {d n o (z n , z n )} (5)
while the average cost for the noisy channel is defined as

Γ ≜ E {c m (a m )} . (6)
The main objecive of this work is to study necessary and sufficient conditions for the optimality of the goal-oriented JSCC setup of Fig. 1.

III. OPTIMALITY CONDITIONS OF THE SETUP IN FIG. 1

To provide the main result of this section, we need to recall some results from [START_REF] Stavrou | A rate distortion approach to goaloriented communication[END_REF] on goal-oriented compression, and on constrained/unconstrained channel capacity [START_REF] Gallager | Information Theory and Reliable Communication[END_REF].

We start with the definition of the SRDF.

Definition 2. (SRDF) [13, Lemma 1] For a given se- mantic/observation source (p(x), p(z|x), d s , d o ), the ergodic SRDF is characterized as follows 1 R(D o , D s ) = min q( z, x|z) E[ ds(z, x)]≤Ds E[do(z, z)]≤Do I(z; z, x) (7)
where

d s (z, x) = x∈X p(x|z)d s (x, x), D s ∈ [D min s , D max s ] ⊂ [0, ∞), D o ∈ [D min o , D max o ] ⊂ [0, ∞).
We note that (7) has similar functional and topological properties as in classical rate distortion theory [START_REF] Berger | Rate Distortion Theory: A Mathematical Basis for Data Compression[END_REF], e.g., monotonicity, continuity, convexity etc.

One interesting result that stems from ( 7) is the following lower bound. Lemma 1. (Lower Bound) [13, Lemma 2] The characterization in (7) admits the following lower bound: [START_REF] Csiszár | Information Theory: Coding Theorems for Discrete Memoryless Systems[END_REF] where (R(D s ), R(D o )) represents the standard direct [START_REF] Berger | Rate Distortion Theory: A Mathematical Basis for Data Compression[END_REF] and indirect RDFs [START_REF] Berger | Rate Distortion Theory: A Mathematical Basis for Data Compression[END_REF], [START_REF] Dobrushin | Information transmission with additional noise[END_REF] subject to their individual distortion criteria, i.e.,

R L (D o , D s ) = max {R(D s ), R(D o )} ≤ R(D o , D s ),

R(D

o ) = min q( z|z) E[do(z, z)]≤Do I(z; z), (9)
R(D s ) = min q( x|z) E[ ds(z, x)]≤Ds I(z; x). ( 10
)
Moreover, R L (D o , D s ) is tight if and only if (iff) z -z -x and z -x -z, (11)
are concurrently satisfied.

Next, we define the ergodic constrained and unconstrained channel capacity. Definition 3. (Constrained/unconstrained capacity) [START_REF] Gallager | Information Theory and Reliable Communication[END_REF] (i) For a given channel (p(b|a), c), the ergodic constrained capacity is characterized as follows

C(P ) = max p(b|a) E[c(a)]≤P I(a; b) (12)
where P ∈ [P min , P max ] = [0, ∞).

(ii) The special case of (12) at which the channel p(b|a) disregards the input cost c(•) is characterized by the ergodic unconstrained capacity as follows

C = max p(b|a) I(a; b). ( 13
)
We note that (13) is also obtained by [START_REF] Liu | A rate-distortion framework for characterizing semantic information[END_REF] if for c(a) < ∞, a ∈ A, C = lim P -→∞ C(P ).

In the sequel, we give two definitions, one for the achievable average distortion(s)-cost triplet (∆ s , ∆ o , Γ) and one for the optimality of the setup in Fig. 1. Clearly, Definitions 4, 5 are generalizations to those considered in [START_REF] Gastpar | To code, or not to code: lossy source-channel communication revisited[END_REF]Definitions 4,[START_REF] Popovski | Semantic-effectiveness filtering and control for post-5G wireless connectivity[END_REF].

Next, we state a lemma that identifies optimality conditions for the goal-oriented JSCC model in Fig. 1.

Lemma 2. (Optimality conditions) For a semanticobservations information source (p(x), p(z|x), d o , d s ) and a channel (p(b|a), c), the transmission using a goal-oriented source-channel code (f E , g D o , g D s ) of rate κ is optimal iff the following conditions are concurrently satisfied:

(i) κR(∆ o , ∆ s ) = C(Γ);
(ii) the pair (∆ o , ∆ s ) cannot be decreased without increasing R(∆ o , ∆ s ) and Γ cannot be decreased without decreasing C(Γ).

Proof: We sketch the proof because it is a modified version of the separation theorem [START_REF] Shannon | A mathematical theory of communication[END_REF]Theorem 21]. From the convexity and concavity of SRDF and the channel capacity, respectively, and the data processing inequality of the setup in Fig. 1, i.e., x n -z n -a m -b m -( x n , z n ), we obtain a converse part of the separation theorem, i.e., κR(∆ o , ∆ s ) ≤ C(Γ). For the direct part, suppose that there exists a triplet (f E , g D o , g D s ) such that κR(∆ o , ∆ s ) = C(Γ) -ϵ, for some ϵ > 0. Then, an immediate application of the direct part of the separation principle implies that there exists a better source-channel code ( f E , gD o , gD s ) such that κR(∆ o , ∆ s ) = C(Γ) -ε for some 0 < ε < ϵ. Hence, the optimal distortion(s)-cost triplet (∆ 0 , ∆ s , Γ) implies (i). This result is only necessary as there may be cases where each or both (∆ o , ∆ s ) (resp. Γ) can be reduced without increasing R(∆ o , ∆ s ) (resp. decreasing (CΓ)). Such cases can be prohibited by condition (ii).

Remark 1. (On Lemma 2) (i) In Lemma 2, the necessary condition is κR(∆ 0 , ∆ s ) = C(Γ) as the second condition that prohibits each or both (∆ 0 , ∆ s ) (resp. Γ) to reduce their value(s) may only happen when R(∆ o , ∆ s ) = 0 (resp. C(Γ) = C). (ii) It should be noted that Lemma 2 includes the case at which the bound in Lemma 1 is tight.

IV. GOAL-ORIENTED SINGLE-LETTER CODES

In this section, we consider single-letter codes to study the optimal performance of the goal-oriented JSCC system in Fig. 1. Our results apply once the bound in Lemma 1 is tight.

We start by introducing a special class to block sourcechannel codes introduced in Definition 1. Definition 6. (Goal-oriented single-letter source-channel codes) For the system model in Fig. 1, a goal-oriented singleletter source-channel code (f E , g D o , g D s ) is specified by an encoding function f E : Z → A, the observable decoding function g D o : B → Z and the semantic decoding function g D s : B → X .

Clearly, from the definition of block source-channel codes, we obtain κ = 1 if goal-oriented single-letter codes are considered. Since in Lemma 2, the crucial condition is κR(∆ o , ∆ s ) = C(Γ), we next state a theorem where we derive necessary and sufficient conditions for that condition to hold when κ = 1.

Theorem 1. (Conditions for R L (∆ o , ∆ s ) = C(Γ)) R L (∆ o , ∆ s ) = C(Γ)
∆ s = E[ d(z, x)], that is, I * (z; x) = R(∆ s ); (iv) the pair (f E (•), g D o (•)) results into I(z; z) = I(a; b); (v) the pair (f E (•), g D s (•)
) results into I(z; x) = I(a; b). Proof: Suppose that for some values of (∆ o , ∆ s ), R L (∆ o , ∆ s ) = R(∆ o ) holds. Then, the system model in Fig. 1 admits the following series of inequalities

R L (∆ o , ∆ s ) (⋆) = R(∆ o ) = min p( z|z) E[d(z, z)]≤∆o I(z; z) (⋆⋆) ≤ I(z; z) (⋆⋆⋆) ≤ I(a; b) (⋆⋆⋆⋆) ≤ max p(a) E[c(a)]≤Γ I(a; b) = C(Γ).
where (⋆) holds iff p( z| x, z) = p( z|z) (see condition (ii)); (⋆⋆) holds with equality iff p( z|z) achieves R(∆ o ) (see condition (ii)); (⋆ ⋆ ⋆) follows by data processing inequality that corresponds to the system in Fig. 1 and holds with equality iff condition (iv) holds; (⋆ ⋆ ⋆⋆) holds with equality iff p(a) is capacity achieving distribution (see condition (i)). Similarly, one can show that when for some value of

(∆ o , ∆ s ), R L (∆ o , ∆ s ) = R(∆ s ), R L (∆ o , ∆ s ) = R(∆ s ) = C(Γ) iff conditions (i), (iii), (v), hold. Hence R L (∆ o , ∆ s ) = C(P ) holds iff conditions (i)-(v) hold.
Theorem 1 (except from (i)) is a generalization of [11, Lemma 2]. One interesting question that stems from Theorem 1 is if one can always find, constructively, goal-oriented single-letter source-channel codes that allow R L (∆ o , ∆ s ) to be achieved despite the fact that this bound is not achievable, in general, via the separation based schemes.

Next, we state a corollary to ensure that Lemma 2, (ii), is always true when

R(∆ o , ∆ s ) = R L (∆ o , ∆ s ) = C(Γ).
Corollary 1. Suppose that for the setup in Fig. 1, the tuple (p(x), p(z|x), d o , d s ) is transmitted across a channel (p(b|a), c) using goal-oriented single-letter codes

(f E , g D o , g D s ) such that R L (∆ o , ∆ s ) = C(Γ).
Then, the following statements hold. (i) Γ cannot be decreased without decreasing C(Γ) iff one of the following two conditions is satisfied: (A) I(a; b) < C; (B) I(a; b) = C and among the possible maximizers, the capacity achieving distribution p(a) is the unique maximer that achieves the lowest Γ.

(ii) Suppose that R L (∆ o , ∆ s ) = R(∆ o ).
Then ∆ o cannot be decreased without increasing R(∆ o ) iff one of the following two conditions is satisfied: (A) I(z; z) > 0; (B) I(z; z) = 0 and among the possible achieving minimizers, the rate-distortion achieving distribution p( z|z) is the unique minimizer that achieves the lowest

∆ o . (iii) Suppose that R L (∆ o , ∆ s ) = R(∆ s ).
Then ∆ s cannot be decreased without decreasing R(∆ s ) iff one of the following two conditions is satisfied: (A) I(z; x) > 0; (b) I(z; x) = 0 and among the possible achieving minimizers, the rate-distortion achieving distribution p( x|z) is the unique minizer that achieves the lowest ∆ s .

Proof: The proof of this corollary follows using similar arguments to [START_REF] Gastpar | To code, or not to code: lossy source-channel communication revisited[END_REF]Proposition 5] with some small changes. For completeness, we give the missing part of the proof in the Appendix A.

V. EXAMPLES

In this section, we construct two examples assuming transmission using goal-oriented single-letter codes with one channel use per source symbol, i.e., κ = 1.

A. Binary sources -BSC

First, we give an example for binary alphabet sources and channels. This example is a generalization of the celebrated result by Jelinek in [START_REF] Jelinek | Probabilistic Information Theory: discrete and memoryless models[END_REF]Section 11.8].

Example 1. Consider X = Z = A = B = X = Z = {0, 1}.
Moreover, the semantic source x is uniform and the transition matrix z given x = x is doubly stochastic both modeled by

p(x) = 1 2 1 2 , p(z|x) = 1 -w 1 w 1 w 1 1 -w 1 (14)
where w 1 ∈ 0, 1 2 . Moreover, the distortion functions d o (z, z) and d s (x, x) are given by

d o (z, z) = 0, if z = z 1, otherwise , d s (x, x) = 0, if x = x 1, otherwise .
The channel is assumed to be the BSC with transition probability matrix p(b|a) given by

p(b|a) = 1 -ϵ 1 ϵ 1 ϵ 1 1 -ϵ 1 , ϵ 1 ∈ 0, 1 2 . (15)
Using [START_REF] Berger | Rate Distortion Theory: A Mathematical Basis for Data Compression[END_REF] under Hamming distortions, the SRDF was obtained in closed form in [13, Example 1] as follows

R(D o , D s ) = R L (D o , D s ) = max {R(D o ), R(D s )} (16)
where

R(D o ) = 1 -H b (D o ), if D o ∈ (0, 1 2 ) 0, if D o ∈ [ 1 2 , ∞) (17)
and

R(D s ) = 1 -H b ( Ds-w1 1-2w1 ), if D s ∈ (w 1 , 1 2 ) 0, if D s ∈ [ 1 2 , ∞) (18)
where H b (•) denotes the binary entropy function.

On the other hand, the channel capacity of the BSC is given by C = 1 -H b (ϵ 1 ) [START_REF] Cover | Elements of Information Theory[END_REF]. Following, the optimality conditions of Lemma 2, we first require R L (∆ o , ∆ s ) = C. For this criterion to be valid, we need to check the following two cases. Suppose that R L (∆ o , ∆ s ) = R(∆ o ), then, from (5), we obtain

∆ o = E[d o (z, z)] = ϵ 1 , which further means that R(∆ o ) = 1 - H b (∆ o ) = 1 -H b (ϵ 1 ), hence R(∆ o ) = C. Suppose that R L (∆ o , ∆ s ) = R(∆ s )
; then, again from (5), we obtain

∆ s = E[d s (x, x)] = E[ d s (z, x)] = ϵ 1 (1 -2w 1 ) + w 1 , which further means that R(∆ s ) = 1 -H b ( ∆s-w1 1-2w1 ) = 1 -H b (ϵ 1 ), hence R(∆ s ) = C.
The previous analysis confirms Lemma 2, (i). On top of that, one can easily see that the conditions of Theorem 1 are also satisfied. Lemma 2, (ii), is clearly satisfied as an immediate consequence of Corollary 1 because the specific choices of w 1 and ϵ 1 guarantee that the maximizer p(a) is unique and achieves C and similarly the minimizers p( z|z) and p( x|z) achieve R(∆ o ) and R(∆ s ), respectively. Hence the specific realization of this goal-oriented sourcechannel communication model in Fig. 1 using single-letter codes is optimal.

B. i.i.d Gaussian sources-AWGN channel

In the next example, we consider a jointly Gaussian semantic source and noisy observations conveyed across an AWGN channel with the cost function being a power and the distortions the standard squared error. This example is a generalization of a result by Goblick in [START_REF] Goblick | Theoretical limitations on the transmission of data from analog sources[END_REF].

Example 2. Consider a joint Gaussian i.i.d process (x n , z n ), where the semantic source is such that x ∼ N (0; σ 2

x ), σ 2

x > 0, and the conditionally Gaussian distribution p G (z|x) is modeled by z = x + n, where n ∼ N (0; σ 2 n ) is an i.i.d sequence of random variables. Moreover, d o (z, z) and d s (x, x) are given as follows

d o (z, z) = (z -z) 2 , d s (x, x) = (x -x) 2 . ( 19
)
The source is conveyed across a standard AWGN channel with transition probability p(b|a) modeled as b = a + m, for which m ∼ N (0; σ 2 m ), σ 2 m > 0, with input power constraint E[a 2 ] ≤ P , P > 0.

For the specific class of Gaussian semantic sources and noisy observations under squared-error distortions, the SRDF is obtained in closed form in [START_REF] Liu | A rate-distortion framework for characterizing semantic information[END_REF]Proposition 3] as follows

R(D o , D s ) = R L (D o , D s ) = max {R(D o ), R(D s )} (20) where R(D o ) = 1 2 log σ 2 z Do , if D o ∈ (0, σ 2 z ) 0, otherwise (21)
and

R(D s ) =    1 2 log σ 4 x σ 2 z (Ds-σ 2 x|z ) , if D s ∈ σ 2 x|z , σ 4 x σ 2 z 0, otherwise (22)
where

σ 2 x|z = σ 2 x σ 2 n σ 2 x +σ 2 n
is the conditional variance of the conditionally Gaussian distribution p G (x|z).

The constrained channel capacity of AWGN is well known and is given by C

(P ) = 1 2 log 1 + P σ 2 m [16]. Following Lemma 2, (i), we first require R L (∆ o , ∆ s ) = C(Γ). Similarly to Example 1, we check if (A) R(∆ o ) = C(Γ); (B) R(∆ s ) = C(Γ).
Since we have now the presence of the cost Γ > 0, the approach is slightly different. To ensure case (A), we require (similar to [START_REF] Goblick | Theoretical limitations on the transmission of data from analog sources[END_REF])

∆ o = σ 2 z σ 2 m Γ+σ 2 m ,
which based on standard terminology we referred to as the minimum observable achievable distortion (D min o ). To achieve this operational point, we need to find a specific encoder and decoder operating at D min o . Indeed, if we define the singleletter source-channel encoder and decoder pair as follows from the choice of (24). One can observe that the above methodology verifies the iff conditions of Theorem 1. Finally, Lemma 2, (ii), is verified because of Corollary 1. Hence, the specific realization of the goal-oriented communication system in Fig. 1, using single-letter codes and uncoded transmission is optimal.

a = Γ σ 2 z z, z = σ 2 z Γ Γ Γ + σ 2 m b, (23)
The two application examples described above, demonstrate the vital role of the fidelity constraints in goal-oriented communications over noisy channels using single-letter codes.

VI. CONCLUSIONS AND ONGOING STUDY

We studied a new variation of a JSCC problem that has natural goal-oriented features from an inference perspective. We defined a variation of block source-channel codes and gave optimality conditions for the system model to operate optimally. Our main focus was on single-letter codes for which we derived a new theorem that provides necessary and sufficient conditions for the probabilistic matching of the semantic source message with the noisy channel. Two application examples were presented to corroborate our theoretical results.

The optimality conditions of our JSCC setup can be further studied to take into account bandwidth constraints (i.e., κ < 1, κ > 1) as Lemma 2 suggests. This study will follow in the extended version of the paper. It would be interesting to use tools from the machine learning community for more complex analysis of our setup and its extensions.

Fig. 1 .

 1 Fig. 1. The proposed goal-oriented source-channel communication model.

Definition 4 .

 4 (Average distortion(s)-cost triplet) For a given (p(x), p(z|x), d o , d s ) and a fixed channel (p(b|a), c), we write (∆ s , ∆ o , Γ) given by (5)-(6) to denote the average distortion(s)-cost triplet achieved by a fixed code (f E , g D o , g D s ). In view of Definition 4, we will denote by (D s , D o , P ) a general distortion(s)-cost triplet not necessarily achievable. Definition 5. (Optimality criterion) The transmission of a semantic/observations source (p(x), p(z|x), d s , d o ), across a noisy channel (p(b|a), c) results into a source-channel code (f E , g D o , g D s ) that is optimal if the following two conditions are concurrently satisfied: (i) the distortion(s) (∆ o , ∆ s ) caused by the choice of (f E , g D o , g D s ), correspond to the minimum achievable distortions (hereinafter denoted by D min o , D min s ) operating at an input cost Γ with the best possible source-channel code of rate κ; (ii) the cost Γ obtained by (f E , g D o , g D s ), corresponds to the minimum cost required to achieve the distortion(s) (∆ o , ∆ s ) with the best possible source-channel code of rate κ.

  holds iff the following conditions are concurrently satisfied: (i) the distribution p(a) of a = f E (z) is capacity achieving for the channel (p(b|a), c) at an average input cost Γ = E[c(a)], that is, I * (a; b) = C(Γ); (ii) the conditional independence p( x| z, z) = p( x| z) holds with z = g D o (b) given z be the achieving distribution of SRDF at R(∆ o ) for an average distortion ∆ o = E[d(z, z)], that is, I * (z; z) = R(∆ o ); (iii) the conditional independence p( z| x, z) = p( z| x) holds with x = g D o (b) given z be the achieving distribution of SRDF at R(∆ s ) for an average distortion

  Now choose the triplet (f E , g D o , g D s ) in Definition 6 such that f E (z) = z, g D o (b) = b, g D s (b) = b (i.e., identity maps), which further implies that a = z, b = z or b = x.

4 x σ 2 m σ 2 z (σ 2 m 2 z

 4222 then, the resulting ∆ o = E[(zz) 2 ] = D min o and case (A) is verified. To ensure case (B), we require ∆ s = σ +Γ) + σ 2 x|z , which is the minimum semantic achievable distortion D min s . To achieve D min s , we choose the following pair of single-letter encoder and decoder: where µ x|z ≡ E[x|z] = σxz σ conditional mean of p G (x|z). The choice in (24) results into an operational distortion∆ s = E[(xx) 2 ] = E[(x -µ x|z + µ x|z -x) 2 ] ( * ) = E[(x -µ x|z ) 2 ] + E[(µ x|z -x) 2 ] ( * * ) = D mins where ( * ) follows from the orthogonality principle; ( * * )

The constrained set in[START_REF] Gallager | Information Theory and Reliable Communication[END_REF] is compact (for both finite or abstract alphabets) and the mutual information in[START_REF] Gallager | Information Theory and Reliable Communication[END_REF] is lower semi-continuous on q( z, x|z). As a result, from Weierstrass' extreme value theorem, the infimum is attained by some q * ( z, x|z) and we can formally replace it with minimum.

APPENDIX A PROOF OF COROLLARY 1

We only prove statement (iii) as statements (i), (ii) are already known from [11,

But when R(∆ s ) > 0 we know that its curve is convex and strictly decreasing with respect to ∆ s (see e.g., [START_REF] Csiszár | Information Theory: Coding Theorems for Discrete Memoryless Systems[END_REF]Chapter 8]), hence there is a unique ∆ s for each point on the curve R(∆ s ). This implies that ∆ s cannot be decreased without increasing R(∆ s ). Necessity of (A): If ∆ s ≥ ∆ max s , then, I(z; x) = 0, hence it is possible to have multiple ∆ s 's without changing the value of R(∆ s ). Sufficiency of (B): If I(z; x) = 0 and among the possible minimizers, the rate-distortion achieving distribution p( x|z) is the one that achieves the lowest ∆ s this means that it is impossible to alter ∆ s without changing R(∆ s ) because we will need to change p( x|z) (this argument is trivially obtained if p( x|z) is unique).

Necessity of (B): If I(a; b) = 0, then, ∆ s ≥ ∆ max s , hence there are multiple minimizers p( x|z) that achieve different values of ∆ s 's but not necessarily its minimum value which is ∆ max s . (again this argument is trivially obtained as long as p( x|z) is unique).