What is the approach to understand this algorithm?

Question

Given $\{x_1, x_2,\ldots x_n\}$ where $x_i \in \{0, 1\}$ there is a binary equation $\varphi$ that is $x_{t_1}+x_{t_2}+\cdots+ x_{t_m}=0 \mod 2$ where $t_i \in \{1,2,\ldots,n\}$ for $x≥1$, $i=1,2,\ldots,m$, there is a probabilistic algorithm $J$ that is assigning $0$ or $1$ to $x_i$'s with the probability of $p(x_i=0)=p(x_i=1)=1/2$. As a conclusion the probability of this $J$ doesn't find a solution to $\varphi$ should be $1/2$. Since every $x_i$ is independent and $p(x_i)=1/2$ in the end shouldn't it be like for example $(1/2)^m$?

Answer 1

No matter what values all except the last variable are assigned, there is exactly one value the last variable can be assigned to satisfy the equation. Since all choices are independent, the probability of satisfying the equation is the same as the last variable taking the correct value, which happens with probability $\frac{1}{2}$.