Markov Environment is not about deterministic or stochastic. "Depends only on the current state and your action" does not mean you know what will happen(deterministic).
We can have Markov + deterministic, Markov + Stochastic, Non-Markov + deterministic, and Non-Markov + stochastic.
The definition you have is not a definition of deterministic. It is a definition of Markov property.
Refer to Wikipedia.
A stochastic process has the Markov property if the conditional
probability distribution of future states of the process (conditional
on both past and present values) depends only upon the present state;
that is, given the present, the future does not depend on the past. A
process with this property is said to be Markovian or a Markov
process. The most famous Markov process is a Markov chain. Brownian
motion is another well-known Markov process.
Markov property is assumed mostly in stochastic problems.
Brownian motion is the motion of molecules of ink in the water and used to model the movement of a stock price, which is stochastic.
Deterministic means when you are in the same state and choose the same action your next state will be always the same.
Stochastic means even you are in the same state and choose the same action, you next state can be different than the previous time.
Example) You toss a coin and roll a die. Every time you roll a die you get pennies as many. If the coin gets head, you get a chance to roll a die twice next time.
Your state can be (money you collect so far, coin head/tail in the previous time).
In this problem, your next state will not be affected by the past. the only thing you need to know is the current state, the money you got and head or tail. It has a Markov process/environment. However, still, it is stochastic because you don't know what will be the next state.
