# Connection between probabilistic algorithm and distributional algorithm

A basic question about the connection between two notions. I am sure these are known notions in CS but I struggle with the basics:
First Definition:
A probabilistic algorithm $A(n)$ decides $L$ if for every $x \in L$, it holds that $\Pr(A(x) = 1) \geq 1 - \epsilon$, and for every $x \notin L, \Pr (A(x) = 0) \leq \delta$.
Second definition:
Given a language $L$ and a distribution $D$ on the instances of $L$, the algorithm $A$ decides $L$ with respect to $D$, if it holds that for every $x$ which is drawn from $D$, the above requirements hold ($\Pr(A(x) = 1)\geq ...$).
Clearly, the first notion is "stronger" in some sense: in the second definition, I may force the algorithm make as many mistakes as I want, by creating a different distribution on which he cannot handle.
My main question is the following:
If for a problem there exists an algorithm $A$ such that $A$ decides $L$ with respect to the uniform distribution, does it mean that $A$ decides $L$ for every input (with high probability)? I somewhat "feel" that uniform solving for a uniform distribution is harder, does this feeling correct?

As for your question, it is not true that an algorithm which outputs the correct answer with high probability when the input is drawn according to the uniform distribution, returns the correct answer with high probability for all inputs. Consider an algorithm which answers correctly for all inputs not of the form $0^n$. For an input drawn from the uniform distribution, the probability of getting a correct answer is $1-2^{-n}$, however for inputs of the form $0^n$ you never get the correct answer.
• $1-\frac{1}{2^n}$ Commented Jul 6, 2018 at 6:59