1
$\begingroup$

Let two functions $f,g :[n]\to \{0,1\},$ then we define $$\delta{(f,g)}=\frac{|\{i\in[n]:f(i)\neq g(i) \}|}{n}$$ is called normalized hamming distance.

My teacher said me this $\delta{(f,g)}$ is equivalent to

  1. $$\mathcal{P}\{f(i)\neq g(i)\},$$ where $i$ chosen uniformly at random.

  2. $$\mathop{\mathbb{E}}\{1_{f(i)\neq g(i)}\},$$ the indicator function.

Anybody give me any example by which I can see above three derives the same value.

For example, $f=1011, g=0101$, I clearly see $\delta(f,g)=\frac{3}{4},$ how can I derive probability and expectations from above also $\frac{3}{4}?$

$\endgroup$

1 Answer 1

1
$\begingroup$
  1. Let $i$ be a random variable taking uniformly from a discrete set $\{1,2,\ldots, n\}$, that is $\mathbb{P}(i = k) = \dfrac{1}{n} \ \forall k \in \{1,2,\ldots, n\}$. Then, $$ \begin{align*} \mathbb{P}(f(i) \neq g(i)) &= \sum_{k = 1}^n \mathbb{P}(f(i) \neq g(i), i = k)\\ &= \sum_{k = 1}^n \mathbb{P}(i = k, f(k) \neq g(k))\\ &= \sum_{k = 1}^n \dfrac{1\{f(k) \neq g(k)\}}{n} \end{align*} $$ The last sum is as same as $\delta(f, g)$ in your post.

  2. For $X$ is any discrete random variable taking values in a finite set $I$, and $f$ is any function, recall this formula: $$ \mathbb{E}[f(X)] = \sum_{k \in I} f(k)\mathbb{P}(X = k) $$ Now, apply this formula to the function $1\{f(X) \neq g(X)\}$, we have $$ \mathbb{E}[1_{f(i) \neq g(i)}] = \sum_{k = 1}^n 1_{f(k) \neq g(k)}\dfrac{1}{n} \equiv \delta(f, g) $$

$\endgroup$
5
  • $\begingroup$ $$ \mathbb{E}[f(X)] = \sum_{k \in I} f(k)\mathbb{P}(X = k) $$, would you elaborate this formula, what is $f(k)$ etc. $\endgroup$
    – user1290851
    Commented May 24 at 2:54
  • $\begingroup$ @David $f(k)$ is the value of $f$ at $k$, $k$ is one of many values that the random variable $X$ can take $\endgroup$ Commented May 24 at 3:00
  • $\begingroup$ In my question, that f(k) and your f(k) both are same? $\endgroup$
    – user1290851
    Commented May 24 at 3:01
  • $\begingroup$ @David No, I mention it as a general formula for any function $f$. In my answer, I then replace $f(X)$ to $1\{f(X) \neq g(X)\}$ $\endgroup$ Commented May 24 at 3:04
  • 1
    $\begingroup$ So please edit the answer, accordingly, it is creating confusion. $\endgroup$
    – user1290851
    Commented May 24 at 3:05

You must log in to answer this question.