User byron schmuland - MathOverflow

Answer by Byron Schmuland for Reference request: Martingale decompositions (positive/negative and u.i./singular)

2012-03-16T00:11:46Z

These are the Krickeberg and Riesz decompositions, respectively. A good reference is section 4 of Chapter V in Probabilities and Potential B by Claude Dellacherie and Paul-Andre Meyer.

Answer by Byron Schmuland for Gluing Markov processes

2012-02-24T01:34:47Z

In his book General Theory of Markov Processes, Michael Sharpe has a chapter on Transformations. One of the transformations described there is "concatenation of processes" which may be what you want.

Answer by Byron Schmuland for Markov Processes with Given Marginals

2012-02-09T03:24:58Z

If you are willing to drop continuity in the parameter $t$, then you could let $(X_t)$ be independent with distribution $\mu_t$.

Answer by Byron Schmuland for Symmetric Feller processes and Dirichlet Forms

2012-02-03T19:24:51Z

I've decided to post an incomplete preliminary answer.

I ran into your problem when I was writing [1]. On page 258 you will see my resolution.

I should point out that in my case, the underlying space $X$ was compact, and that $m$ was a finite measure with full support. Thus, $C(X)$ embeds into $L^2(X;m)$ with a continuous, linear injection in the obvious way. This may not hold in the locally compact case, and I'm not sure how serious a problem that is.

Translated into your notation, and letting $\tilde G$ be the Friedrichs extension we note that $\bar G$ and $\tilde G$ agree on $\cal D$ and so the resolvent operators $\bar R_\lambda$ and $\tilde R_\lambda$ agree on $(\lambda-G)({\cal D})$. We deduce that $\bar R_\lambda= \tilde R_\lambda$ on $C(X)$ and using the Yosida approximation conclude the same about the semigroup operators $\bar T_t$ and $\tilde T_t$.

I hope this is of some help. If anything is unclear, let me know.

[1] A result on the infinitely many neutral alleles diffusion model. Journal of Applied Probability 28, 253-267 (1991).

Answer by Byron Schmuland for Some questions concerning a random number process

2011-10-28T17:23:29Z

Using Markov chain theory, it is not hard to show that the expected time until the process hits state "1" starting at $N_0$ is $1+1+1/2+\cdots+1/(N_0-1)$.

Correction

In my previous answer, I mistakenly chose a new state uniformly from $[1,\dots, N_i]$ instead of $[1,\dots, N_{i-1}]$. The expected hitting time of state "1" for the OP's model starting at $N_0$ is $1+1/2+\cdots+1/(N_0-1)$. This is one less than my first answer.

Answer by Byron Schmuland for Probability-one event for Markov chain

2011-10-20T23:49:14Z

If I've understood your problem correctly, an argument along these lines may help:

Let ${\cal F}_n=\sigma(X_0,X_1,\dots,X_n)$ and define $S_n=\left(X_n\in S\right)$, so that $S_n\in {\cal F}_n$. We will use Levy's generalization of the Borel-Cantelli Lemma which states that $$\left( S_n\mbox{ i.o.} \right)=\left(\sum_n \mathbb{P}(S_{n+1} | {\cal F}_{n})=\infty\right).$$

Let's calculate the conditional probability. Letting $E(x)={ X_{n}=x_{n},X_{n-1}=x_{n-1},\dots,X_0=x_0}$ be a generic partition set, we get \begin{eqnarray*} \mathbb{P}(S_{n+1}\,|\,{\cal F}_n)&=&\sum_x\mathbb{P}(X_{n+1}\in S\,|\,E(x))1_{E(x)}\cr &=&\sum_x\mathbb{P}(X_{n+1}\in S\,|\,X_n=x_n)1_{E(x)}\cr &=&\sum_x P(x_n, S)1_{E(x)}\cr &=&P(X_n, S), \end{eqnarray*} where $P$ is the transition kernel for the Markov chain.

The definition of ``nice" set gives $P(X_n,S)\geq \varepsilon_K 1_K(X_{n}),$ and since $(X_n)$ visits $K$ infinitely often, we have $$\sum_n P(X_n,S)\geq \varepsilon_K \sum_n 1_K(X_{n})=\infty$$ almost surely.

Answer by Byron Schmuland for Markov Property: determined by just the law or also the realization?

2011-10-18T14:17:48Z

I've posted a solution on my webpage.

Answer by Byron Schmuland for Distribution of the biggest gap

2011-09-25T20:07:33Z

This is the answer to a slightly modified version of the problem. I hope that it would also lead to a solution of the original version.

As I point out in my answer to Math StackExchange question 66430 ("What is the distribution of gaps?"), if, in addition to the gaps $G_1=a_1$and $G_j:=a_j-a_{j-1}$ for $2\leq j\leq n$, you introduce final gap $G_{n+1}=(m+1)-a_n$, the random vector $(G_1,G_2,\dots, G_{n+1})$ gives a random composition of the number $m+1$. That is, all outcomes $(g_1,g_2,\dots, g_{n+1})$ with $$g_1+g_2+\cdots+g_{n+1}=m+1,\quad g_j\geq 1$$ are equally likely. There are $m\choose n$ such compositions, as found using stars and bars.

Then $Pr(a_{\max}\leq k)$ (where my maximum includes the final gap) is just the proportion of compositions using numbers from $1$ to $k$. By inclusion-exclusion and stars and bars, this probability is $$Pr(a_{\max}\leq k)={\sum_{x} (-1)^x {m-xk\choose n}{n+1\choose x}\over{m\choose n}}.$$

Answer by Byron Schmuland for Support of Probability Measures on Separable Metric Spaces

2011-04-23T15:34:25Z

A separable metric space is strongly Lindelof, that is, every open cover of an open subset has a countable subcover. The complement of the support is the union of all open balls with zero measure. By reducing to a countable subcover, we see that this set has measure zero. So the support has full measure.

Answer by Byron Schmuland for probability and math puzzle books/references

2011-04-23T13:57:59Z

Problems and Snapshots from the World of Probability by Gunnar Blom, Lars Holst, and Dennis Sandell is a book that I like very much. Their problems are pretty challenging and assume a working knowledge of basic probability.

Answer by Byron Schmuland for Number of required trials to sample all possible states of a 'd'-sided loaded die

2011-04-14T12:55:13Z

You may also find the answers of this Math SE question helpful.

The average number of unique observations $E(M)$ is given in Henry's answer here, at least in the case of a fair die.

Answer by Byron Schmuland for Probability estimates for "beans & boxes"

2011-03-27T15:33:19Z

Your problem falls under the general category of "coupon collector's problems". There is a large literature on such problems, mainly concerned with formulas for the mean and variance of the random variable $T$.

The exact distribution of the time $T$ to have at least one bean ($N=1$) in each box is known in terms of Stirling numbers of the second kind: see Henry's answer here, or below
$$P(\mbox{ every box has at least one bean after }T \mbox{ seconds}) = P^{-T}\ P\ !\ \left\lbrace {T\atop P} \right\rbrace.$$

In general, I think you should take Alekk's advice and use the Poisson approximation.

Answer by Byron Schmuland for What is the cover time of a random walk on a cube?

2011-03-23T02:02:21Z

An additional reference:

Chapter 12 in Problems and Snapshots from the World of Probability by Blom, Holst, and Sandell is devoted to an elementary exposition of such cover problems.

A related problem:

The solution to Problem 6556 in the American Mathematical Monthly (Vol. 96, No. 9, Nov. 1989, pages 847-849) looks at the average number of steps for a random walk to visit all the edges on the cube in dimensions $d=2$, $3$, and $4$.

For $d=2$ the answer is easily computed to be 10.

For $d=3$ a system with 387 equations in 387 unknowns is solved to give an answer of about 48.5.

For $d=4$ the problem is declared hopeless.

Is the infimum of the Ky Fan metric achieved?

2010-08-15T22:53:00Z

Consider the probability space $(\Omega, {\cal B}, \lambda)$ where $\Omega=(0,1)$, ${\cal B}$ is the Borel sets, and $\lambda$ is Lebesgue measure.

For random variables $W,Z$ on this space, we define the Ky Fan metric by

$$\alpha(W,Z) = \inf \lbrace \epsilon > 0: \lambda(|W-Z| \geq \epsilon) \leq \epsilon\rbrace.$$

Convergence in this metric coincides with convergence in probability.

Fix the random variable $X(\omega)=\omega$, so the law of $X$ is Lebesgue measure, that is, ${\cal L}(X)=\lambda$.

Question: For any probability measure $\mu$ on $\mathbb R$, does there exist a random variable $Y$ on $(\Omega, {\cal B}, \lambda)$ with law $\mu$ so that $\alpha(X,Y) = \inf \lbrace \alpha(X,Z) : {\cal L}(Z) = \mu\rbrace$ ?

Notes:

By Lemma 3.2 of Cortissoz, the infimum above is $d_P(\lambda,\mu)$: the Lévy-Prohorov distance between the two laws.
The infimum is achieved if we allowed to choose both random variables. That is, there exist $X_1$ and $Y_1$ on $(\Omega, {\cal B}, \lambda)$ with ${\cal L}(X_1) = \lambda$, ${\cal L}(Y_1) = \mu$, and $\alpha(X_1,Y_1) = d_P(\lambda,\mu)$. But in my problem, I want to fix the random variable $X$.
Why the result may be true: the space $L^0(\Omega, {\cal B}, \lambda)$ is huge. There are lots of random variables with law $\mu$. I can't think of any obstruction to finding such a random variable.
Why the result may be false: the space $L^0(\Omega, {\cal B}, \lambda)$ is huge. A compactness argument seems hopeless to me. I can't think of any construction for finding such a random variable.

Answer by Byron Schmuland for Examples of common false beliefs in mathematics.

2010-05-08T14:39:53Z

From the Markov property of the random walk $(X_n)$ we have

$$P(X_4>0 \ |\ X_3>0, X_2>0) = P(X_4>0\ |\ X_3>0).$$

To paraphrase Kai Lai Chung in his book "Green, Brown, and Probability",

"The Markov property means that the past has no after-effect on the future when the present is known; but beware, big mistakes have been made through misunderstanding the exact meaning of the words "when the present is known"."

Answer by Byron Schmuland for Differentiation of a series of increasing functions

2011-01-05T00:02:18Z

This is also Theorem 17.18 (page 267) of Real and Abstract Analysis by Hewitt and Ross. The result is credited there to Fubini.

Answer by Byron Schmuland for Reachability for Markov process

2010-12-23T13:41:34Z

It is right, and not so obvious.

The question of whether or not a Markov process hits particular sets is usually studied using the concept of capacity.

For a continuous time parameter Markov process taking values in a general topological state space, this leads to non-trivial problems of measurability. For instance, for a Borel $A$ there is no guarantee that the set $R(T,A)\in{\cal F}$ where $(\Omega,{\cal F},\Pr)$ is the probability space. However, under suitable conditions, capacity theory can be used to show that $R(T,A)$ is universally measurable, and hence that $\Pr[R(T,A)]$ makes sense.

Let's assume that the state space and process are "nice"; say, the state space is a locally compact, separable metric space, and the process has right continuous sample paths. For fixed $T<\infty$, the formula $\phi(A)=\Pr[R(T,A)]$ defines a Choquet capacity on the Borel sets $A$. Therefore, $$\phi(A)=\sup(\phi(K): K\subseteq A,\ K\mbox{ compact}).$$

For a compact $K$, define the stopping time $\tau(\omega):=\inf(t\geq 0: X_t(\omega)\in K)$. Since the sample paths of $(X_t)$ are right continuous and $K$ is closed, we have $R(T,K) = (X_{\tau\wedge T} \in K).$

Therefore, $$\Pr[R(T,K)]\leq \mathbb{E}[I_A(X_{\tau\wedge T})]\leq \Pr[R(T,A)].$$

Taking the supremum over compact subsets of $A$ gives $$ \Pr[R(T,A)]=\sup_{\tau}\ \mathbb{E}[I_A(X_{\tau\wedge T})],$$ which gives your desired result. Letting $T\to\infty$ gives the infinite version.

The result hinges on the fact that, as far as the process goes, the Borel set $A$ can be well approximated from the inside by compact sets.

You can find more details in Chapter I, Section 10 of Blumenthal and Getoor's Markov Processes and Potential Theory, or in Section 3.3 of Kai Lai Chung's Lectures from Markov Processes to Brownian Motion.

Is the space of continuous functions from a compact metric space into a Polish space Polish?

2010-11-14T03:50:59Z

Let $K$ be a compact metric space, and $(E,d_E)$ a complete separable metric space. Define $C:=C(K,E)$ to be the continuous functions from $K$ to $E$ equipped with the metric $d(f,g)=\sup_{k\in K}\ d_E (f(k),g(k))$. Is the space $C$ separable?

The result is true when $E$ is the real line; this is Corollary 11.2.5 in Dudley's book Real Analysis and Probability.

The result is also true when $K=[0,1]$ (if I'm not being too careless) by considering $C$ as a subspace of the Skorohod space $D_E[0,1]$, which is complete and separable by Theorem 5.6 in Ethier and Kurtz's book Markov Processes: Characterization and Convergence.

For general $K$, it is not so obvious how to find an explicit countable dense set in $C$, but I suspect one could modify Ethier and Kurtz's approach and get a proof.

But surely this result is known, and stated in some book? I've searched through my library without success.

Update: This result is also Theorem 2.4.3 of S. M. Srivastava's book A Course on Borel Sets. His proof is the same as Kechris's. I have also found an alternative, but false, published proof using the "fact" that $C(K,E)$ is $\sigma$-compact. Beware!

Answer by Byron Schmuland for Right-continuity of natural filtrations

2010-11-22T15:46:34Z

Right continuity fails even for canonical continuous processes.

The natural filtration on $C([0,\infty))$ is not right continuous. For example, the event $\{\omega: {d^+\over dt}\ \omega_t\mbox{ exists at }t=0\}$ belongs to ${\cal F}_{0+}$ but not ${\cal F}_0$. In words, you can tell whether the function $\omega_t$ has a right derivative at $t=0$ with an infinitesimal peek beyond time 0, but you cannot tell just from the value of the function $\omega_t$ at time 0.

Right continuous filtrations are nicer to work with, and since it fails for the natural filtration,
we often use the right continuous version instead. Fortunately, many of the nice properties of right continuous processes carry over even with this enlarged filtration. For example, Brownian motion is still Markov with respect to ${\cal F}_{t+}$ which leads to interesting results like Blumenthal's zero-one law.

Answer by Byron Schmuland for If $H$ is a separable Hilbert space, is $L^2(H)$ separable?

2010-11-15T01:25:19Z

By Example 7.14.13 in Volume 2 of Bogachev's Measure Theory, every Radon measure on $H$ is separable, so that $L^2(H,\gamma)$ is also separable. It is not necessary that $H$ is a Hilbert space, just that every compact subset of $H$ be metrizable.

Answer by Byron Schmuland for Is there an extension of the Arzela-Ascoli theorem to spaces of discontinuous functions?

2010-11-11T01:16:07Z

Billingsley's book Convergence of Probability Measures has a section on the geometry of the Skorohod space $D=D[0,1]$, and in Theorem 14.3 gives an analogue of the Arzela-Ascoli theorem. I am using the first edition of this book.

A set $A$ has compact closure in the Skorohod topology if and only if $$\sup_{x\in A}\ \sup_t |x(t)|<\infty\ \mbox{ and }\ \lim_{\delta\to 0}\ \sup_{x\in A}\ w^\prime_x(\delta)=0.$$

Here $$w^\prime_x(\delta)=\inf_{t_i}\ \max_{0 < i\leq r}\ \sup\{ |x(s)-x(t)|: s,t\in [ t_{i-1} , t_i) \} , $$ where the infimum extends over finite sets of points $\{ t_i\}$ such that $0=t_0 < t_1 < \cdots < t_r=1$ and $t_i-t_{i-1}>\delta\ $ for $1\leq i \leq r$.

Billingsley also gives a second characterization of compactness in Theorem 14.4 that he says is sometimes more convenient to work with.

I presume that this is the same as the solutions already given, but I thought another reference wouldn't hurt.

Here is another reference. In section 6 of chapter 3 of Ethier and Kurtz's Markov processes: Characterization and Convergence you will find similar criteria for relative compactness of subsets of $D_E[0,\infty)$, that is, $E$-valued Skorohod space, where $E$ is a metric space.

Answer by Byron Schmuland for Most memorable titles

2010-10-31T16:34:17Z

Zaphod Beeblebrox's Brain and the Fifty-ninth Row of Pascal's Triangle

Answer by Byron Schmuland for Expectation of first positive value in random walk

2010-10-27T15:13:42Z

You are looking for the "mean ladder height" of a random walk. There is a (not very tractable) formula due to Spitzer that gives the answer:

$$ E(S_N)={\sigma\over\sqrt{2}} \exp\left(\sum_{n=1}^\infty {1\over n}(P(S_n<0)-1/2)\right)$$

Here $\sigma^2$ is the variance of the jump distribution. Maybe it would be possible to work this out in your special case.

[1] Chow, Yuan S. On Spitzer's formula for the moment of ladder variables. Statist. Sinica 7 no. 1, 1997, 149–156.

[2] Spitzer, Frank A Tauberian theorem and its probability interpretation. Trans. Amer. Math. Soc. 94, 1960, 150–169.

Answer by Byron Schmuland for Continuity of cylindrical functions.

2010-10-27T20:37:46Z

For each $j$, the inequality $$|\langle x , e_j\rangle| = j \sqrt{\langle x , e_j\rangle\langle e_j , x\rangle\over j^2}\leq j\sqrt{\langle x , x\rangle_\omega}$$ shows that the map $x\mapsto \langle x , e_j\rangle$ is continuous from $(X , \langle\cdot ,\cdot\rangle_\omega)$ to $\mathbb R$. Thus, for fixed $d$ the map $x\mapsto (\langle x , e_1\rangle, \dots,\langle x , e_d\rangle)$ is continuous from $(X , \langle\cdot ,\cdot\rangle_\omega) $ into ${\mathbb R}^d$. Composing with the smooth map $\phi:{\mathbb R}^d\to {\mathbb R}$ gives you a continuous function from $(X , \langle\cdot ,\cdot\rangle_\omega)$ into $\mathbb R$ again.

Answer by Byron Schmuland for A Markov process which is not a strong markov process?

2010-10-27T17:17:16Z

A standard example is Exercise 6.17 in Sharpe's book The general theory of Markov processes. The process stays at zero for an exponential amount of time, then moves to the right at a uniform speed.

Answer by Byron Schmuland for When is $L^2(X)$ separable?

2010-10-15T17:51:01Z

In addition to the measure $\mu$ being $\sigma$-finite, I think you also need some conditions on the measurable space $(X,{\cal A})$.

Proposition 3.4.5 of Cohn's book Measure Theory says that $L^p(X,{\cal A},\mu)$ ($1\leq p < \infty$) is separable if $\mu$ is $\sigma$-finite and $\cal A$ is countably generated. For example, it holds if $X$ is a complete separable metric space, and $\cal A$ is the Borel $\sigma$-algebra.

However, even for a compact group, you can make counterexamples like $[-1/2,1/2]^{[0,1]}$, an uncountable product of a circles. For the product measure, $\mu=\lambda^{[0,1]}$, the coordinate functions are orthogonal in $L^2$ but there are uncountably many.

I haven't checked the details, so take my answer with a grain of salt!

Answer by Byron Schmuland for Wiener process related counterexample

2010-09-25T06:08:15Z

This is not hard to find such an example. Let $P$ be Wiener measure on the space $\Omega = C([0,\infty))$ of continuous functions $t\mapsto \omega(t)$. Then the process $\omega(t)$ satisfies all three conditions of a Brownian motion.

Now let's define a new process $W(t)$ that is "almost" equal to $\omega(t)$, but where we deliberately wreck the sample path continuity.

Take any random time $T:\Omega\to [0,\infty)$ that has a continuous distribution on $(\Omega, P)$, and let $W(t,\omega)=\omega(t)$ when $t\not=T(\omega)$, but $W(t,\omega)=\omega(t)+1$ otherwise. The process $W(t)$ still satisfies 1 and 3 but the sample path continuity fails at exactly at the time point $T(\omega)$ for each $\omega$.

There are many such random times $T$, for example you could use $T(\omega):=\inf [t>0: \omega(t)=1 ]$, i.e. the hitting time of 1.

Answer by Byron Schmuland for Product of Borel sigma algebras

2010-09-24T18:38:34Z

The answer to question 3 is yes. At least according to Lemma 6.4.2 of the second volume of Bogachev's book "Measure Theory".

He requires both spaces to be Hausdorff and one of them to have a countable base. They need not be metric spaces.

Answer by Byron Schmuland for On measurable functions of two variables

2010-09-20T18:50:45Z

Yes, by continuity in the $t$ variable $f(t,x)=\lim_n f(\lfloor n t\rfloor/n,x)$, which expresses $f$ as the pointwise limit of a sequence of measurable functions.
Yes, by continuity in the $t$ variable we have $\min_{t\in[0,1]} f(t,x)=\min_{t\in[0,1]\cap {\mathbb Q}} f(t,x)$, where $\mathbb Q$ means the rational numbers.

Answer by Byron Schmuland for estimate the error term in CLT

2010-09-20T01:07:20Z

If $X_m$ has cumulative distribution function $F_m$, and $X$ has cumulative distribution function $F$, then (at least formally) integration by parts gives you $$E(f(X_m))-E(f(X))=\int (F_m(x)-F(x)) df(x).$$ Now you can apply the Berry-Esseen bound.

Comment by Byron Schmuland

2012-02-08T17:38:28Z

@Hans In that case, doesn't the Friedrichs extension of $(G,{\cal D})$ equal the $L^2$ generator of the process by definition?

Comment by Byron Schmuland

2012-02-07T21:51:55Z

@Hans I'm still thinking about your problem from time to time, when I have moment to spare. I believe that a complete resolution of your problem can only come after we have clearly defined "the $L^2$ semigroup induced by $X$". Do you have a specific definition in mind?

Comment by Byron Schmuland

2012-02-02T16:12:11Z

I'm thinking about your problem, and hope to post an answer soon. In the meantime, I think you want to drop the condition $G({\cal D})\subset C_K$. This eliminates too many nice processes, and is not needed to make $\int Gf\, g\, dm$ finite. – Byron Schmuland

Comment by Byron Schmuland

2011-12-31T19:11:19Z

The motivation: math.stackexchange.com/questions/94948/…

Comment by Byron Schmuland

2011-11-22T13:12:06Z

Crossposted: math.stackexchange.com/questions/84552/…

Comment by Byron Schmuland

2011-11-20T19:50:02Z

Crossposted: math.stackexchange.com/questions/83931/…

Comment by Byron Schmuland

2011-10-24T18:59:54Z

Standard dice have $m=6$ sides, not 18.

Comment by Byron Schmuland

2011-10-21T15:17:35Z

In my solution $\varepsilon_K(\omega)>0$ and $K(\omega)$ can be random. Only $S$ must be a non-random set.

Comment by Byron Schmuland

2011-09-29T02:23:31Z

Crossposted: math.stackexchange.com/questions/68395/…

Comment by Byron Schmuland

2011-09-25T20:08:55Z

Can someone help me hyperlink to the MSE question? I couldn't make it work.

Comment by Byron Schmuland

2011-09-23T00:56:54Z

Crossposted: math.stackexchange.com/questions/66777/…

Comment by Byron Schmuland

2011-08-30T15:27:55Z

Asked and answered at MathSE: math.stackexchange.com/questions/58018/…

Comment by Byron Schmuland

2011-04-26T17:46:48Z

This is part (a) of problem 11524 in the October 2010 issue of the American Mathematical Monthly.

Comment by Byron Schmuland

2011-04-23T15:49:21Z

This could also be of interest: mathoverflow.net/questions/44408/…

Comment by Byron Schmuland

2011-03-09T02:39:16Z

@George: Would the negative result also follow from the Martingale Representation Theorem? The martingale jump process $N_t-t$ cannot be represented as a stochastic integral with respect to BM, since it doesn't have continuous sample paths.