What is the difference between deterministic and stochastic model? Simple Linear Model:
$x=\alpha t + \epsilon_t$ where $\epsilon_t$  ~iid $N(0,\sigma^2)$
with $E(x) = \alpha t$ and $Var(x)=\sigma^2$
AR(1):
$X_t =\alpha X_{t-1} + \epsilon_t$ where $\epsilon_t$  ~iid $N(0,\sigma^2)$
with $E(x) = \alpha t$ and $Var(x)=t\sigma^2$
So a simple linear model is regarded as a deterministic model while a AR(1) model is regarded as stocahstic model.
According to a Youtube Video by Ben Lambert - Deterministic vs Stochastic, the reason of AR(1) to be called as stochastic model is because the variance of it increases with time. So is the feature of non-constant variance to be the criteria to determine the stochastic or deterministic?
I also don't think simple linear model is totally deterministic as we have a $\epsilon_t$ term associated with the model. Hence, we always have a randomness in $x$. So to what degree can we say a model is deterministic or stochastic?
 A: Some informal definitions


*

*A deterministic time series $\{y_t\}$ can be written as a function only of time. There is NO randomness. Some examples:


*

*$y(t) = 2t$

*$y(t) = e^t$


*A stochastic process $\{Y_t\}$ is a series of random variables. Recall that a random variable is a function from a sample space $\Omega$ to an outcome. A stochastic process $Y(t,\omega)$ is a function of both time $t$ and an outcome $\omega$ from sample space $\Omega$. Examples:


*

*$y_t = \epsilon_t$ where $\epsilon_t \sim \mathcal{N}(0, 1)$ (i.e. follows standard normal distribution)

*$y_t = .7 y_{t-1} + \epsilon_t$ 


You can also think of a stochastic process as a deterministic path for every outcome $\omega$ in the sample space $\Omega$. Randomly draw an $\omega \in \Omega$ and you get a path $Y_t(\omega)$.
Some comments...

... reason of AR(1) to be called as stochastic model is because the variance of it increases with time.

That's not the reason! The reason an AR(1) defines a stochastic process is because the process is random. Different values are possible at a time $t$, hence the process is stochastic.

I also don't think simple linear model is totally deterministic as we have a $\epsilon_t$ term associated with the model. 

The $x_t$ you have written up there is not deterministic. If you had a time series process $x_t = \alpha t + \epsilon_t$ where $\{\epsilon_t\}$ is a white noise process, then the time series $\{x_t\}$ would not be deterministic. It is stochastic because there is randomness!
The time series $y_t = \alpha t$ would be deterministic. You can decompose $\{x_t\}$ into two components: a deterministic component $\alpha t$ and a stochastic component $\epsilon_t$.
This leads to Wold's Theorem that any covariance stationary process can be uniquely decomposed into a deterministic component and a stochastic component.
A: The video is talking about deterministic vs. stochastic trends, not models. The highlight is very important. Both your models are stochastic, however, in the model 1 the trend is deterministic.
The model 2 doesn't have a trend. Your question text is incorrect.
The model 2 in your question is AR(1) without a constant, while in the video the model is a random walk (Brownian motion):
$$x_t=\alpha+x_{t-1}+e_t$$
This model indeed has a stochastic trend. It's stochastic because it's $\alpha t$ only in average. Each realization of a Brownian motion will deviate from $\alpha t$ because of the random term $e_t$, which is easy to see by differencing:
$$\Delta x_t=x_t-x_{t-1}=\alpha+e_t$$
$$x_t=x_0+\sum_{t=1}^t\Delta x_t=x_0+\alpha t +\sum_{t=1}^t e_t$$
A: As Aksakal mentioned in his answer, the video Ken T linked describes properties of trends, not of models directly, presumably as part of teaching about the related topic of trend- and difference-stationarity in econometrics.  Since in your question, you asked about models, here it is in the context of models:
A model or process is stochastic if it has randomness.  For example, if given the same inputs (independent variables, weights/parameters, hyperparameters, etc.), the model might produce  different outputs.  In deterministic models, the output is fully specified by the inputs to the model (independent variables, weights/parameters, hyperparameters, etc.), such that given the same inputs to the model, the outputs are identical.  The origin of the term "stochastic" comes from stochastic processes.  As a general rule of thumb, if a model has a random variable, it is stochastic.   Stochastic models can even be simple independent random variables.
Let's unpack some more terminology that will help you understand the literature around statistical models (deterministic, stochastic, or otherwise...):
Stochastic models do not need to be time-dependent or even Markov processes (dependent on past states, for example $AR(1)$ is first-order Markov since it depends on the state at $t-1$).  The linear model you posed above is stochastic (has a random variable) but not Markov (does not depend on past states).  In the linear model posed in the question, the error term is a random variable that we assume is uncorrelated (some people go further to state that error is i.i.d.), symmetrically distributed about the mean (some people go further to state that error is normally distributed), and mean zero ($\mu_{\epsilon_t}=0$), etc.  We make these assumptions in order to make the linear model useful to estimate the dependent variable(s) by minimizing some norm of that error term.  These assumptions allow us to derive useful properties of estimators and prove that certain estimators are the best under those assumptions; for example, that the OLS estimator is BLUE.  
A simpler example of a stochastic model is flipping a fair coin (heads or tails), which can be modeled stochastically as an i.i.d. uniformly distributed binary random variable, or a Bernoulli process.   You can also consider the coin flip as a physical system and come up with a deterministic model (in an idealized setting) if you take into account the shape of the coin, angle and force of impact, distance to the surface, etc.  If the latter (physical) model  of the coin flip has no random variables in it (e.g. it doesn't consider measurement error of any of the inputs to the model), then it is deterministic.
In teaching statistics, there is a common point of confusion between stochasticity and heteroscedasticity.  For example, Ken T has confused stochasticity for heteroscedasticity (or variability in variance).  A random (stochastic) variable, such as the output variable $X_t$ of an $AR(1)$ process or $\epsilon_t$ in a linear model $y_t = ax_t+\epsilon_t$, is heteroscedastic iff its variance changes over some input, such as time ($t$) in this case, such that different groups within the population have different variances.  In the video that Ken T linked (by Ben Lambert), if you pause it at 4:00 (4 minutes), you can see that $Var[X_t]$ in the model on the right side changes with $t$ (heteroscedastic) while $Var[X_t]$ in the linear model is constant (homoscedastic).
Furthermore, there is sometimes confusion between stationary stochastic processes and non-stationary stochastic processes.  Stationarity implies that statistics such as mean or variance do not change over time in the model.  Both are still considered stochastic models/processes as long as there is randomness involved.  As fellow Maroon, Matthew Gunn, mentions in his answer, Wold's decomposition states that any stationary stochastic process can be written as the sum of a deterministic and a stochastic process.
