Some Results for Identification for Sources and its Extension to Liar Models

Let (${cal U}, P$) be a source, where ${cal U} = {1,2,dots,N}, P = {P_1, P_2, dots, P_N}$, and let ${cal C} = {c_1,c_2,dots,c_N}$ be a binary prefix code (PC) for this source with $||c_u||$ as length of $c_u$. Introduce the random variable $U$ with Prob($U=u$) = $p_u$ for $u = 1,2,dots,N$ and the random variable $C$ with $C = c_u = (c_1,c_2,dots,c_{u||c_u||})$ if $U=u$. We use the PC for noiseless identification, that is user $u$ wants to know whether the source output equals $u$, that is, whether $C$ equals $c_u$ or not. The user iteratively checks whether $C$ coincides with $c_u$ in the first, second, etc. letter and stops when the first different letter occurs or when $C = c_u$. What is the expected number $L_{cal C}(P,u)$ of checkings? In order to calculate this quantity we introduce for the binary tree $T_{cal C}$, whose leaves are the codewords $c_1,c_2,dots,c_N$, the sets of leaves ${cal C}_{ik} (1 leq i leq N; 1 leq k)$, where ${cal C}_{ik} = {c in {cal C}: c$ coincides with $c_i$ exactly until the $k$'th letter of $c_i}$. If $C$ takes a value in ${cal C}_{uk}, 0 leq k leq ||c_u||-1$, the answers are $k$ times "Yes" and 1 time "No". For $C = c_u$ the $$ L_{cal C}(P,u) = sum_{k=0}^{||c_u||-1}P(C in {cal C}_{uk})(k+1) + ||c_u||P_u. $$ For code ${cal C}$,~ $L_{cal C}(P) = max L_{cal C}(P,u)$, $1 geq u geq N$, is the expected number of checkings in the worst case and $L(P) = min L_{cal C}(P)$ is this number for the best code ${cal C}$. Let $P = P^N = {frac{1}{N}, dots, frac{1}{N}}$. We construct a prefix code ${cal C}$ in the following way. In each node (starting at the root) we split the number of remaining codewords in proportion as close as possible to $(frac{1}{2},frac{1}{2})$. It is known that $$ lim_{N ightarrow infty} L_{cal C}(P^N) = 2 $$ (Ahlswede, Balkenhol, Kleinewachter, 2003) We know that $L(P) leq 3$ for all $P$ (Ahlswede, Balkenhol, Kleinewachter, 2003). Also, the problem to estimate an universal constant $A = sup L(P)$ for general $P = (P_1,dots, P_N)$ was stated (Ahlswede, 2004). We compute this constant for uniform distribution and this code ${cal C}$. $$ sup_N L_{cal C}(P^N) = 2+frac{log_2(N-1)-2}{N} $$ Also, we consider the average number of checkings, if code ${cal C}$ is used: $ L_{cal C}(P,P) = sum P_u L_{cal C}(P,u)$, for ${u in {cal U}}$. We calculate the exact values of $L_{cal C}(P^N)$ and $L_{cal C}(P^N,P^N)$ for some $N$. Other problem is the extension of identification for sources to liar models. We obtain a upper bound for the expected number of checkings $L_{cal C}(P^N;e)$, where $e$ is the maximum number of lies. $$ L_{cal C}(P^N;e) leq M_{cal C}(P^N;e) = (e+1)L_{cal C}(P^N) + e; ~~ lim_{N ightarrow infty} M_{cal C}(P^N;e) = 3e+2 $$