Let's split the $n$-digit numbers without consecutive identical digits that end in a given digit, with leading zeros allowed, into $a_n$ numbers with identical first and last digits and $b_n$ numbers with different first and last digits. Then we have the recurrences $a_{n+1}=b_n$ and $b_{n+1}=9a_n+8b_n$. Eliminating $b_n$ yields $a_{n+2}=9a_n+8a_{n+1}$. With $a_1=1$ and $a_2=0$, this yields $a_3=9$, $a_4=72$, $a_5=657$, $a_6=5904$ and thus also $b_5=5904$. We want the $a_5$ admissible numbers ending in $5$, and the $8/9$ of the $b_5$ admissible numbers ending in $5$ that don't begin with $0$, and the $b_5$ admissible numbers ending in $0$. So that's
$$
a_5+\frac89b_5+b_5=657+\frac{17}9\cdot5904=11809\;.
$$
This we have to divide by the total number $9\cdot10^4$ of $5$-digit numbers without leading zeros to arrive at your computed probability.
Your computation of "with replacement" has a bit of a problem, in that you're assuming that there are $10^4$ possibilities -- but $1000$ of those are not actually possibilities, because you're explicitly specifying that the first digit cannot be $0$.
A shorter computation: "With replacement" the possible numbers are $1000$ through $9999$, and all of these $9000$ numbers are equally probable. Every fourth of them is divisible by $4$ -- no need to consider digits here, just notice that the interval from $1000$ to $9999$ contains a whole number of four-periods.
So the probability in this case should be $\dfrac14$.
Without replacement, imagine choosing the two last digits first, which can be done in $90$ ways. How you choose the two remaining digits is then immaterial.
How many endings from 00
to 99
are divisible by 4
and don't repeat digits? All the 25 you know, except for 00
, 44
, and 88
.
Actually, that may not work. We run into the problem that it is not even well-defined what it means to choose the four digits "without replacement" when the leftmost of them cannot be $0$.
We can see this clearer if we imagine choosing two digits "without replacement", where the left one must not be $0$.
If we choose the left digit first (and that is not $0$), there will be nine digit to choose from for the right digit, and $0$ is always among them -- so the probability of the right digit being $0$ is $\frac19$. On the other hand, if the choose the right digit first, all ten digits will be available at that time, so now the probability of the right digit being $0$ is only $\frac1{10}$.
You need to specify which order the digits are picked in, if you want "without replacement" at the same time as "leftmost digit must be nonzero". Otherwise it is ambiguous what the probability of picking each particular number is.
Of course you can also specify that you're choosing uniformly in a single step between all sequences of 4 diferent digits that do not start with $0$. But it seems to be hard to argue that "without replacment" is an accurate description of that procedure.
Best Answer
$$\color{red}{416/3125}=0.13312. $$ The last digit must be $2$ or $4$, this happens with probability $2/5$. The sum of the four other digits must be $\pm1\pmod{3}$, according to the last digit being $2$ or $4$. Since both events have the same probability, the answer is $2/5$ times the probability that the sum $s$ of four digits is $1\pmod{3}$, that is, $s=-2$ or $s=+1$ or $s=+4$.
$s=+4$ corresponds to $+1,+1,+1,+1$, with probability $2^4/5^4$.
$s=+1$ corresponds to $0,0,0,+1$, or $0,+1,+1,-1$ in whatever order. In the first case, one must place the $+1$, thus $4$ cases, with probability $2/5^4$ each. In the second case, one must place the $0$ and the $-1$, thus $12$ cases, with probability $2^3/5^4$ each.
$s=-2$ corresponds to $+1,-1,-1,-1$, thus $4$ cases, with probability $2^4/5^4$ each, or to $0,0,-1,-1$, thus $6$ cases, with probability $2^2/5^4$ each.
Summing up, the answer is $(2/5)\cdot(2^4+4\cdot2+12\cdot2^3+4\cdot2^4+6\cdot2^2)/5^4$.