General approach to randomized algorithm for equality problem
Suppose that the inputs are $x,y \in \{0,1\}^n$.

Consider the following protocol:


The parties decide on a random string $z \in \{1,2\}^n$.
Alice sends Bob $\alpha = \sum_{i=1}^n x_i z_i \pmod{3}$, and Bob sends Alice $\beta = \sum_{i=1}^n y_i z_i \pmod{3}$.
The parties compute $\gamma = \alpha - \beta \pmod{3}$.


Suppose that the Hamming distance between $x$ and $y$ is $d$. Then $\gamma$ is the sum of $d$ random values in $\{1,2\}$. Using linear algebra, we can calculate
$$ \Pr[\gamma = 0] = \frac{1}{3} + \frac{2}{3} \left(-\frac{1}{2}\right)^d.$$
(You can also prove this formula by induction.)

In particular, when $d=0$ the probability is $1$, when $d=1$ the probability is $0$, and otherwise the probability is in the range $[1/4,1/2]$ (corresponding to $n=3$ and $n=2$, respectively).

The suggests a protocol of the following form:


The parties decide on $N$ random strings $z_1,\ldots,z_N \in \{1,2\}^n$.
Alice sends Bob $\alpha_j = \sum_{i=1}^n x_i z_{j,i} \pmod{3}$ and Bob sends Alice $\beta_j = \sum_{i=1}^n y_i z_{j,i} \pmod{3}$, for $1 \leq j \leq N$.
The parties compute $\gamma_j = \alpha_j - \beta_j \pmod{3}$ for $1 \leq j \leq N$.
If all $\gamma_j$ are zero or all are non-zero, output "Hamming distance is probably at most 1", otherwise output "Hamming distance is definitely more than 1".


As in the case of equality, this protocol has only one-sided error: whenever the algorithm outputs "Hamming distance is more than 1", it is always correct. It remains to determine the connection between $N$ and the error probability $\epsilon$. Let $p = \Pr[\gamma = 0]$. If $p \neq 0,1$, the probability that the algorithm outputs the incorrect answer is
$$
p^N + (1-p)^N \leq (1/2)^N + (3/4)^N.
$$
This shows that $\epsilon$ is exponentially small in $N$, and so in order to guarantee an error probability of $\epsilon &gt; 0$, it suffices to take $N = O(\log(1/\epsilon))$.