Tag Info

Hot answers tagged

9

The probability of any chair being occupied can be calculated exactly and, for the third chair as asked for in the question, it comes to $513/1943=0.26402\ldots$. More generally, let $\lambda$ be the rate at which customers arrive multiplied by the time taken for a haircut. So, here, we have $\lambda=(10{\rm mins})^{-1}(15{\rm mins})=3/2$. Then, after a long ...


7

The difference between Markov chains and Markov processes is in the index set, chains have a discrete time, processes have (usually) continous. Random variables are much like Guinea pigs, neither a pig, nor from Guinea. Random variables are functions (which are deterministic by definition). They are defined on probability space which most often denotes all ...


6

For a Markov process $(X_t)_{t \geq 0}$ we define the generator $A$ by $$Af(x) := \lim_{t \downarrow 0} \frac{\mathbb{E}^x(f(X_t))-f(x)}{t} = \lim_{t \downarrow 0} \frac{P_tf(x)-f(x)}{t}$$ whenever the limit exists in $(C_{\infty},\|\cdot\|_{\infty})$. Here $P_tf(x) := \mathbb{E}^xf(X_t)$ denotes the semigroup of $(X_t)_{t \geq 0}$. By Taylor's formula ...


5

Queueing theory uses Kendall's notation, as you described. There are three components describing the behavior of a queue: The customers arriving for service, which is usually described by a Poisson process (random arrivals), but sometimes by non-Poisson processes or even deterministic arrivals rates The time required to service each customer, which is ...


5

This is not a solution, but it might be helpful, and it is too long for a comment. Your $N^N$ equations can be simplified, because you can exploit symmetry in the structure of the problem. Say that $L(S)$ is the expected number of rounds for the game to end after reaching state $S$, where $S$ is some string of length $N$. Then: $$ \begin{eqnarray} ...


4

I can improve a little on MJD's method. This was based on computing for each state $S$ (the last $N$ values) the expected remaining number of steps $L(S)$ until a final state (last $N$ values equal) is reached. Let me change the notation slightly. Let $T_S$ be the number of steps from state $S$ until a final state is reached, and assume that this final ...


4

Suppose that for $t\geq s$, we have some function $g$ so that $$E[f(X_{t}) \,\vert\, \mathcal{F}_{s}]=g(X_{s}) \quad \mbox{a.s.}\tag1$$ Conditioning on $X_s$ in (1) gives $$E[f(X_{t}) \,\vert\, X_s]=g(X_{s}) \quad \mbox{a.s.}\tag2$$ From this we deduce $$E[f(X_{t}) \,\vert\, \mathcal{F}_{s}]=E[f(X_{t}) \,\vert\, X_s] \quad \mbox{a.s.}\tag3 $$ Equation (3) ...


4

This theorem is proved in most textbooks on Markov chains (yours would seem to be an exception). For example, you could see Durrett's Essentials of Stochastic Processes. The proof is not quite trivial but not excessively difficult either. It takes perhaps a page or two once the necessary background is in place. In the case of a finite-state Markov chain, ...


4

Let $f: [0,\infty) \to [0,\infty)$ and $s,t \in [0,\infty)$. Then $$\DeclareMathOperator{cov}{cov} \cov(B_{f(s)},B_{f(t)}) = \min \{f(s),f(t)\}$$ since $\cov(B_u,B_v)=\min\{u,v\}$ holds for all $u,v \in [0,\infty)$, so in particular for $u:=f(s)$, $v:=f(t)$. Concerning your second question: Theorem: Let $(X_t)_{t \geq 0}$ a continuous local ...


4

Your initial state is $X_0=0$. When tossing the two coins you can have the following results $\{HH, HT, TH, TT \}$ with probabilities $1/4$ each. Then in each step there are the possible transitions $$X_{n+1}=\begin{cases} X_n+1, & \text{with probability } \frac14 \{HT\} \\ X_n+0=X_n, & \text{with probability } \frac12 \{HH, TT\}\\ X_n-1, & ...


4

Poisson process is memoryless so after $n$ arrival, the probability of $A$ be the first arrival (or similarly for $B$) remains same for all $n$. Suppose that $X$ is the first arrival of the Poisson process with parameter $\lambda$ and $Y$ is the first arrival of the Poisson process with parameter $\mu$. From another question we know that $P(X>Y)=\frac ...


4

This has nothing to do with being a Lévy process or even with randomness. Assume that the function $f:t\mapsto f(t)$ has no positive jump. Let $t_y=\inf\{t\gt0\mid f(t)\gt y\}$. Assume that $t_y$ is finite and that $y\gt f(0)$. Then $f(t_y-h)\leqslant y$ for every $h\gt0$, by definition of $t_y$, hence $\limsup\limits_{s\to t,s\lt t}f(s)\leqslant y$. ...


4

Note that both $(Z\circ \theta_t)\, V$ and $ \mathbb{E}_{Y_t}[Z]\, V$ are product functions whose expectation can be found using your main equation. Define $$\phi(z)=\mathbb{E}_z(Z)=g_0(z)\int K_{s_1}(z,dy_1)g_1(y_1)\cdots\int K_{s_m-s_{m-1}}(y_{m-1},dy_m)g_m(y_m).$$ Then we calculate $$ \begin{eqnarray*} ...


3

Here is a computational approach using dynamic programming. Consider a function $V : \mathbb{N}^2 \to \mathbb{Q}$ such that $V(b, r)$ is the value of a game with $b$ black balls and $r$ red ones. What do we know about $V$? $V(0, r) = r$. $V(b, 0) = 0$, since if there are no red balls left we should walk away. For $b, r > 0$, we consider what will ...


3

We will use the result if $\lim_{n\to \infty} \frac{a_{n+1}}{a_n}=a $ and $|a|<1$, then $\lim_{n\to \infty}{a_n}=0$. Let $$ a_n = \binom {2n}{n} p^n(1-p)^n \implies \frac{a_{n+1}}{a_n}= {\frac { 2p(1-p)\left( 2\,n+1 \right) }{(n+1)}}. $$ Taking the limit of the last expression $$ \lim_{n\to \infty} \frac{a_{n+1}}{a_n}= 4 p(1-p).$$ Now, note ...


3

We can show that ${2n \choose n}p^n(1-p)^n \rightarrow 0$ as $n \rightarrow \infty$ by the ratio test. Let $a_n = {2n \choose n}p^n(1-p)^n$, then $$ \lim_{n \rightarrow \infty}\frac{a_{n+1}}{a_n} = \lim_{n \rightarrow \infty} p(1-p) \frac{(2n+2)(2n+1)} {(n+1)^2} = 4p(1-p) $$ Since $p$ is a probability, $4p(1-p) \leqslant 1$, if $p \neq \frac{1}{2}$, we're ...


3

The process $(r_c(t))$ based on $P(\xi(t,n)=1)=c^n$ jumps from $n$ to $n+1$ after a geometric time with mean $1/c^n$ hence $(r_c(t))$ hits $n$ after $\Theta(1/c^n)$ steps. Since $E(r_c(t))=\Theta(\log t)$ and $r_c(t)\geqslant r(t)$, $E(r(t))=O(\log t)$. On the other hand, $r(t)\to+\infty$ almost surely. Otherwise, $r(t)$ would stay at some level $n$ forever ...


3

From my own experience, I found chapter 7 in Pierre Brémaud's book "Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues" quite an illuminating introduction to Markov random fields.


3

A sufficient condition is that the process $X$ is measurable, that is, the map $(\omega,t)\to X(\omega,t)$ should be measurable on the product space $(\Omega\times I,{\cal F}\times {\cal I})$ to $(E,{\cal E})$. Then if $\tau:(\Omega,{\cal F})\to(I,{\cal I})$ is a (measurable) random time, the composition $$\begin{array}{ccccc} \omega &\to& ...


3

It has been a while since I've done anything with Markov chains, so I apologize for any poor notation in advance. Notice that $ \{X_n=x_n, X_k=x_k\} $ is $\sigma$-measurable from $ \{X_n=x_n, \ldots,\ X_1=x_1 \},$ for $k< n$. Really the Markov property for finite state spaces is equivalent to $ P(X_{n+1}=x_{n+1}\,|\, \sigma\{X_n,\, \ldots,\, X_1 \} ...


3

You might have a look at James Norris, Markov chains.


3

This uses two conventions at once: For every integer $t\geqslant0$, $P_t$ is the transition matrix of $t$ steps of the Markov chain with transition matrix $P$. Hence $P_0$ is the identity and $P_{t+1}=P_tP=PP_t$ for every $t\geqslant0$. For every transition matrix $P$ and every $B$ in $\Sigma$, $P(x,B)=\sum\limits_{y\in B}P(x,y)$. In the discrete ...


3

Since $X_s$ is $\mathcal F_s$-measurable, the tower property shows that $$ \mathrm{P}_x\left[\left.X_{t+s}\in A\space\right|X_s\right]=\mathrm E_x\left[Y\left.\space\right|X_s\right],\qquad \text{where}\quad Y=\mathrm{P}_x\left[\left.X_{t+s}\in A\space\right|\mathcal{F}_s\right]. $$ Item (3) of Definition 17.3 asserts that $Y$ is $\sigma(X_s)$-measurable, ...


3

The Markov chain property does not say that $X_0$ and $X_2$ are independent, only that the dependence of $X_2$ on $(X_0,X_1)$ is equivalent to the (a priori simpler) dependence of $X_2$ on $X_1$ only. Consider for example some i.i.d. standard normal random variables $Z_k$ and define $$ (X_0,X_1,X_2)=(Z_0,Z_0+Z_1,Z_0+Z_1+Z_2). $$ Then $(X_k)_{0\leqslant ...


3

No. Try $X_t=S_t-B_t$, where $S_t=\sup\limits_{0\leqslant s\leqslant t}B_s$. Another class of examples: $X_t=\displaystyle\int_0^tg(s)\,\mathrm dB_s$.


3

Copying my answer from MO... There is an improper marginalization in the equation that defines your overall strategy: $$P(X_2,\dots,X_n|X_1)=P(X_n|X_{n-1},\dots,X_1)\cdot P(X_{n-1}|X_{n-2},\dots,X_1)\cdot \dots \cdot P(X_2|X_1)?$$ For simplicity, take $n=3$: $$P(X_2,X_3|X_1)=P(X_3|X_2,X_1) \cdot P(X_2|X_1)?$$ Now remember that each $P$ above is really a ...


3

The transition kernel $K_t$ is defined by some measurability conditions and by the fact that, for every measurable Borel set $A$ and every (bounded) measurable function $u$, $$ \mathrm E(u(X_t):X_{t+1}\in A)=\mathrm E(u(X_t)K_t(X_t,A)). $$ Hence, each $K_t(\cdot,A)$ is defined only up to sets of measure zero for the distribution of $X_t$, in the following ...


3

We have to show that for each $n\geqslant 1$, if $x\in S$ is fixed, then the map $S\in\mathcal{S}\mapsto P^n(x,S)$ is a probability measure, and if $B\in\cal S$ is fixed, the map $x\in S\mapsto P^n(x,B)$ is measurable. We proceed by induction. We assume that $P^{n-1}$ is a transition kernel. If $x\in S$ is fixed, since for all $y$ we have ...


3

Just hit me! We don't actually know matrix multiplication works, that's what the Chapman-Kolmogorov equation actually tells us. So before it, we can write them as a matrix purely because it's a table, but we don't know multiplying makes sense, the equation proved without matrix multiplication that ends up being the definition of matrix multiplication is ...


3

We define a sequence of (discrete) stopping times $$\tau_j := \frac{\lfloor 2^j \tau \rfloor+1}{2^j}, \qquad j \in \mathbb{N}.$$ It is not difficult to see that $\tau_j$ is indeed a stopping time and $\tau_j \downarrow \tau$ as $j \to \infty$. Since the Brownian motion has continuous paths, this implies $B(\tau) = \lim_{j \to \infty} B(\tau_j)$. Let ...



Only top voted, non community-wiki answers of a minimum length are eligible