Dariusz Dereniowski

Adrian Kosowski
email: adrian.kosowski@inria.fr

Dominik Pająk

Distinguishing Views in Symmetric Networks: A Tight Lower Bound

Keywords: anonymous network, port-labeled network, view, quotient graph

The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers n ≥ D ≥ 1, there exists a port-labeled network with at most n nodes and diameter at most D which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth Ω(D log(n/D)) are identical.

Introduction

The notion of a view was introduced and first studied by Yamashita and Kameda in [START_REF] Yamashita | Computing on anonymous networks: Part I-characterizing the solvable cases[END_REF] in the context of distributed message passing algorithms. In so-called anonymous networks (without unique identifiers accessible to a distributed algorithm), the view is a fundamental concept which allows for identification of the network topology and for breaking of symmetries between nodes. Different views for a pair of nodes guarantee that the corresponding nodes are distinguishable, which is useful in, e.g., leader election algorithms. View-based approaches have been successfully used when designing algorithms for various network problems, including map construction [START_REF] Chalopin | Constructing a map of an anonymous graph: Applications of universal sequences[END_REF][START_REF] Dereniowski | Drawing maps with advice[END_REF], leader election [START_REF] Chalopin | An efficient message passing election algorithm based on Mazurkiewicz's algorithm[END_REF][START_REF] Das | Effective elections for anonymous mobile agents[END_REF][START_REF] Dereniowski | Leader election for anonymous asynchronous agents in arbitrary networks[END_REF][START_REF] Fusco | Knowledge, level of symmetry, and time of leader election[END_REF][START_REF] Tani | Exact quantum algorithms for the leader election problem[END_REF][START_REF] Yamashita | Leader election problem on networks in which processor identity numbers are not distinct[END_REF], rendezvous [START_REF] Czyzowicz | How to meet when you forget: log-space rendezvous in arbitrary graphs[END_REF][START_REF] Das | Rendezvous of mobile agents when tokens fail anytime[END_REF][START_REF] Guilbault | Asynchronous rendezvous of anonymous agents in arbitrary graphs[END_REF], and other tasks [START_REF] Flocchini | Computing on anonymous networks with sense of direction[END_REF][START_REF] Yamashita | Computing functions on asynchronous anonymous networks[END_REF].

The view from a node of a network is by definition (cf. Section 2) an infinite rooted tree, and therefore distributed algorithms (both for agents exploring the network or for the nodes in message passing models) can only know a finite subtree of the view. This motivates the question about the minimum integer l such that the view truncated to depth l contains all crucial information an algorithm may need.

Yamashita and Kameda proved that if views of two nodes truncated to depth n 2 are identical, then their infinite views are identical [START_REF] Yamashita | Computing on anonymous networks: Part I-characterizing the solvable cases[END_REF], where n is the number of nodes of the network. The bound has been improved to n -1 by Norris [START_REF] Norris | Universal covers of graphs: Isomorphism to depth N-1 implies isomorphism to all depths[END_REF]. Although this bound is asymptotically tight [START_REF] Boldi | Fibrations of graphs[END_REF][START_REF] Norris | Universal covers of graphs: Isomorphism to depth N-1 implies isomorphism to all depths[END_REF], it is far from being accurate for many networks. Hence, one may ask for bounds expressed as function of different graph invariants. Fraigniaud and Pelc proved in [START_REF] Fraigniaud | Decidability classes for mobile agents computing[END_REF] that if two nodes have the same views do depth n-1 then their views are the same, where n is the number of nodes having different views (or equivalently, n is the size of the quotient graph [START_REF] Yamashita | Computing on anonymous networks: Part I-characterizing the solvable cases[END_REF]). For some works on view computation see, e.g., [START_REF] Boldi | Universal dynamic synchronous self-stabilization[END_REF][START_REF] Tani | Compression of view on anonymous networks -folded view[END_REF]. Recently, Hendrickx [START_REF] Hendrickx | Views in a graph: To which depth must equality be checked?[END_REF] proved (for simple graphs with symmetric port labeling) an upper bound of O(D log(n/D)) on the depth to which views need to be checked in order to be distinguished, where D is the diameter of the network, leaving the tightness of this bound as an open problem.

In this work we provide a corresponding lower bound of Ω(D log(n/D)). In particular, for each D ≥ 3 and n ≥ D • 2 12 /3, we construct an n -node graph G with diameter at most D such that taking truncations of the view to depth D -5 6 log 2 n D -0.41D does not guarantee distinguishing a pair of nodes of this graph, which do in fact have different (infinite) views. Our construction is done in two steps. First, a list of graphs G l , l ≥ 1, is defined with the following properties: (a) diam(G l ) = 3 for each l ≥ 1, and (b) G l contains two nodes a l and b l such that the views from them to depth l = Θ(log n) are identical but their (infinite) views are different, where n is the size of G l . Next, in order to extend the bound for arbitrarily large diameter D we then modify G l by subdividing each of its edges roughly D /3 times so that the new graph: (a) has diameter roughly D , and (b) contains two nodes a l and b l such that their views are the same till depth Θ(D log 2 (n /D )) but their views are different, where n is the size of the subdivided graph.

We remark that very recently [START_REF] Fusco | Knowledge, level of symmetry, and time of leader election[END_REF], a construction of a class of labeled graphs has been put forward in the context of lower bounds for the leader election problem on anonymous graphs, which can also be used to obtain a separation of node views at distance Θ(log n) in a graph of diameter D = O(1). The analysis of that class appears somewhat more involved than for our construction.

Preliminaries

In this work we consider anonymous port labeled networks (the terms graph and network are used interchangeably throughout) in which the nodes do not have identifiers and each edge {u, v} has two integers assigned to its endpoints, called the port numbers at u and v, respectively. The port numbers are assigned in such a way that for each node v they are pairwise different and they form a consecutive set of integers {1, . . . , k}, where k is the number of neighbors of v in G. The number of neighbors of v in G is called the degree of v and is denoted by deg G (v). To simplify some statements we introduce a port labeling function λ for G defined in such a way that for each pair u, v of adjacent nodes, λ(u, v) is the port label at u of the edge {u, v}. For each node v of G and for each p ∈ {1, . . . , deg G (v)}, next p (v) is the node u such that λ(v, u) = p, whereas end p (v) = λ(next p (v), v) is the port label at the other end of the edge.

We recall the definition of a view [START_REF] Yamashita | Computing on anonymous networks: Part I-characterizing the solvable cases[END_REF]. Let G be a graph, v be a node of G and let λ be a port labeling for G. Given any l ≥ 0, the (truncated) view up to level l, V l (v), is defined as follows. V 0 (v) is a tree consisting of a single node x 0 . Then, V l+1 (v) is the port-labeled tree rooted at x 0 and constructed as follows. For every node v i , i ∈ {1, . . . , deg G (v)}, adjacent to v in G there is a child x i of x 0 in V l+1 (v) such that the port number at x 0 corresponding to edge {x 0 , x i } equals λ(v, v i ), and the port number at x i corresponding to edge {x 0 , x i } equals λ(v i , v). For each i ∈ {1, . . . , deg G (v)} the node x i is the root of the truncated view V l (v i ).

The view from v in G is the infinite port-labeled rooted tree V(v) such that V l (v) is its truncation to level l, for each l ≥ 0.

We remark that by adopting the above definitions, we are considering so-called symmetric networks in the sense that the port-labeled network corresponds to an unlabeled graph which is undirected, and that the encoding of port numbers at both endpoints of each edge appears in the labeling of the edges of the view.

A path in G is denoted as a sequence of nodes, P = (v 0 , v 1 , . . . , v k ), such that {v 0 , . . . , v k } ⊆ V (G) and {v i , v i+1 } is an edge in G for each i ∈ {0, . . . , k -1}. Note that nodes may repeat in a path, i.e., we do not assume that v i = v j for i = j. We say that two paths P 1 = (u 0 , u 1 , . . . , u k ) and

P 2 = (v 0 , v 1 , . . . , v k ) in G are isomorphic if λ(u i , u i+1 ) = λ(v i , v i+1 ) and λ(u i+1 , u i ) = λ(v i+1 , v i )
for each i ∈ {0, . . . , k -1}. We will call a path non-backtracking1 if it never follows the same edge twice on end in opposite directions, i.e., λ(v i , v i-1 ) = λ(v i , v i+1 ) for all i ∈ {1, . . . , k -1}.

Claim 2.1 ([19])

Let G be a graph, let u, v be two nodes of G, and let l ≥ 0 be an integer. We have V l (u) = V l (v) if and only if, for any path of length l starting at u, there exists an isomorphic path of length l starting at v, and vice versa. The claim also holds when restricting considerations to non-backtracking paths.

We write diam(G) to denote the diameter of G, i.e., the maximum (taken over all pairs of nodes u and v) length of a shortest path between u and v in G.

The lower bound

For each l > 1 we define the graph G l which consists of nodes laid out on a regular grid with l + 2 levels and 2 l columns, where the node in level i ∈ {0, 1, . . . , l + 1} and column j ∈ {0, 1, . . . , 2 l -1} is denoted by v i (j). Note that all levels are of size 2 l , and

n l = |V (G l )| = (l + 2)2 l .
The construction of the edge set of G l proceeds in four stages. Before giving a formal construction, we first provide some intuitions regarding the purpose served by edges introduced in different stages. The edges added to G l in Stages 2 and 3 ensure that the graph is connected and has diameter of fixed size. The aim of Stage 3 is to add edges between consecutive levels in such a way that if one wants to detect a difference between some pairs of nodes in level l + 1 (e.g., v l+1 (0) and v l+1 (2 l-1 )), then two paths of sufficient length from those nodes need to be selected. In particular, the paths first need to go through all levels and reach level 0 (in the mentioned case, these are the nodes v 0 (0) and v 0 (1)). The edges added to G l in Stage 1 ensure that nodes in level 0 from two consecutive columns have different views truncated to depth 2.

Stage 1. Edges within level 0. In level 0, the edges form a matching between nodes v 0 (j) and v 0 (j ⊕ 1), j ∈ {0, . . . , 2 l -1}, with ports with labels {1, 2}, given as follows:

for j := 0, . . . , 2 l -1 do λ(v 0 (j), v 0 (j ⊕ 1)) := 1 + ((j + 1) mod 2); In the above, ⊕ denotes the xor operation (bitwise modulo-2 addition of non-negative integers).

Stage 2. Edges within level l + 1. The edges in level l + 1 form a clique on all 2 l nodes of the level, with port labels corresponding to the difference of identifiers of the connected nodes, computed modulo 2 l .

for j := 0, . . . , 2 l -1 do for p := 1, . . . , 2 l -1 do λ(v l+1 (j), v l+1 ((j + p) mod 2 l )) := p.

Stage 3. Edges connecting level l + 1 with all lower levels. Each node v l+1 (j) from level l + 1 is connected to all nodes lying in lower levels, in the same column. The port numbers at node v l+1 (j) leading to successive levels are successive integers starting from 2 l , and the port numbers at the other end of such edges are always equal to 1, except for level 0, where the port label is either 1 or 2 (depending on which port was not used at the considered node in Stage 1 of the construction): for j := 0, . . . , 2 l -1 do for i := 0, . . . , l do λ(v l+1 (j), v i (j)) := 2 l + i;

if i > 0 then λ(v i (j), v l+1 (j)) := 1. else λ(v 0 (j), v l+1 (j)) := 1 + (j mod 2).
Stage 4. Edges connecting adjacent levels. Each node belonging to a level i ∈ {0, . . . , l -1} is connected by an edge to exactly one node of the level i + 1 directly above, so that the set of edges between such two adjacent levels is a matching. Specifically, we introduce a permutation π i on the set of integers {0, . . . , 2 l -1}, defined for i = 0 as the identity permutation π 0 (j) = j, and for i > 0 as the involution (a function that is its own inverse) which swaps the values of the i-th and (i -1)-th rightmost bits in the binary notation of its argument:

π i (j) = (j -2 i b i (j) -2 i-1 b i-1 (j)) + 2 i b i-1 (j) + 2 i-1 b i (j), (1)
where for k ≥ 0, b k (j) = 1 if (j mod 2 k+1 ) ≥ 2 k , and b k (j) = 0, otherwise. For each node at level i ∈ {1, . . . , l -1}, the port label used on the edge leading to level i -1 is always 2, and the port label leading to level i + 1 is always 3, as follows: for j := 0, . . . , 2 l -1 do for i := 0, . . . , l -1 do λ(v i (j), v i+1 (π i (j)) := 3; λ(v i+1 (π i (j)), v i (j)) := 2. The graph G 4 with some edges omitted is shown in Figure 1. In particular, the edges between

Proof:

The number of edges of G l can be bounded by counting the number of edges added in Stages 1 to 4 and bounding for l ≥ 6.

To bound the diameter, note that any node of G l either belongs to level l + 1 or is within distance 1 from a node in level l + 1. Also, any two nodes in level l + 1 are adjacent.

For a pair of integers 0 ≤ j 1 , j 2 < 2 l , we will denote by δ(j 1 , j 2 ) the number of rightmost bits in their binary representations which are all identical, i.e., δ(j 1 , j 2 ) is the largest integer δ ∈ {0, . . . , l} such that (j 1 ≡ j 2 ) mod 2 δ (or equivalently, such that b k (j 1 ) = b k (j 2 ) for all 0 ≤ k < δ). The function δ(j 1 , j 2 ) has several important properties with respect to transformations of its parameters. Lemma 3.1 Let j 1 , j 2 , d ∈ {0, . . . , 2 l -1} and i ∈ {1, . . . , l -1} be arbitrarily chosen. Then:

(i) δ(j 1 ⊕ d, j 2 ⊕ d) = δ(j 1 , j 2 ). (ii) δ((j 1 + d) mod 2 l , (j 2 + d) mod 2 l ) = δ(j 1 , j 2 ).
(iii) δ(π i (j 1 ), π i (j 2 )) ≥ δ(j 1 , j 2 ) -1, where involution π i is defined by (1).

Proof: Claims (i) and (ii) can be attributed to folklore. To prove claim (iii), note that the involution π i consists in swapping adjacent bits at positions i and i -1, only. Consequently, we have by definition of δ(j 1 , j 2 ) that if δ(π i (j 1 ), π i (j 2 )) = δ(j 1 , j 2 ) then either δ(j 1 , j 2 ) = i -1 or δ(j 1 , j 2 ) = i. In both cases, we have δ(π i (j 1 ), π i (j 2 )) ≥ i -1, and claim (iii) follows.

In the following, for two nodes v i (j 1 ) and v i (j 2 ) belonging to the same level i of G l , we will use the notation: δ(v i (j 1 ), v i (j 2 )) ≡ δ(j 1 , j 2 ). Lemma 3.2 Consider a pair of nodes v i (j 1 ), v i (j 2 ) of G l with δ(v i (j 1 ), v i (j 2 )) > 0. Then: (i) Nodes v i (j 1 ) and v i (j 2 ) are of the same degree d.

(ii) For any port p ∈ {1, . . . , d}, nodes next p (v i (j 1 )) and next p (v i (j 2 )) belong to the same level in G l .

(iii) For any port p ∈ {1, . . . , d}, δ(next

p (v i (j 1 )), next p (v i (j 2 )) ≥ δ(v i (j 1 ), v i (j 2 )) -1.
(iv) For any port p ∈ {1, . . . , d}, end p (v i (j 1 )) = end p (v i (j 2 )).

Proof: By the construction of G l , all nodes in the same level are of the same degree, and claim (i) follows. Claim (ii) also follows directly from the construction of G l . The construction of the port labeling in G l is such that the Stage a ∈ {1, 2, 3, 4}, during which an edge along any port p is added to a vertex v i (j), depends only on the value of its level i and the parity j mod 2 of its column number (this parity is only relevant for the case of i = 0 and p = 2, distinguishing edges added in Stage 1 and Stage 3). The nodes v i (j 1 ) and v i (j 2 ) belong to the same level. Moreover, since δ(j 1 , j 2 ) > 0, we have that

(j 1 ≡ j 2 ) mod 2.
(

) 2
It follows that the edges e 1 = {v i (j 1 ), next p (v i (j 1 ))} and e 2 = {v i (j 2 ), next p (v i (j 2 ))}, corresponding to a traversal of the same port p starting from nodes v i (j 1 ) and v i (j 2 ), must necessarily have been defined in the same Stage a of the construction of the edge set of G l . To complete the proofs of claims (iii) and (iv), we consider the corresponding four cases of a ∈ {1, 2, 3, 4}.

• Edges e 1 and e 2 were defined in Stage 1. Then, i = 0, p ∈ {1, 2}, and we have:

next p (v i (j 1 )) = v i (j 1 ⊕ 1), end p (v i (j 1 )) = 1 + (j 1 mod 2), next p (v i (j 2 )) = v i (j 2 ⊕ 1), end p (v i (j 2 )) = 1 + (j 2 mod 2).
By Lemma 3.1(i), we have:

δ(next p (v i (j 1 )), next p (v i (j 2 )) = δ(v i (j 1 ), v i (j 2 )).
Moreover, taking into account (2), we obtain end p (v i (j 1 )) = end p (v i (j 2 )). This completes the proof of claims (iii) and (iv) for this case.

• Edges e 1 and e 2 were defined in Stage 2. Then, i = l + 1, p ∈ {1, . . . , 2 l -1}, and we have:

next p (v i (j 1 )) = v i ((j 1 + p) mod 2 l ), end p (v i (j 1 )) = (2 l -p) mod 2 l , next p (v i (j 2 )) = v i ((j 2 + p) mod 2 l ), end p (v i (j 2 )) = (2 l -p) mod 2 l .
We immediately have end p (v i (j 1 )) = end p (v i (j 2 )), and moreover, by Lemma 3.1(ii):

δ(next p (v i (j 1 )), next p (v i (j 2 )) = δ(v i (j 1 ), v i (j 2 )).
• Edges e 1 and e 2 were defined in Stage 3. Then, we need to consider two cases: either i = l +1, or i ∈ {0, . . . l}.

If i = l + 1, then p = 2 l + i for some i ∈ {0, . . . l}. We have for i > 0:

next p (v i (j 1 )) = v i (j 1 ), end p (v i (j 1 )) = 1, next p (v i (j 2 )) = v i (j 2 ), end p (v i (j 2 )) = 1,
whereas for i = 0:

next p (v i (j 1 )) = v 0 (j 1 ), end p (v i (j 1 )) = 1 + (j 1 mod 2), next p (v i (j 2 )) = v 0 (j 2 ), end p (v i (j 2 )) = 1 + (j 2 mod 2).
Claims (iii) and (iv) follow directly, taking into account Equation (2) in the latter case.

Otherwise, if i < l + 1, then p = 2 (if i = 0 and j 1 ≡ j 2 ≡ 1 mod 2), or p = 1 (in all other cases). We have:

next p (v i (j 1 )) = v l+1 (j 1 ), end p (v i (j 1 )) = 2 l + i, next p (v i (j 2 )) = v l+1 (j 2 ), end p (v i (j 2 )) = 2 l + i,
and claims (iii) and (iv) immediately follow as well.

By [START_REF] Boldi | Fibrations of graphs[END_REF],

π l-1-i (j) = j -2 l-1-i b l-1-i (j) -2 l-2-i b l-2-i (j) + 2 l-1-i b l-2-i (j) + 2 l-2-i b l-1-i (j).
We have b l-1-i (j) = 0 because 2 l-2-i mod 2 l-i = 0 < 2 l-1-i , and b l-2-i (j) = 1 because 2 l-2-i mod 2 l-1-i ≥ 2 l-2-i . Thus, π l-1-i (j) = j -2 l-2-i + 2 l-1-i = 2 l-1-i as required, which completes the proof of (3). Thus, for i = l -1, we reach nodes v 1 (0) and v 1 (1), respectively. Then, after following port 2 for the l-th time, we reach nodes v 0 (0) and v 0 (1), respectively. Finally, after following port 2 for the (l + 1)-th time, We reach nodes v 0 (1) and v l+1 (1), respectively.

In the last step of the traversal of this sequence of ports, node v 0 (1) is entered by port 1, while node v l+1 (1) is entered by port 2 l . Hence, V(a l ) = V(b l ). On the other hand, δ(v l (0), v l (2 l-1 )) = l -1, so by Lemma 3.3, V l-1 (a l ) = V l-1 (b l ). We obtain the following claim. Proposition 3.1 For any integer l ≥ 6, there exists a graph G l on (l + 2)2 l nodes, at most 2 2l edges, and diameter at most 3, which contains a pair of nodes a l , b l having distinct views and having the same views up to depth l -1.

This result completes our proof for the case of graphs of diameter 3. Now, in order to obtain an asymptotic lower bound of Ω(D log(n/D)), where n and D are, respectively, the size and the diameter of a graph, we modify each of G l 's to obtain graphs of arbitrarily large diameter.

Let D be an odd integer. For each G l , l ≥ 1, define ξ D (G l ) to be a graph constructed by replacing each edge {u, v} from G l by a path P ({u, v}) of length D with endpoints u and v. Note that

|V (ξ D (G l ))| = |V (G l )| + (D -1)|E(G l )| and |E(ξ D (G))| = D|E(G l )|. Also, ξ 1 (G l ) = G l .
We define the port labeling λ D for ξ D (G l ) as follows. For each {u, v} ∈ E(G l ) take the corresponding path P ({u, v}) = (u, x 1 , . . . , x D-1 , v) and set λ D (u, x 1 ) = λ(u, v), λ D (v, x D-1 ) = λ(v, u). The remaining port labels of P ({u, v}) are assigned arbitrarily but in such a way that whenever two edges of G l have the same port labels at the endpoints, then we select isomorphic port labelings for the two corresponding paths in ξ D (G l ). Formally, for any two edges {u, v} and {u , v } of G l satisfying λ(u, v) = λ(u , v ) and λ(v, u) = λ(v , u ), for the two corresponding paths P ({u, v}) = (u = x 0 , x 1 , . . . , x D-1 , x D = v) and P ({u , v }) = (u = x 0 , x 1 , . . . , x D-1 , x D = v ) it holds that λ D (x j , x j+1 ) = λ D (x j , x j+1 ) and λ D (x j+1 , x j ) = λ D (x j+1 , x j ) for each j ∈ {0, . . . , D -1}. The latter is possible for any D when λ(u, v) = λ(v, u) and it is possible for odd D for 'symmetric' edges, i.e., when λ(u, v) = λ(v, u). As an example of such labeling consider the following. If D is odd and λ(u, v) = λ(v, u), then we set λ D (x j , x j-1 ) = 1 and λ D (x j , x j+1 ) = 2 for each j ∈ {1, . . . , D/2 }, and λ D (x j , x j-1 ) = 2 and λ D (x j , x j+1 ) = 1 for each j ∈ { D/2 + 1, . . . , D -1}.

If, on the other hand, λ(u, v) = λ(v, u), then one can set λ D (x j , x j-1 ) = 1 and λ D (x j , x j+1 ) = 2 for each j ∈ {1, . . . , D -1}.

We also have the following claim.

Claim 3.2

For each l ≥ 1 and D ≥ 1 it holds that diam(ξ D (G l )) ≤ 3D.

• One may consider scenarios in which some information (labels) is also encoded at nodes of the network, and also appears as a node-labeling in the definition of the view. (Such an extended definition of views has appeared, e.g., in the context of leader election in networks where not all identifiers are distinct [START_REF] Yamashita | Leader election problem on networks in which processor identity numbers are not distinct[END_REF]).

• One may ask about the depth of the view which suffices not only to distinguish a pair of nodes of the same graph having distinct views, but also any pair of nodes of two arbitrary graphs, which have the same view. (This type of distinction is required in, e.g., in so-called map construction problems [START_REF] Chalopin | Constructing a map of an anonymous graph: Applications of universal sequences[END_REF].)

Since our lower bound concerns a more restricted scenario, it immediately applies to both of the above cases as well. Formally, when considering a pair of graphs, as n and D we take the maximum order and diameter of the two graphs. At the same time, the techniques used by Hendrickx [START_REF] Hendrickx | Views in a graph: To which depth must equality be checked?[END_REF] to show a corresponding upper bound of O(D log 2 (n/D)) for distinguishing a pair of nodes of a connected graph can be adapted to apply to all of the above cases as well, including the scenario of distinguishing a pair of views in two different graphs. Indeed, suppose that there exist a graph G 1 on n 1 nodes with diameter D 1 containing a node v 1 , and a graph G 2 on n 2 nodes with diameter D 2 containing a node v 2 , such that nodes v 1 and v 2 have views in their respective graphs indistinguishable up to some distance l > 1. Then, one can construct a new connected graph G on n = n 1 + n 2 nodes with diameter D ≤ D 1 + D 2 , in which there exists a pair of nodes with views indistinguishable also up to distance l. To achieve this, denoting by d the degrees of v 1 in G 1 and of v 2 in G 2 , which are necessarily equal, we form G by taking the disjoint union of graphs G 1 and G 2 , and connecting vertices v 1 and v 2 by an edge labeled with port d + 1 at both ends.

Thus, we can say that the question of the necessary depth of view reconstruction with respect to the diameter of a symmetric port-labeled networks has been completely resolved.

Figure 1 :Claim 3 . 1

 131 Figure 1: The construction of G l for l = 4

Boldi and Vigna used in[START_REF] Boldi | Fibrations of graphs[END_REF] the term "non-stuttering" to denote such paths.

Partially supported by National Science Centre grant DEC-2011/02/A/ST6/00201.

• Edges e 1 and e 2 were defined in Stage 4. Then, p ∈ {2, 3} and i ∈ {0, . . . , l}.

We first consider the case of p = 3, i.e., when i < l and port p leads up to level i + 1. We have:

next p (v i (j 1 )) = v i+1 (π i (j 1 )), end p (v i (j 1 )) = 2, next p (v i (j 2 )) = v i+1 (π i (j 2 )), end p (v i (j 2 )) = 2.

Claim (iv) follows directly, and so does claim (iii), taking into account that by Lemma 3.1(iii):

In the case of p = 2, i.e., when i > 0 and port p leads down to level i -1, we have:

We obtain the claims as in the previous case, this time noting that since π i-1 is an involution, we have π -1 i-1 ≡ π i-1 , and we can apply Lemma 3.1(iii) for π i-1 to show Claim (iii).

Lemma 3.3 Consider a pair of nodes

Then, the views of nodes v i (j 1 ) and v i (j 2 ) are equal at least up to depth δ, V δ (v i (j 1 )) = V δ (v i (j 2 )).

Proof:

The proof proceeds by induction with respect to δ. When δ = 1, by Lemma 3.2(i), the nodes v i (j 1 ) and v i (j 2 ) have the same degree d, and by Lemma 3.2(iv), after traversing an edge labeled with any port p ∈ {1, . . . , d} from either node, we enter the adjacent node by the same port:

Now, let δ > 1 and suppose that the claim of the lemma holds for all δ ≤ δ -1. Again, by Lemma 3.2(i) and (iv), the nodes v i (j 1 ) and v i (j 2 ) have the same degree, and after traversing an edge labeled with any port p ∈ {1, . . . , d} from either node, we enter the adjacent node by the same port. Moreover, we have by Lemma 3.2(iii) that δ(next p (v i (j 1 )), next p (v i (j 2 )) ≥ δ -1, and, by Lemma 3.2(ii), next p (v i (j 1 )) and next p (v i (j 2 )) belong to the same level of G l . Hence, by the inductive assumption, V δ-1 (next p (v i (j 1 ))) = V δ-1 (next p (v i (j 2 ))). Since port p was arbitrarily chosen, it follows from the recursive definition of the view that V δ (v i (j 1 )) = V δ (v i (j 2 )), and so we have the claim.

Observe that the nodes a l = v l (0) and b l = v l (2 l-1 ) have distinct views in G l . Indeed, consider a sequence of l traversals along port 2, starting from nodes a l and b l . We argue, by induction on i ∈ {0, . . . , l -1}, that after i edge traversals the node reached from a l is v l-i (0), and the node reached from b l is v l-i (2 l-1-i ). For i = 0 the claim is trivial and hence assume that it holds for some 0 ≤ i < l -1. The edge with port number 2 at v l-i (0) clearly leads to v l-1-i (0) as required. Hence, it remains to argue that there is an edge between v l-i-1 (2 l-2-i ) and v l-i (2 l-1-i ) in G. According to construction of edges between the levels l -2 -i and l -1 -i in Stage 4, we need to argue that π l-1-i (j) = 2 l-1-i , where j = 2 l-2-i .

(

We now consider the nodes a l , b l ∈ V (G l ) satisfying Proposition 3.1, and characterize their (truncated) views within graph ξ D (G l ).

Lemma 3.4 For any

Proof: In order to prove that V Di (a l ) = V Di (b l ), we will use the characterization from Claim 2.1. Let P j = (u j 0 , u j 1 , . . . , u j kD ), j ∈ {1, 2}, be any two non-backtracking paths in ξ D (G l ) such that u 1 0 = a l and u 2 0 = b l . By construction, P j = (u j 0 , u j D , u j 2D , . . . , u j kD ) is a path in G l for each j ∈ {1, 2}. By the definition of port labeling of ξ D (G l ), for paths ending at nodes within V (G l ), the port labelings of P 1 and P 2 are identical if and only if the port labelings of P 1 and P 2 are identical. Thus, P 1 and P 2 are isomorphic in ξ D (G l ) if and only if P 1 and P 2 are isomorphic in G l . Since i ≤ l -1, by Claim 2.1 we obtain that V Di (a l ) = V Di (b l ). The fact that V(a l ) = V(b l ) follows from similar arguments.

Final remarks

We have shown a tight lower bound of Ω(D log(n/D)) on the depth to which the views of a pair of nodes of a symmetric anonymous network need to be checked in order to decide if their views in the graph are different. We remark that our problem of view distinction can be generalized in the following two directions:


Nicolas Amiot

Mohamed Laaraiedh

come

PyLayers: An Open Source Dynamic Simulator for Indoor Propagation and Localization Nicolas Amiot, Mohamed Laaraiedh , Bernard Uguen University of Rennes 1, IETR Email: {nicolas.amiot, mohamed.laaraiedh, bernard.uguen}@univ-rennes1.fr Abstract-In this paper, we introduce PyLayers a new open source radio simulator built to tackle indoor localization problem. PyLayers has been designed to simulate complete dynamic scenarios including the realistic movement of persons inside a building, the transmission channel estimation for multiple radio access technologies and the position estimation relying on location-dependent parameters originated from the simulated OSI physical layer. The channel is estimated by using a fast graph-based ray tracing method. From these simulated data, location dependent parameters, such as received power or time of arrival, can be deduced. The realistic movement of persons into the building layout is modeled with a virtual forces approach. The simulated data can be directly used with one of the builtin localization algorithms or be exported to various standards extensions. Finally, the accuracies of both the channel estimation and the localization are compared to measurements and show a good match.

Index Terms-Simulator, propagation, localization, raytracing, multi-wall, mobility model, graph theory

I. INTRODUCTION

E VALUATING performances of an indoor localization al- gorithm is often a complicate task because performances highly depend on the chosen test environment. Three main approaches are generally retained to perform such an evaluation. First one consists in using statistical models. Those statistical models are very efficient tools for obtaining a global trend of the algorithm accuracy. However, when the simulation scenario becomes very specific, this approach is often not sufficient. For more complex scenarios, a measurement campaign can be realized. The use of measurements is probably the best solution in terms of data quality. In return, it's also a laborious task in terms of realization and post processing. An intermediate solution is to use simulators. Simulators are convenient because they combine the accuracy of measurements and ease to use of statistical model. Nevertheless, the accuracy of the simulated data are conditioned by the realism level of the simulator.

Most of available radio estimators such as [START_REF] Esparza | Simulation of indoor lte behaviour[END_REF] are efficient in channel estimation but not necessary adapted for localization purposes. The channel impulse response is not directly an input of a localization algorithm. In addition, those tools are generally built for specific bandwidths for a given standard, and this prevent e.g. the validation of heterogeneous localization algorithms. Furthermore, movements of persons are generally simulated with random models or more generally by a Markov chain [START_REF] Nielsen | On the impact of information delay on location-based relaying: A markov modeling approach[END_REF]. However, those approaches only capture the human mobility at a large scale, and don't take into consideration small scale e.g. attracting points of a room.

The aim of PyLayers [3] is to provide a transversal, versatile and upgradable simulator for indoor propagation and localization: Transversal because it addresses multiple simulation issues (mechanical, radio, localization); Versatile because each part of simulation is independent and different type of radio access technologies (RATs) are envisaged; Upgradeable because it is an open source project, coded with Python and standard scientific high level libraries Numpy, Scipy, NetworkX and Matplotlib. In the following, the four specific fields of simulation, so-called layers, of PyLayers are presented from section II-A to section II-D. Then, the simulator outputs are shown and compared to measurements in section III.

II. PYLAYERS STRUCTURE: MULTI-LAYERS DESCRIPTION

PyLayers is a complete dynamic simulator for indoor propagation and localization based on graphs description. As shown on Fig. 1, the simulator is based on four layers: layout, mechanical, network and localization. Each layer regroups various toolboxes and operates independently from each other, but data from each layer can be shared with the others, e.g. the positions computed at the mechanical layer can be used by the network layer.

A. The Layout layer

The Layout layer allows to precisely describe a simulation scene, in terms of outlines, used materials and radio propa-gation paths. These layout properties are distributed on four graphs of the layout layer:

• The structure graph G s (Fig. 2)

• The graph of rooms G r (Fig. 3)

• The visibility graph G v (Fig. 4)

• The topological graph G t (Fig. 5) The structure graph G s is used to describe the layout outlines and the materials used in the scene. Conventionally, the nodes with a positive index describes walls, whereas the nodes with a negative index describe vertexes. The edges of G s link two nodes with a positive and a negative index respectively. The graph of rooms G r describes all the mechanical paths between the rooms. It is built as a sub-graph of G s , by retaining only cycles which possess at least one door. It is especially used by the mechanical layer. The graph of visibility G v share its nodes with the structural graph G s . Its edges link nodes who share an optical visibility. It is used by the network layer to perform the estimation of location dependent parameters (LDPs). The topological graph G t contains information about room connections in term of electromagnetic propagation. Indeed, it allows to fast linking any position inside the layout to G v . It results from the determination of all the close set of nodes, , a.k.a. the cycle, of the graph G s . A complete description of these graphs is available in [START_REF] Uguen | Exploiting the graph description of indoor layout for ray persistency modeling in moving channel[END_REF]. Fig. 2: the structure graph Gs, describes both the outlines of the layout linking vertexes (hatched circles) and walls (white circles), and the materials of the walls (not represented here).

B. The Mechanical layer

To ensure dynamic and layer independence, all the upcoming layers processing are based on the SimPy library Fig. 5: The topological graph Gt is used to quickly links the Gv cycles. [START_REF]SimPy[END_REF]. SimPy is a discrete event simulator which allows the simulation of active components. In particular, the mechanical layer uses the Personal Rapid Transit Simulation [START_REF] Macleod | Personal Rapid Transit Simulation[END_REF], a SimPybased library which defines the movement of persons. In PyLayers, persons are called agents. Agents are independent instances moving into the layout. The movement of the agents is implemented by taking into account the 2 of the 3 major properties of the human mobility [START_REF] Karamshuk | Human mobility models for opportunistic networks[END_REF]:

1) Temporal, which defines time dependent action of the movement, 2) Spatial, which defines the physical nature of the movement.

The temporal property describes where agents are moving into the layout, e.g. having a target and knowing the path to reach that target. In PyLayers, the target is defined as a room and the path as a succession of rooms. The path from a room i to a targeted room t is obtained with the help of graph G r . Rooms i and t corresponds respectively to nodes v i r and v t r of G r . Then, the path is obtained with D, a Djikstra [START_REF] Dijkstra | A Short Introduction to the Art of Programming[END_REF] shortest path algorithm:

V p = D(v i r , v t r ). (1)
The ordered set of node V p describes the shortest path between v i r and v t r . To achieve the complete trajectory from i to t, the agent go iteratively through all the room corresponding to the nodes of V p . Hence each time a node of V p is reached, the next one becomes an intermediate target it, until the node v t is reached. With regard to Fig. 3, if the agent is in room i = 1 and its target is room t = 10, the returned path is V p = {1, 8, 10}. Thus, the agent will first move from room 1 to its intermediate target 8. Once the agent has reached the center of room 8, it moves to its final target in room 10.

Once the path has been computed, the agents are moving by taking into account the layout environment, such as walls and doors. This is the spatial property of the movement. That spacial property of the human mobility has been modeled using magnetic forces [START_REF] Teknomo | Microscopic Pedestrian Flow Characteristics: Development of an Image Processing Data Collection and Simulation Model[END_REF]. The magnetic force model aims to obtain a resulting acceleration vector a to drive the agents through the layout. The magnetic force model supposes that the agents and the layout environment can be assimilated to positive poles unlike the intermediates target which can be assimilated to negative poles. Each agent k is potentially under the influence of several magnetic forces: an attractive magnetic force F it which attracts the agent to its intermediate target node v it ; several repulsive magnetic forces F r , which avoid the collision of the agent with the walls or with another agent. According to [START_REF] Teknomo | Microscopic Pedestrian Flow Characteristics: Development of an Image Processing Data Collection and Simulation Model[END_REF], it is possible to approximate the attractive magnetic force F k it on agent k, with the Coulomb's law:

F k it ≈ q k q it ||R k,ig || 2 Rk,it , (2)
with q k and q it the intensities of the magnetic load of the agent and the intermediate target respectively, R k,it the vector from the agent k to the intermediate targeted node v ig . In order to be close to a human being mobility, we suppose that agents are not grazing the walls. Then the repulsive force must be maximal along the wall . Thus, we propose to model the repulsive magnetic forces F r with:

F r (d k,w ) = α ||d k,w || 2 dk,w , (3)
with d k,w the distance vector from the agent k to a wall w and α a parameter to adjust the repulsion. Similarly, the interagent avoidance can be modeled with (3), by replacing d k,w by d k,l where k and l are two different agents. Then, the acceleration vector a k of the agent k with regard to the environment can be written as the sum of three previously described interactions:

a k = F k ig + W w F r (d k,w ) + K l =k F r (d k,l ), ( 4
)
where W is the number of walls in the vicinity of the agent k.

The vicinity of the agent is determined with a simple distance threshold. The use of that threshold avoids the computation of the forces from all the walls of the entire layout. An example of operation of the mechanical layer can be seen in [START_REF]PyLayer mechanical layer example[END_REF].

C. The Network layer

The network layer describes all radio interactions between the nodes of the entire network, to obtain channel impulse response (CIR) and/or LDPs. Like the layout layer, the network layer has a graph description. The nodes V n of network graph G n have three attributes:

• type: agent or anchor, • emitted power in dBm, • receiver sensitivity in dBm. On the edges of G n , LDPs between nodes are computed. In order to manage multiple RATs between nodes, G n is built as a multi-graph. A multi-graph is a graph where several parallel edges can link two nodes [START_REF] Bollobás | Modern Graph Theory: Béla Bollobás[END_REF]. This multi-graph description allows to describe each RAT on a different edge of the graph. Fig. 6: Example of graph of network Gn which shows all the links between 4 radio nodes on 2 different RATs. The multi-graph approach can be observed between nodes 1 and 7, which are linked with two different edges.

On each edge are evaluated the received power (Pr) and the time of arrival (TOA) for ultra wide band RAT. Those LDPs are computed either in real-time with a modified COST-231 multi-wall approach [START_REF] Damosso | DGX III[END_REF], or post processed with the graphbased ray-tracing approach completely described in [START_REF] Uguen | A comprehensive mimo-uwb channel model framework for ray tracing approaches[END_REF]. The standard COST-231 multi-wall approach consists in evaluating the losses by taking into account the intersection between walls and the ray which link the two nodes. In that model, losses from walls materials are computed supposing a specular incidence angle. The PyLayers multi-wall model adds to that standard model a computation of the losses from the walls by including the incidence angle. Hence, efficient transmission coefficient and excess delay through multi-materials walls can be computed using formulas given in [START_REF] Orfanidis | Electromagnetic Waves and Antennas[END_REF]. For the problem at hand, both the incidence angle and the material are required. The incidence angle on each wall is computed during the construction of G v while the constitutive materials can be retrieved using G s . The received power Pr can be easily evaluated by subtracting the computed losses from the transmission power. The TOA is obtained by adding the excess delay to the line of sight delay.

Alternatively, the LDPs can be obtained by a ray-tracing approach from CIR computation. This second approach requires a prior graph-based step: the determination of signatures. These signatures are then used to obtain rays. Let T be a device which tries to obtain LDPs from R, another device. The first step of signature computation consists in obtaining the two set of nodes V T t and V R t which are in direct visibility of T and R respectively. Then, a shortest path algorithm is computed on G v for each pair of nodes v T t and v R t of the set V T t and V R t respectively. The obtained minimal set of interactions between T and R is the so-called signature S. The procedure is described in Algorithm 1.

Algorithm 1 determination of signatures

Require: T ,R Require: G t ,G v V T t ← nodes of G t in direct visibility of T V R t ← nodes of G t in direct visibility of R for nt ∈ V T t do for nr ∈ V R t do S tmp = D(G v , n t , n r ) if length(S tmp ) < length(S) then S = S tmp end if end for end for
Obtaining CIRs using this approach requires to evaluate a numerous number of rays in G v . This computation is high time consuming and provide to obtain the LDPs in real time. On the other side, LDPs obtained from CIRs are more accurate than those obtained by multi-wall technique. The user can choose between the two approaches, depending on its final application.

D. The Localization Layer

The localization layer exploits the LDPs computed by the network layer to perform position estimation. Two types of methods have been implemented in the localization layer: Algebraic based methods [START_REF] Laaraiedh | Comparison of hybrid localization schemes using rssi, toa, and tdoa[END_REF] and geometric based method [START_REF] Amiot | Evaluation of a geometric positioning algorithm for hybrid wireless networks[END_REF]. The algebraic methods are based on maximum likelihood or on a weighted least square estimation to perform. The geometric based method use LDPs to build bounded regions of space called constraints. The geometrical intersection of those constraints define a smaller bounded region which contains the sought position. III. SIMULATOR OUTPUTS PyLayers provides numerous useful outputs and visualization tools for data post-processing and localization analysis.

From each layer, relevant information can be exported in standard format file (csv, Matlab). Hence, from the mechanical layer, a time-stamped log file is stored for each agent. It contains the position, the velocity and the acceleration vectors. That time-stamped exportation is also available for the LDPs of the network layer and the estimated positions of the localization layer.

The visualizations tools of PyLayers take advantage of the multi-graph description. If Figures 23456shows layout description graphs, further visualization tools are available. For instance, the transmission and reflection coefficients of each material from each part of G s can be displayed. Fig. 7 shows the modulus and the phase response of the transmission coefficients for a wood door as a function of the frequency. This standard PyLayers output can also be produced for walls with multiple stack of materials. As explained previously, these transmission coefficients are used by the multi-wall algorithm to estimate Pr and TOA. The coverage tool extends the computation from a single link to the whole layout, and thus provides a map of either the received power (Fig. 8), or the excess delay (Fig. 9). The received power map in addition of received power value may also provide information on areas under the receiver sensitivity and areas under the noise floor. The map of excess delays informs about the delay introduced by the walls contributions.

The accuracy of CIRs obtained using PyLayers can be observed on Fig. 10 which compares measurements from [START_REF]Deliverable 4.1: Measurements of locationdependent channel features[END_REF] and simulations along the same trajectory. paths are retrieved in simulations with a correct delay. This is especially observable for the first arriving path which is mandatory for an accurate TOA estimation. However, it is noticeable that simulations provide a lower density of paths. This is due to the number of interactions considered during the simulation and the ignoring of pieces of furniture in the layout description. By focusing on a single CIR on Fig 11, it is confirmed that most of the paths and especially the first NLOS path are correctly estimated in terms of delay and amplitude. However, on the simulated plot, a lack of signal can be observed between 25 ns and 35 ns. This difference is due to a simulation setup which limit the number of considered multi-paths. Increasing the number of paths would increase the computation time but would allow to better fit with the measurements.

IV. CONCLUSIONS

This paper has presented an overview of PyLayers, an open source dynamic radio simulator for indoor propagation and localization. The simulator is built as a stack of specific capabilities named layers. Each Layer takes advantage of a graph description to simulate the realistic movement of persons, to model the propagation channel, and to perform localization estimation. A comparison against realistic measurements has shown that the simulator is able to provide accurate CIRs and LDPs. Our current work consists in both improving the global computation speed, and add localization layer visualization tools. Future work consists in adding the OSI MAC layer mechanisms. Finally, due to the open source aspect of the project, we also invite any interested person to use, test, or propose improvements of any parts of the project, by forking the following GitHub repository : https://github.com/PyLayers/PyLayers.

Fig. 1 :

 1 Fig. 1: Conception of PyLayers in four independent layers.

Fig. 3 :

 3 Fig. 3: The graph of room Gr describes the possible paths of agents.

Fig. 4 :

 4 Fig.4: The visibility graph Gv describes all the possible electromagnetic paths through the layout walls.

Fig. 7 :

 7 Fig. 7: Modulus and phase of transmission coefficient for a wood door as a function of the frequency.

Fig. 8 :Fig. 9 :

 89 Fig.8: Map of received power. The black triangle is the transmitter position. The white area represents power under the noise floor, the grey area represents power under receiver sensitivity, elsewhere is the received power in dBm

Fig. 10 :

 10 Fig. 10: Comparison of Measured (on the top) and Simulated (above) CIRs along an indoor trajectory.

Me a s ure m e nts Simulations Fig. 11 :

 Simulations11 Fig. 11: Example of measured and simulated CIRs.

ACKNOWLEDGMENT

The work presented in this paper has been performed in the framework of the FP7 project ICT-248894 WHERE2 (Wireless Hybrid Enhanced Mobile Radio Estimators -Phase 2) which is funded by the European Union.


Nicolas Amiot
email: nicolas.amiot@univ-rennes1.fr

Meriem Mhedhbi #
email: meriem.mhedhbi@univ-rennes1.fr

Bernard Uguen #
email: bernard.uguen@univ-rennes1.fr

Raffaele Derrico
email: raffaele.derrico@cea.fr

WBAN Off-Body Channel Angular Structure Comparison between SAGE Estimation and Ray Tracing Simulation

Keywords: Body Area Networks, Ray tracing, Channel model, Multipath Channels, Path Loss, Direction-of-Arrival, SAGE

In this paper, we present a comparison between Off-Body channel characteristics estimated with Space-Alternating Generalized Expectation-Maximization (SAGE) algorithm from measurement data and those obtained from ray-tracing simulated data. Measurement data were obtained considering a body-worn antenna on a phantom and an external one simulating an access point. The chosen simulation approach takes into account the influence of the body directly into the antenna radiation pattern, and not by including a dedicated body representation into the simulated environment. This simplified approach provides a good agreement between simulation and measurement in terms of received power and Angle of Arrival retrieval.

I. INTRODUCTION

Considering both the emergence of wearable devices (smart watches, connected glasses) carried by the quantified-self trend, and Ultra Low Power radio technologies capabilities enabled by e.g. the Ultra Wideband (UWB), Wireless Body Area Networks (WBAN) could be massively disseminated in the public space in the near future.

Regarding the limited available energy and interoperability requirements of those devices, a good understanding of channel characteristics has a fundamental importance in order to design operative and reliable communication systems [START_REF] Hall | Antennas and propagation for body centric communications[END_REF] [START_REF] Molisch | Ultra-wide-band propagation channels[END_REF]. Indeed, Physical layer (PHY), Medium Access Control (MAC) and Upper Layers protocols performances are strictly dependent to the knowledge of propagation mechanisms and channel models. Consequently, different WBAN channels depending on the wireless node position have to be defined [START_REF] Chavez-Santiago | Propagation models for ieee 802.15.6 standardization of implant communication in body area networks[END_REF].

In the particular case of the Off-Body channel, one of the end points of the link designates a device placed on a human body and the other, far from it, is an external fixed device e.g. a gateway or a router [START_REF] Maman | Research trends in wireless body area networks: From on-body to body-to-body cooperation[END_REF].

A deterministic description of the Off-Body channel should consider diffraction and/or shadowing effect of the body(ies) parts, in addition to the classical propagation phenomena. The use of a ray-tracing (RT) tool can be considered in the specific context of WBAN for predicting the Off-Body channel, allowing the future design of communication and localization systems.

Such a simulator has to accurately take into account both the movement of the body and the associated on-body antennas positions, orientations and perturbed radiation pattern. Indeed, one of the specific aspect of the WBAN channel is the dependency of antenna characteristics on the body [START_REF] Conway | In situ measurement of uhf wearable antenna radiation efficiency using a reverberation chamber[END_REF] [6] [START_REF] Cotton | A review of radio channel models for body centric communications[END_REF], where the proximity of a human body affects the antenna radiation pattern and thus the channel observation. Then, it is mandatory to properly describe the antenna at both ends of the radio link to correctly predict the channel in terms of power and angles of arrivals (AoA).

The open source mobility-oriented ray-tracing tool PyLayers [START_REF] Amiot | Pylayers: An open source dynamic simulator for indoor propagation and localization[END_REF][9] provides a multi-cylinder description of the human body in order to address WBAN scenarios. It also allows to modify the radiation pattern of the antenna depending on the body antenna distance through a compact parametric model using spherical harmonics decomposition of the complex radiation pattern [START_REF] Mhedhbi | Modelling of uwb antenna perturbed by human phantom in spherical harmonics space[END_REF].

Within this context, this paper illustrates, through a comparison with measured data, the capability of a RT approach to recover the channel angular structure of specific Off-Body channel.

Section II provides information about the measurement setup, the chosen spatial configuration of the measured scene and the used antennas. Section III describes the modeled synthetic environment and the antennas used for simulation. Section IV focuses on the comparison between measurement and simulation in terms of path loss and angular delay spread.

II. MEASUREMENT SETUP

The UWB Off-Body channel measurements have been performed at CEA-Leti in the frequency range [3 -10] GHz. A CTIA/IEEE standardized phantom located on a (X, Y) positioner and a 4 ports VNA have been used. The Off-Body antenna has been placed on a mast, thus representing an external access point, and three on-body antennas has been placed on the torso, the left shoulder and the back of the phantom. These on-body locations have been chosen according the application scenarios of the CORMORAN project [START_REF]ANR CORMORAN[END_REF].

More precisely, they represent the identified favorite onbody locations for the Coordinated Group Navigation (CGN) applications.

The measurement campaign has consisted in both obtaining received power measurements and estimating the parameters of the multi-path components (MPC) by using a SAGE algorithm [START_REF] Fleury | Wideband angle of arrival estimation using the sage algorithm[END_REF] [START_REF] Fleury | Channel parameter estimation in mobile radio environments using the sage algorithm[END_REF]. In particular, the estimation allows to determine the the number of paths, their amplitudes, delays and AoA. SAGE algorithm has been implemented in the frequency domain for the mathematical suitability with UWB signals.

Figures 1 illustrates the measurement setup with the Off-Body antenna and the phantom. Both are separated by a distance d of f . The phantom can be rotated from 0 • to 315 • with a step equal to 45 • . The red dots on the phantom indicate the positions of antennas. The body-worn antenna has been moved over a spatial grid, for different phantom orientation. In addition, measurements have also been realized in the absence of the human body (isolated antenna). With this setup, MPC could be determined in the case of isolated antenna and bodyworn antennas. The UWB extension of the SAGE algorithm described in [START_REF] Haneda | An application of SAGE algorithm for UWB propagation channel estimation[END_REF] has been employed to estimate the number of paths, their amplitudes, delays and an AoAs [START_REF] Pasquero | Angle of arrival characterization in uwb indoor off-body channel[END_REF].

A. Measurement Environment Description

Figure 2a and Figure 2b show respectively the floor plan and a picture of the measurement environment. The height between the floor and the ceil was 2.55m and 2.80m on the left half side and right half side of the room respectively. The height of the Off-Body antenna was 1.35m and the height of the isolated antenna was 1.33m. Those of the antennas located on the torso, the shoulder and the back, were respectively 1.33m, 1.40m and 1.35m. Finally, the height of the phantom when placed on the positioner was 1.75m. The green squares represent two positions of the virtual antenna array which is required for the MPC estimation of the SAGE algorithm. Let us note its size is not in scale compared to that of the room.

B. Antennas

The Off-Body antenna is an UWB Wire-patch monopole antenna, omni-directional in azimuth. Its radiation pattern in elevation for different frequency values is given in Figure 4a. The antenna placed on the body is an UWB printed dipole [START_REF] Gueguen | A low cost uwb printed dipole antenna with high performance[END_REF], omni-directional in azimuth in the isolated case. When the antenna is placed to the human body, its radiation pattern is modified depending on the operating frequency and distance from the body.

Furthermore, in the scenario using the isolated antenna which has been performed for studying the body influences, only one omni-directional antenna has been used at the phantom side.

III. DETERMINISTIC SIMULATION SETUP

A. Synthetic Environment Description

The described synthetic environment is a simplify version of the layout which does not include the large table in the room. The 3 internal walls are made of 10cm of plaster while the outside wall is made of 7cm of brick. Plaster and brick properties are defined in Table I, where r and σ are the electric permittivity and the electrical conductivity respectively. This environment description preserves the asymmetrical distribution of the path energy depending on the direction of arrival of the rays, because the level coming from the brick wall would be stronger than the level coming from the partition wall. In Figure 3, the rainbow colored shapes represent the antenna pattern on both transmitting and receiving sides and the black lines represent the rays obtained from a simulation. In this configuration, the two antennas are 8 meters distant. The antenna patterns correspond respectively to a wire-patch monopole (left) and to a nearby body antenna (right). The blue and red parts on the walls represent windows and the door respectively.

B. Antenna Modeling

Figure 4 shows (a) the Off-Body measured realized gain pattern of the wire-patch monopole antenna in the elevation plane, and (b) the antenna pattern used in the RT tool. The 3D simulated antenna pattern is close to measurement, with a maximum realized gain around 5dBi except from the horizontal to the bottom, where the simulated antenna present a higher gain than the actual measured gain. In the RT simulation, the presence of the phantom is taken into account through a perturbed antenna radiation pattern. The antenna used in measurement has been placed on cylindrical phantom with 30cm radius and an antenna-body separation of 5mm . Then, the gain patterns in elevation and azimuth have been obtained from a CST MWS TM simulation. These results are presented in Figure 5.

IV. COMPARISON MEASUREMENTS VS DETERMINISTIC SIMULATION

In this section, the PyLayers RT simulator is used to reproduce the measurement conditions presented in the previous sections. The goal is to check the ability of the tool to provide rich channel information in a rather controlled scenario.

A. Path Loss Comparison

As a first step, it is important to check the RT tool capability to deliver consistent path loss (PL) levels regarding the antennas and the propagation environment. In particular, by using the simplified approach consisting in including the body effect only through a perturbed antenna radiation pattern.

Figure 6, Figure 7 and Figure 8 illustrate the simulated PL obtained for 3 different positions of the body mounted antenna, respectively torso, shoulder and back. Notice that, the PL is accounted unconventionally as a negative number. The simulation considers the gain patterns described in III-B, which is close to the one expected in the real channel measurements.

As expected, for both measures and simulations, the more the phantom hides the Line of Sight, the greater the absolute value of the path loss (PL). More precisely, the absolute PL value is the lowest when the phantom orientation φ is equal to:

• 0 • for antenna located on the torso, • 0 • and/or 180 • for antenna located on the left shoulder,

• 180 • for antenna located on the back. The absolute value of the PL is the highest when the phantom orientation φ is equal to:

• 180 • for antenna located on the torso, • 90 • for antenna located on the left shoulder, • 0 • for antenna located on the back. For the three scenarios, a good agreement between measurement and simulation can be observed, both quantitatively and qualitatively. The observable differences of levels are due to higher gain of the simulated Off-Body antenna in some space directions. However, it is noticeable that the simulation with realistic antennas catches the modification of the path loss exponent in situation of strong shadowing, as it was observed in measurements. Indeed at angle values of 180 • , 90 • and 0 • for torso, shoulder and back respectively, the dependency with distance is observed as being almost flat.

B. Angular Delay Spread Comparison

We now compare the AoA estimations obtained by the SAGE algorithm to those obtained by RT including the perturbed antennas. The simulations have been done for two distances (d of f = 1m and d of f = 8m) in the case with nophantom and for a single distance (d of f = 8m) in others cases. All the antenna positions on the body (Torso, Shoulder It can be noticed that, in all cases, the number of observed MPC is lower in simulation than in measurement. Specifically, simulations show that no energy is caught by the simulator between 20m and 40m. This can be explained both by the lack of furnitures in the simulated environment, and by the fact that low-energy level rays are neglected. Those rays correspond to multiple bouncing rays between the walls behind the antennas. Moreover this discrepancy between simulated and measured results can depend on the SAGE algorithm tuning and capability to catch specular components.

In a first step, to have a reference situation, Figure 9 and Figure 10 compare the measurement and simulation of AoA distribution in situation without phantom, i.e. isolated antenna. This first validation step shows that both amplitude levels and angle distribution of the strongest paths are well recovered.

In the second step, we compare measurement and simulations with the body phantom. Recall that the presented simulations account for the body only through the surrounded antenna radiation pattern. For that purpose, the different antenna positions on the body have been obtained by rotating the antenna pattern.

Figure 11, Figure 12 and Figure 13 illustrate the results for the antenna placed on the torso, shoulder and back respectively, when d of f = 8m. Considering the left figure corresponding to the measurement for the 3 cases, torso, shoulder and back, we can notice that the direction of arrival, 0 • , 90 • and 180 • are consistent with the antennas configurations. This is also true for the simulation, whereas less paths are recovered especially the weakest. It is interesting to underline that the asymmetry introduced in the layout description (brick wall on the left, plaster wall on the right when looking along x axis) is well observed in e.g. Figure 11.

For simulation, when considering the distribution of the rays in the angle/distance domain a straight vertical line is observed. This results from a geometrical fact due to the chosen RT parametrization which emphasizes the rays reflected on the lateral walls and neglects weak rays emanating from the walls behind the antennas. Then, the prevalent relation observed in simulation between distance and angle in the This paper presented a comparison between data from an indoor UWB Off-Body measurement campaign on a phantom and the simulation from a site specific simulator. At that point of the investigation, the main features of the deterministic raytracing tool PyLayers have been validated for static scenarios starting from measurements. It has been shown that even with a simplified environment description and a fairly approximated antenna pattern on the body, the tool is able to retrieve the main channel characteristics. Moreover, it validates the idea that the influence of the human body in the channel can be modeled by a modified antenna pattern. This result open new perspectives for further PHY layer simulation, in particular for scenarios taken into consideration the body movement.

Figure 1 :

 1 Figure 1: (a) Side and (b) top representation of the Off-Body antenna and on-body antenna measurement configuration. The red dots on the phantom indicate the positions of on-body antennas on torso, shoulder and back.

Figure 2 :

 2 Figure 2: (a) The floor map and (b) picture of the measurement environment.

  Material properties used in RT simulation.

Figure 3 :

 3 Figure 3: 3D view of the synthetic environment. The two colored shapes are the antennas radiation patterns, the blue and red parts on the walls represent the door and windows respectively, and the black lines are the the rays obtained by the RT simulation.

Figure 4 :

 4 Figure 4: (a) Measured and (b) simulated Off-Body antenna pattern

Figure 5 :

 5 Figure 5: Body-worn antenna simulated pattern: (a) elevation and (b) azimuth

Figure 6 :

 6 Figure 6: (a) Measured versus (b) Simulated Path Loss, antenna mounted on torso

Figure 7 :

 7 Figure 7: (a) Measured versus (b) Simulated Path Loss, antenna mounted on shoulder

Figure 8 :

 8 Figure 8: (a) Measured versus (b) Simulated Path Loss, antenna mounted on back

Figure 9 :Figure 10 :

 910 Figure 9: (a) Measured versus (b) Simulated AoA at 1m, isolated antenna

Figure 11 :

 11 Figure 11: (a) Measured versus (b) Simulated AoA at 8 m, antenna mounted on torso

Figure 12 :

 12 Figure 12: (a) Measured versus (b) Simulated AoA at 8 m, antenna mounted on shoulder

Figure 13 :

 13 Figure 13: (a) Measured versus (b) Simulated AoA at 8 m, antenna mounted on back

ACKNOWLEDGMENT

This work has been carried out in the frame of the COR-MORAN project, which is funded by the French National Research Agency (ANR) under the contract number ANR-11-INFR-010.


Thierry Denoeux

Rejoinder on "Likelihood-based belief function: justification and some extensions to low-quality data"

Keywords: Statistical Inference, Dempster-Shafer Theory, Evidence Theory, Likelihood Principle, Uncertain data

This note is a rejoinder to comments by Dubois and Moral about my paper "Likelihood-based belief function: justification and some extensions to low-quality data" published in this issue. The main comments concern (1) the axiomatic justification for defining a consonant belief function in the parameter space from the likelihood function and (2) the Bayesian treatment of statistical inference from uncertain observations, when uncertainty is quantified by belief functions. Both issues are discussed in this note, in response to the discussants' comments.

I thank the discussants, Dr. Dubois and Prof. Moral, for there insightful and thought-provoking comments about my paper "Likelihood-based belief function: justification and some extensions to low-quality data" published in this issue [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF][7] [START_REF]Comments on "Likelihood-based belief function: Justification and some extension to low-quality data[END_REF]. Both discussants questioned some of the axioms I proposed in order to justify the method for defining a consonant belief function from the likelihood function introduced by Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF]. Additionally, Moral [START_REF]Comments on "Likelihood-based belief function: Justification and some extension to low-quality data[END_REF] argued for a Bayesian analysis of statistical inference from uncertain observations, different from the approach presented in [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF]. These two issues are further examined below, in response to the discussants' comments.

Axiomatic justification of likelihood-based belief functions

In [START_REF] Shafer | A mathematical theory of evidence[END_REF], Shafer introduced a method for modeling statistical evidence using a consonant belief function. In [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF], I attempted to justify this method axiomatically by reasoning as follows. Let X ∈ X denote the observable data, θ ∈ Θ the parameter of interest and f (x; θ) the probability mass or density function describing the data-generating mechanism. Having observed a realization x of X, we wish to quantify the uncertainty on Θ using a belief function Bel Θ (•; x). Which properties should Bel Θ (•; x) have? In [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF], I proposed the following three requirements: The first two requirements jointly imply that the contour function pl(θ; x) associated to Bel Θ (•; x) should be proportional to the likelihood function:

pl(θ; x) ∝ L(θ; x). (1)
Assuming the commonality ordering [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF] to be relevant for comparing the informational content of belief functions, the third requirement, together with the other two, then yields a unique solution, which is the consonant belief function whose contour function is the relative likelihood function:

pl(θ; x) = L(θ; x) sup θ ∈Θ L(θ ; x) . (2)
Dubois [START_REF] Dubois | On various ways of tackling incomplete information in statistics[END_REF] and Moral [START_REF]Comments on "Likelihood-based belief function: Justification and some extension to low-quality data[END_REF] both acknowledge that this formal result provides a justification for viewing the normalized likelihood function as defining a consonant belief function, a view that has been shared by several authors (see, e.g., [START_REF] Ph | Possibilistic inference from statistical data[END_REF], [START_REF] Wasserman | Belief functions and statistical evidence[END_REF], [START_REF] Aickin | Connecting Dempster-Shafer belief functions with likelihood-based inference[END_REF], among others). However, they also claim that the axioms that support this solution (in particular, requirements 2 and 3 above) are questionable and that, consequently, they are not sufficiently compelling to rule out alternative methods of statistical inference in the belief function framework. I can only agree with the discussants on this point. Indeed, I never claimed that the approach advocated in [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF] is the only acceptable one for statistical inference in the belief function framework. As a matter of fact, formal requirements justifying a solution to some problem are rarely unquestionable or self-evident (see, e.g., the long-lasting debates on Savage's or Cox's axioms [START_REF] Shafer | Savage revisited (with discussion)[END_REF], [START_REF] Van Horn | Constructing a logic of plausible inference: a guide to Cox's theorem[END_REF], [START_REF] Shafer | Comments on "Constructing a logic of plausible inference: a guide to Cox's Theorem[END_REF]). The axiomatic approach only lays bare some basic principles, from which the solution can be derived. These principles should be as "natural" or "reasonable" as possible. However, accepting or rejecting them is a matter of personal judgement.

Dubois [START_REF] Dubois | On various ways of tackling incomplete information in statistics[END_REF] is, of course, right to point out that the informational ordering of belief functions based on their commonalities is not the only "reasonable" one. Other examples are the ordering based on plausibilities, the specialization ordering, as well as orderings based on the canonical decomposition of belief functions, as introduced in [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]. None of these orderings seems to qualify as the unique way of comparing the information content of belief functions. Similarly, there is no unique equivalent of Shannon's entropy for measuring the degree of uncertainty of belief functions (see, e.g., [START_REF] Pal | Uncertainty measures for evidential reasoning I: A review[END_REF], [START_REF] Klir | Uncertainty-Based Information. Elements of Generalized Information Theory[END_REF]). Consequently, any application of the Least commitment Principle [START_REF] Dubois | The principle of minimum specificity as a basis for evidential reasoning[END_REF][START_REF] Ph | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF] can be criticized as being based on a more or less arbitrary choice of an ordering or an uncertainty measure. Some arguments in favor of one informational ordering or another might be found in the future. It seems unlikely, though, that such arguments will be strong enough to discard other solutions. I am more inclined to accept the coexistence of several notions of information content for belief functions, just as there exist several notions of independence (see, e.g., [START_REF] Ben Yaghlane | Belief function independence: I. the marginal case[END_REF], [START_REF] Ben Yaghlane | Belief function independence: II. the conditional case[END_REF], [START_REF] Couso | Independence concepts in evidence theory[END_REF]).

In his comments, Moral [START_REF]Comments on "Likelihood-based belief function: Justification and some extension to low-quality data[END_REF] focuses his criticism on the second requirement, namely, that combining the belief function induced by observations with a Bayesian prior using Dempster's rule yield the Bayesian posterior. Indeed, the belief function induced by two independent samples is not equal to the orthogonal sum of the belief functions induced by each of the samples. As noted in [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF], this remark suggests that Dempster's rule is not the only reasonable mechanism for pooling statistical evidence, which leaves open the possibility of defining other ways of combining a Bayesian prior with a belief function induced by the data. Starting from this observation, Moral [START_REF]Comments on "Likelihood-based belief function: Justification and some extension to low-quality data[END_REF] proposes two alternatives to the consonant belief function induced by [START_REF] Ben Yaghlane | Belief function independence: I. the marginal case[END_REF]. However, while these two alternative solutions make sense in the imprecise probability framework, when interpreting upper probabilities as lower selling prices [START_REF] Walley | Upper probabilities based on the likelihood function[END_REF], they appear to be weakly justified in the belief function framework. Actually, one of the proposed solution (denoted by P 4 ) is not a plausibility function, and it is not known how consistency of the other solution (denoted by pl 3 ) with Bayesian inference could be achieved.

To conclude this section, we might observe that, while the discussants' criticisms are partly well-founded, they do not point to any better justified alternative to the method advocated in [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF] for representing statistical evidence in the belief function framework.

Here, x = 1 if the drawn ball is green, and x = 0 otherwise; Ω = {c, nc}, where c stands for "color-blind" and nc for "not color-blind"; and the probability distribution on Ω is defined by p(c) = 0.2 and p(nc) = 0.8. If the observer is not color-blind, we know that the ball that has been drawn from the urn is green; otherwise, we only know that it is either red or green. Such evidence can then be modeled by a multi-valued mapping Γ from Ω to 2 X such that Γ(nc) = {1} and Γ(c) = {0, 1}.

In this example, it can be assumed that E corresponds to the proposition "The observer reports that the ball is green". The two independence assumptions make sense: the fact that the observer is color-blind does not depend on the color of the ball being drawn from the urn, and the probability that the observer will report the ball to be green does not depend on the proportion of green balls in the urn, if we already know the color of the ball as well as the state of the observer (color-blind or not). Assumption (5), though, is more problematic. In this example, it implies that P (E|0, c) = 1 and P (E|1, c) = 1, which means that, if the observer is color-blind, he will report for sure the ball to be green, whatever its real color. This assumption is quite strong and it does not seem to be implied by the initial story. We may simply not know what a color-blind observer would report if the ball was green or red.

The analysis presented in [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF] is based on the interpretation of a piece of evidence as a message with uncertain meaning [START_REF] Shafer | Constructive probability[END_REF]. Here, the report that the ball is green can be seen as a message with two possible meanings: if the observer is not color-blind, it means that the ball is really green; otherwise, it means that the ball is either red or green. Let us detail the analysis in [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF] by explicitly introducing the meaning M of the message, taking values in 2 X . We note that the introduction of this variable taking values in the power set of X is not artificial, as suggested in [START_REF]Comments on "Likelihood-based belief function: Justification and some extension to low-quality data[END_REF]; it is inherent in the interpretation of belief functions as representing pieces of evidence. The relation between ω and M given E is determined by the multi-valued mapping Γ:

p(M = A|E, ω) = 1 if Γ(ω) = A, 0 otherwise. (6) Now, f (θ|E) = ω∈Ω,A⊆X f (θ|ω, M = A, E)p(ω, M = A|E). (7)
We have

p(ω, M = A|E) = p(M = A|ω, E)p(ω|E) (8a) = m X (A) if Γ(ω) = A, 0 otherwise, (8b)
and f (θ|ω, M = A, E) = f (θ|M = A) (once the meaning of the message is known, the state of the observer becomes irrelevant). Consequently,

f (θ|E) = A⊆X f (θ|M = A)m X (A). (9)
Now, knowing that the meaning of the message is A is the same as knowing that X ∈ A, and nothing more. Hence,

f (θ|M = A) = f (θ|X ∈ A) = P X (A|θ)π(θ) P X (A) , (10)
and

f (θ|E) = π(θ) A⊆X P X (A|θ) P X (A) m X (A), (11)
which is identical to Equation (42) in [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF]. In the example considered here, we have, assuming a uniform prior: f (θ|E) = P X ({1}|θ) P X ({1}) m X ({1}) + P X ({0, 1}|θ) P X ({0, 1}) m X ({0, 1}). [START_REF] Pal | Uncertainty measures for evidential reasoning I: A review[END_REF] As P X ({1}|θ) = θ and P X ({1}) = θπ(θ)dθ = 1/2, we have

f (θ|E) = 1.6θ + 0.2. ( 13
)
In contrast, the generalized likelihood function The Bayesian analysis (with the above assumptions) and the D-S analysis thus yield different results even in the case of a uniform prior, as claimed in [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF].

  [START_REF] Ben Yaghlane | Belief function independence: II. the conditional case[END_REF] isL(θ|E) = L(θ|1)pl(1) + L(θ|0)pl(0)

  1. Likelihood principle: Bel Θ (•; x) should only depend on the likelihood function, defined by L(θ; x) = αf (x; θ) for all θ ∈ Θ, where α is any positive multiplicative constant. 2. Compatibility with Bayesian inference: if a Bayesian prior π(θ) is available, combining it with Bel Θ (•; x) using Dempster's rule should yield the Bayesian posterior. 3. Least Commitment Principle: Bel Θ (•; x) should be the least committed belief function, among all those satisfying the previous two requirements.

Bayesian analysis of inference from uncertain data

In [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF], I considered the situation where the data x are imperfectly observed, and uncertainty about x is described by a mass function m X induced by a finite random set (Ω, 2 Ω , P Ω , Γ) (to simplify the discussion, the sample space X is assumed to be finite). I then proposed an extension of the likelihood function to such uncertain data, as:

where pl(x) is the contour function associated to m X . This corresponding contour function in the parameter space is then

which is a proper generalization of (2). In [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF], I also proposed a Bayesian analysis of this problem, and arrived at the conclusion that the posterior probability function f (θ|m X ) given m X is not proportional to pl(θ; m X ), which means that the Dempster-Shafer and Bayesian analyses of this problem yield different solutions.

In his comments [START_REF]Comments on "Likelihood-based belief function: Justification and some extension to low-quality data[END_REF], Moral proposes an alternative Bayesian analysis, which he claims to be "the most natural" and which yields a solution equivalent to (3). To clarify the discussion, we need to examine in detail the assumptions underlying the two solutions.

Moral models a piece of evidence as a propositional variable E depending on x and ω, such that

Assuming (a) the independence of X and Ω and (b) the conditional independence of E and θ given x and ω, he then finds P (E|θ) to be identical to L(θ; m X ) in [START_REF] Ben Yaghlane | Belief function independence: II. the conditional case[END_REF]. The posterior probability mass or density function f (θ|E) (with our notation) is then proportional to P (E|θ)π(θ). The meaning of these assumptions can be better understood using a simple concrete example. Consider an urn containing red and green balls. A ball is drawn from the urn, and an observer reports that the ball is green. However, there is 20 % chance that the observer is color-blind. What can we say about the proportion θ of green balls?