# Probability of modifying $\alpha$ and $\beta$ in $\beta = a \alpha + b$ such that the equality still holds

Let $a ,$ $b ,$ $\alpha ,$ and $\beta$ be non-zero binary strings of length exactly $n$ where $$\beta = a \alpha + b.$$

Now, consider the following scenario. Fix $a$ and $b.$ I give you $\alpha$ and $\beta,$ but keep $a$ and $b$ as secrets from you. What is the probability that you can modify both strings (same length, just alter some bits), such that the altered strings $\alpha'$ and $\beta'$ still satisfy $$\beta' = a \alpha' + b.$$ A cryptography paper which I am reading mentions it is $2^{-n}$ but I couldn't convince myself why.

-
How many strings of length $n$ are there? How many pairs of strings of length $n$ are there? And from these, how many could satisfy a linear relationship? – Raskolnikov Mar 3 '11 at 20:23
'the probability that you can modify both strings'... Your question is not well formulated, pls revise it. – leonbloy Mar 3 '11 at 20:24
@leonbloy Sorry I'm an ESL speaker. I will revise it. – user2468 Mar 3 '11 at 21:18
@Raskolnikov There are $2^n$ different $\alpha$s and same number of $\beta$s. So, there are $2^{2n}$ different pairs $(\alpha',\beta')$. Now, I need to count how many of those $2^{2n}$ pairs satisfy the linear relation $\beta' = a \alpha' + b$. And the probability of choosing an element randomly from the $2^{2n}$ such that it satisfies the linear relation. Right? – user2468 Mar 3 '11 at 21:25
@M.S.: You got it! – Raskolnikov Mar 3 '11 at 21:26

## 1 Answer

Answer was figured out in the comments by discussion with @Raskolnikov.

(Edit: It's better if a moderator can close the question.)

-