probability of finding a random polynomial P(x) such that P(a)=b My question is related to this question. 
All operations and polynomials are defined over a finite field of prime order: $\mathbb{F}_p$, where $p$ is a large prime number. 

There are two parties involved in this question: A and B. Party A picks two arbitrary non-zero elements of the field: $(\alpha, \beta)$. Party B picks a uniformly random polynomial $P(x)$ of degree $d$. 
Question: What is the probability that $P(\alpha)=\beta$?
would it be correct to say that the probability is at most $\frac{1}{p}$?
 A: I assume a uniformly random polynomial of degree $d$ has every coefficient uniformly chosen from $\{0, 1, \dots, p-1\}$, except the highest degree coefficient is chosen from $\{1, 2, \dots, p-1\}$, i.e. it cannot be $0$.
Write $P(x) = Q(x) + c$ where $c$ is the constant term randomly chosen, i.e. $Q(x)$ has no constant term.  Then $P(\alpha) = \beta$ iff $c = \beta - Q(\alpha)$.  Therefore:
$$Prob(P(\alpha) = \beta) = Prob(c = \beta - Q(\alpha)) = 1/p$$
because for any choice of $\alpha, \beta$ and coefficients of $Q$, there is exactly $1/p$ chance that a uniformly-chosen $c$ will be just the value you need.
A: Let $p$ be a large prime and let $P\in F_p[x]$ be a random polynomial. Then its values $(P(i))_{i\in[[0,p-1]]}$ are independent and uniformly random in $[[0,p-1]]$. Here, we assume that $\alpha,\beta$ may be $0$.
Then, if we fix random $\beta$ and $P$, then the number $k$ of solutions of $P(x)=\beta$ is, in general, in $[[0,4]]$ (according to the normal law which is an approximation of the Bernouilli law). Thus $prob(P(\alpha)=\beta)\approx k/p$.
Now, if our random $P$ varies, then the mean of the number of solutions of $P(x)=\beta$ is $\approx 1$; finally, the required probability that $P(\alpha)=\beta$ is $\approx 1/p$.
EDIT. antkam is right. If we fix the degree $d$ of the polynomials, then, for every $\beta$, the mean of the number of solutions of $P(x)=\beta$ is exactly $1$. Thus the required probability is exactly $1/p$. 
