Normalized hamming distance in probability

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}?$$

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)$$

• $$\mathbb{E}[f(X)] = \sum_{k \in I} f(k)\mathbb{P}(X = k)$$, would you elaborate this formula, what is $f(k)$ etc.
– user1290851
Commented May 24 at 2:54
• @David $f(k)$ is the value of $f$ at $k$, $k$ is one of many values that the random variable $X$ can take Commented May 24 at 3:00
• In my question, that f(k) and your f(k) both are same?
– user1290851
Commented May 24 at 3:01
• @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)\}$ Commented May 24 at 3:04