Definition. A uniquely decipherable code is a code $\varphi: A \rightarrow\{0,1\}^{*}$ such that every concatenation of codewords is unique.
A non-example of this definition is as follows: let the codewords be $w_1 = 01$, $w_2 = 001$, $w_3 = 010$, then the string $0101001$ could correspond to “$w_1w_3w_1$”, “$w_1w_1w_2$”, or “$w_1w_2w_1$”.
I’m trying to use the probabilistic method on this problem. Following an example that I’ve read, I’m assuming $\sum_{i=1}^n 2^{-l_i} > 1$ and trying to find a contradiction. My guess is that this quantity represents the expected value of a random variable (e.g. the number of codeword strings corresponding to a particular “0/1”-string), hence the contradiction.
Let $A = \{a_1, \ldots, a_n\}$ be our alphabet, and $\varphi(A) = \{w_1, \ldots , w_n\}$ be our codewords. Let $w = w_{i_1} \ldots w_{i_m}$ be a word of length $m$.
To realize the idea above, I’d need to find a sequence of events $E_i$’s over the $w_i$’s, let $X_i$’s be their indicator variables, sum them up and use the union bound on them. I have one or two ideas about what the events could be, but none seems to work so far.