Mixing
Convergence of discrete function satisfying $|f_k+1(X_k)|leq deltaVert fVert_infty$ for $X_k$ Markov chain
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let $Nsubset mathbb N$ be a finite set. Define the sequence of functions $f_k: Ntomathbb R$. Let $X_k$ be a homogeneous irreducible aperiodic Markov chain taking values in $N$ with no absorbing states. Assume that $f_k+1(X_k)$ satisfies the following:
beginaligntag1
| f_k+1(X_k) |leq delta Vert f_kVert_infty
texta. s.
endalign
with $deltain(0,1)$.
Question: Can we know something about the convergence of $f_k$? If nothing, what kind of conditions do we need to get some kind of convergence?
Attempts. I think that $f_kto 0$ at least pointwise. But I cannot use usual tools, because there is some randomness going on here. My stochastic process knowledge is weak, but I tried the following. Define $tau_n:=sum_j=1^n Y_j$ where $Y_j$ is the time it takes to get to see each state of $X_k$ at least once starting from where we were last in $Y_j-1$. Then from $(1)$ we immediately see the following:
$$Vert f_tau_n+1Vert_infty leq delta Vert f_tau_nVert_infty$$ Clearly $f_tau_nto 0$ as $ntoinfty$ (I don't know what kind of convergence do we have here?). It seems that now I have something like: given $varepsilon>0$, then there is some random time $tau$ such that for all $k>tau$ one has:
beginalign
Vert f_k Vert_infty leq Vert f_tauVert_infty <varepsilon
endalign
Can we conclude $f_kto 0$ then? What bothers me is the random time $tau$. Also I think that I need some assumptions on $tau_n$ like $tau_n<infty$ a.s., is that true?
I appreciate any help. Even hints like "You need to study that part of that book.". Thanks in advance!
(This is actually part of a larger problem where I'm trying to show that the error made in an algorithm will be zero eventuallly)
convergence stochastic-processes stopping-times
asked Jul 16 at 11:46
Shashi
6,1261523
add a comment |Â
up vote
2
down vote
favorite
Let $Nsubset mathbb N$ be a finite set. Define the sequence of functions $f_k: Ntomathbb R$. Let $X_k$ be a homogeneous irreducible aperiodic Markov chain taking values in $N$ with no absorbing states. Assume that $f_k+1(X_k)$ satisfies the following:
beginaligntag1
| f_k+1(X_k) |leq delta Vert f_kVert_infty
texta. s.
endalign
with $deltain(0,1)$.
Question: Can we know something about the convergence of $f_k$? If nothing, what kind of conditions do we need to get some kind of convergence?
Attempts. I think that $f_kto 0$ at least pointwise. But I cannot use usual tools, because there is some randomness going on here. My stochastic process knowledge is weak, but I tried the following. Define $tau_n:=sum_j=1^n Y_j$ where $Y_j$ is the time it takes to get to see each state of $X_k$ at least once starting from where we were last in $Y_j-1$. Then from $(1)$ we immediately see the following:
$$Vert f_tau_n+1Vert_infty leq delta Vert f_tau_nVert_infty$$ Clearly $f_tau_nto 0$ as $ntoinfty$ (I don't know what kind of convergence do we have here?). It seems that now I have something like: given $varepsilon>0$, then there is some random time $tau$ such that for all $k>tau$ one has:
beginalign
Vert f_k Vert_infty leq Vert f_tauVert_infty <varepsilon
endalign
Can we conclude $f_kto 0$ then? What bothers me is the random time $tau$. Also I think that I need some assumptions on $tau_n$ like $tau_n<infty$ a.s., is that true?
I appreciate any help. Even hints like "You need to study that part of that book.". Thanks in advance!
(This is actually part of a larger problem where I'm trying to show that the error made in an algorithm will be zero eventuallly)
convergence stochastic-processes stopping-times
asked Jul 16 at 11:46
Shashi
6,1261523
@nicomezi yes, I forgot. Edited.
– Shashi
Jul 16 at 12:24
Does equality (1) hold with probability 1? Is the chain aperiodic?
– Michael
Jul 16 at 13:34
@Michael it is actually also aperiodic. I'll add that too.
– Shashi
Jul 16 at 14:40
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let $Nsubset mathbb N$ be a finite set. Define the sequence of functions $f_k: Ntomathbb R$. Let $X_k$ be a homogeneous irreducible aperiodic Markov chain taking values in $N$ with no absorbing states. Assume that $f_k+1(X_k)$ satisfies the following:
beginaligntag1
| f_k+1(X_k) |leq delta Vert f_kVert_infty
texta. s.
endalign
with $deltain(0,1)$.
Question: Can we know something about the convergence of $f_k$? If nothing, what kind of conditions do we need to get some kind of convergence?
Attempts. I think that $f_kto 0$ at least pointwise. But I cannot use usual tools, because there is some randomness going on here. My stochastic process knowledge is weak, but I tried the following. Define $tau_n:=sum_j=1^n Y_j$ where $Y_j$ is the time it takes to get to see each state of $X_k$ at least once starting from where we were last in $Y_j-1$. Then from $(1)$ we immediately see the following:
$$Vert f_tau_n+1Vert_infty leq delta Vert f_tau_nVert_infty$$ Clearly $f_tau_nto 0$ as $ntoinfty$ (I don't know what kind of convergence do we have here?). It seems that now I have something like: given $varepsilon>0$, then there is some random time $tau$ such that for all $k>tau$ one has:
beginalign
Vert f_k Vert_infty leq Vert f_tauVert_infty <varepsilon
endalign
Can we conclude $f_kto 0$ then? What bothers me is the random time $tau$. Also I think that I need some assumptions on $tau_n$ like $tau_n<infty$ a.s., is that true?
I appreciate any help. Even hints like "You need to study that part of that book.". Thanks in advance!
(This is actually part of a larger problem where I'm trying to show that the error made in an algorithm will be zero eventuallly)
convergence stochastic-processes stopping-times
asked Jul 16 at 11:46
Shashi
6,1261523
Let $Nsubset mathbb N$ be a finite set. Define the sequence of functions $f_k: Ntomathbb R$. Let $X_k$ be a homogeneous irreducible aperiodic Markov chain taking values in $N$ with no absorbing states. Assume that $f_k+1(X_k)$ satisfies the following:
beginaligntag1
| f_k+1(X_k) |leq delta Vert f_kVert_infty
texta. s.
endalign
with $deltain(0,1)$.
Question: Can we know something about the convergence of $f_k$? If nothing, what kind of conditions do we need to get some kind of convergence?
Attempts. I think that $f_kto 0$ at least pointwise. But I cannot use usual tools, because there is some randomness going on here. My stochastic process knowledge is weak, but I tried the following. Define $tau_n:=sum_j=1^n Y_j$ where $Y_j$ is the time it takes to get to see each state of $X_k$ at least once starting from where we were last in $Y_j-1$. Then from $(1)$ we immediately see the following:
$$Vert f_tau_n+1Vert_infty leq delta Vert f_tau_nVert_infty$$ Clearly $f_tau_nto 0$ as $ntoinfty$ (I don't know what kind of convergence do we have here?). It seems that now I have something like: given $varepsilon>0$, then there is some random time $tau$ such that for all $k>tau$ one has:
beginalign
Vert f_k Vert_infty leq Vert f_tauVert_infty <varepsilon
endalign
Can we conclude $f_kto 0$ then? What bothers me is the random time $tau$. Also I think that I need some assumptions on $tau_n$ like $tau_n<infty$ a.s., is that true?
I appreciate any help. Even hints like "You need to study that part of that book.". Thanks in advance!
(This is actually part of a larger problem where I'm trying to show that the error made in an algorithm will be zero eventuallly)
convergence stochastic-processes stopping-times
asked Jul 16 at 11:46
Shashi
6,1261523
edited Jul 16 at 14:47
asked Jul 16 at 11:46
Shashi
6,1261523
asked Jul 16 at 11:46
Shashi
6,1261523
asked Jul 16 at 11:46
Shashi
6,1261523
6,1261523
@nicomezi yes, I forgot. Edited.
– Shashi
Jul 16 at 12:24
Does equality (1) hold with probability 1? Is the chain aperiodic?
– Michael
Jul 16 at 13:34
@Michael it is actually also aperiodic. I'll add that too.
– Shashi
Jul 16 at 14:40
add a comment |Â
@nicomezi yes, I forgot. Edited.
– Shashi
Jul 16 at 12:24
Does equality (1) hold with probability 1? Is the chain aperiodic?
– Michael
Jul 16 at 13:34
@Michael it is actually also aperiodic. I'll add that too.
– Shashi
Jul 16 at 14:40
@nicomezi yes, I forgot. Edited.
– Shashi
Jul 16 at 12:24
@nicomezi yes, I forgot. Edited.
– Shashi
Jul 16 at 12:24
Does equality (1) hold with probability 1? Is the chain aperiodic?
– Michael
Jul 16 at 13:34
Does equality (1) hold with probability 1? Is the chain aperiodic?
– Michael
Jul 16 at 13:34
@Michael it is actually also aperiodic. I'll add that too.
– Shashi
Jul 16 at 14:40
@Michael it is actually also aperiodic. I'll add that too.
– Shashi
Jul 16 at 14:40
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
For simplicity, assume that the initial condition of the Markov chain is fixed, say, $X_0=0$ surely, where $0$ is a particular state in $N$. Your equality (1) is equivalent to: For all $k in 0, 1, 2, ...$ we have
$$ |f_k+1(X_k)|leq delta max_x in N |f_k(x)| quad mbox(with prob 1) quad (1)$$
where $delta in (0,1)$ is a given constant.
If the chain is irreducible and aperiodic
Since the chain is finite state, irreducible, and aperiodic, there is a (deterministic) time index $K$ such that for every $y in N$, we have
$$ P[X_k = y] >0 quad forall k geq K$$
(This can be proven from the fact that aperiodic means there is a $tildeK$ such that it is possible to go from state $0$ to state $0$ in $k$ hops whenever $k geq tildeK$.) Fix $y in N, k geq K$. If $f_k+1(y)>delta max_x in N |f_k(x)|$ then
$$Pleft[|f_k+1(X_k)|> delta max_x in N|f_k(x)|right] geq P[X_k=y]>0$$
which contradicts (1). Thus,
$$ |f_k+1(y) |leq delta max_x in N |f_k(x)| quad forall y in N, forall k geq K$$
Taking a max of both sides over all $y in N$ gives
$$max_y in N |f_k+1(y)|leq delta max_xin N |f_k(x)| quad forall k geq K$$
and so $lim_krightarrowinftymax_x in N |f_k(x)|= 0$.
If the chain is irreducible but not aperiodic
Here is a counter-example: Let $N=0,1$ and consider the Markov chain that deterministically alternates between states 0 and 1 over time $k in 0, 1, 2, ...$:
$$ X_k = left{ beginarrayll
0 &mbox if $k$ is even \
1 & mbox if $k$ is odd
endarray
right.$$
It is easy to construct functions $f_k:0,1rightarrowmathbbR$ that satisfy (1) with $delta = 1/2$ such that
$$ lim_krightarrowinftymax_x in 0,1 |f_k(x)| = infty$$
answered Jul 16 at 13:55
Michael
12.2k11325
So $K$ is random, right? How could that be non-problematic? Sorry if this is a silly question. Also your comment says that (1) implies $|f_k+1(X_k)|leq delta |f_k(X_k-1)|$, but that is stronger than (1) itself, so I doubt the truth of it...
– Shashi
Jul 16 at 14:44
$K$ is not random. I updated my answer to emphasize that, with some explanation.
– Michael
Jul 16 at 16:26
You are right about the extra comment I had after my answer, so I deleted it. It does not affect my answer.
– Michael
Jul 16 at 16:27
Thanks for the explanation. One last question about some possible generalization, if one assumes $f_k:Ntimes Omegatomathbb R$ is random which is fully determined by $sigma(X_1,...,X_k)$ or see $f_k$ as a random vector with dimension $N$, then I think the same argument applies. Is that true or things get non-trivial then?
– Shashi
Jul 16 at 18:05
It depends on your revised condition (1)'. It seems you now have functions $f_k(a, X_1, ..., X_k)$ for $a in N$ and random $X_1, ..., X_k$ in $N$. Then what is the meaning of $||f_k||$? Is it $max_a, x_1, ..., x_k |f_k(a, x_1, ..., x_k)|$? In that case there may be vectors $(a, x_1, ..., x_k)$ that never arise in the Markov chain as states $(X_k-1, X_1, ..., X_k)$, but have very large $f$ values (similar to my counter-example for the periodic case).
– Michael
Jul 16 at 18:13
 |Â
show 3 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
For simplicity, assume that the initial condition of the Markov chain is fixed, say, $X_0=0$ surely, where $0$ is a particular state in $N$. Your equality (1) is equivalent to: For all $k in 0, 1, 2, ...$ we have
$$ |f_k+1(X_k)|leq delta max_x in N |f_k(x)| quad mbox(with prob 1) quad (1)$$
where $delta in (0,1)$ is a given constant.
If the chain is irreducible and aperiodic
Since the chain is finite state, irreducible, and aperiodic, there is a (deterministic) time index $K$ such that for every $y in N$, we have
$$ P[X_k = y] >0 quad forall k geq K$$
(This can be proven from the fact that aperiodic means there is a $tildeK$ such that it is possible to go from state $0$ to state $0$ in $k$ hops whenever $k geq tildeK$.) Fix $y in N, k geq K$. If $f_k+1(y)>delta max_x in N |f_k(x)|$ then
$$Pleft[|f_k+1(X_k)|> delta max_x in N|f_k(x)|right] geq P[X_k=y]>0$$
which contradicts (1). Thus,
$$ |f_k+1(y) |leq delta max_x in N |f_k(x)| quad forall y in N, forall k geq K$$
Taking a max of both sides over all $y in N$ gives
$$max_y in N |f_k+1(y)|leq delta max_xin N |f_k(x)| quad forall k geq K$$
and so $lim_krightarrowinftymax_x in N |f_k(x)|= 0$.
If the chain is irreducible but not aperiodic
Here is a counter-example: Let $N=0,1$ and consider the Markov chain that deterministically alternates between states 0 and 1 over time $k in 0, 1, 2, ...$:
$$ X_k = left{ beginarrayll
0 &mbox if $k$ is even \
1 & mbox if $k$ is odd
endarray
right.$$
It is easy to construct functions $f_k:0,1rightarrowmathbbR$ that satisfy (1) with $delta = 1/2$ such that
$$ lim_krightarrowinftymax_x in 0,1 |f_k(x)| = infty$$
answered Jul 16 at 13:55
Michael
12.2k11325
So $K$ is random, right? How could that be non-problematic? Sorry if this is a silly question. Also your comment says that (1) implies $|f_k+1(X_k)|leq delta |f_k(X_k-1)|$, but that is stronger than (1) itself, so I doubt the truth of it...
– Shashi
Jul 16 at 14:44
$K$ is not random. I updated my answer to emphasize that, with some explanation.
– Michael
Jul 16 at 16:26
You are right about the extra comment I had after my answer, so I deleted it. It does not affect my answer.
– Michael
Jul 16 at 16:27
Thanks for the explanation. One last question about some possible generalization, if one assumes $f_k:Ntimes Omegatomathbb R$ is random which is fully determined by $sigma(X_1,...,X_k)$ or see $f_k$ as a random vector with dimension $N$, then I think the same argument applies. Is that true or things get non-trivial then?
– Shashi
Jul 16 at 18:05
It depends on your revised condition (1)'. It seems you now have functions $f_k(a, X_1, ..., X_k)$ for $a in N$ and random $X_1, ..., X_k$ in $N$. Then what is the meaning of $||f_k||$? Is it $max_a, x_1, ..., x_k |f_k(a, x_1, ..., x_k)|$? In that case there may be vectors $(a, x_1, ..., x_k)$ that never arise in the Markov chain as states $(X_k-1, X_1, ..., X_k)$, but have very large $f$ values (similar to my counter-example for the periodic case).
– Michael
Jul 16 at 18:13
 |Â
show 3 more comments
up vote
1
down vote
accepted
For simplicity, assume that the initial condition of the Markov chain is fixed, say, $X_0=0$ surely, where $0$ is a particular state in $N$. Your equality (1) is equivalent to: For all $k in 0, 1, 2, ...$ we have
$$ |f_k+1(X_k)|leq delta max_x in N |f_k(x)| quad mbox(with prob 1) quad (1)$$
where $delta in (0,1)$ is a given constant.
If the chain is irreducible and aperiodic
Since the chain is finite state, irreducible, and aperiodic, there is a (deterministic) time index $K$ such that for every $y in N$, we have
$$ P[X_k = y] >0 quad forall k geq K$$
(This can be proven from the fact that aperiodic means there is a $tildeK$ such that it is possible to go from state $0$ to state $0$ in $k$ hops whenever $k geq tildeK$.) Fix $y in N, k geq K$. If $f_k+1(y)>delta max_x in N |f_k(x)|$ then
$$Pleft[|f_k+1(X_k)|> delta max_x in N|f_k(x)|right] geq P[X_k=y]>0$$
which contradicts (1). Thus,
$$ |f_k+1(y) |leq delta max_x in N |f_k(x)| quad forall y in N, forall k geq K$$
Taking a max of both sides over all $y in N$ gives
$$max_y in N |f_k+1(y)|leq delta max_xin N |f_k(x)| quad forall k geq K$$
and so $lim_krightarrowinftymax_x in N |f_k(x)|= 0$.
If the chain is irreducible but not aperiodic
Here is a counter-example: Let $N=0,1$ and consider the Markov chain that deterministically alternates between states 0 and 1 over time $k in 0, 1, 2, ...$:
$$ X_k = left{ beginarrayll
0 &mbox if $k$ is even \
1 & mbox if $k$ is odd
endarray
right.$$
It is easy to construct functions $f_k:0,1rightarrowmathbbR$ that satisfy (1) with $delta = 1/2$ such that
$$ lim_krightarrowinftymax_x in 0,1 |f_k(x)| = infty$$
answered Jul 16 at 13:55
Michael
12.2k11325
So $K$ is random, right? How could that be non-problematic? Sorry if this is a silly question. Also your comment says that (1) implies $|f_k+1(X_k)|leq delta |f_k(X_k-1)|$, but that is stronger than (1) itself, so I doubt the truth of it...
– Shashi
Jul 16 at 14:44
$K$ is not random. I updated my answer to emphasize that, with some explanation.
– Michael
Jul 16 at 16:26
You are right about the extra comment I had after my answer, so I deleted it. It does not affect my answer.
– Michael
Jul 16 at 16:27
Thanks for the explanation. One last question about some possible generalization, if one assumes $f_k:Ntimes Omegatomathbb R$ is random which is fully determined by $sigma(X_1,...,X_k)$ or see $f_k$ as a random vector with dimension $N$, then I think the same argument applies. Is that true or things get non-trivial then?
– Shashi
Jul 16 at 18:05
It depends on your revised condition (1)'. It seems you now have functions $f_k(a, X_1, ..., X_k)$ for $a in N$ and random $X_1, ..., X_k$ in $N$. Then what is the meaning of $||f_k||$? Is it $max_a, x_1, ..., x_k |f_k(a, x_1, ..., x_k)|$? In that case there may be vectors $(a, x_1, ..., x_k)$ that never arise in the Markov chain as states $(X_k-1, X_1, ..., X_k)$, but have very large $f$ values (similar to my counter-example for the periodic case).
– Michael
Jul 16 at 18:13
 |Â
show 3 more comments
up vote
1
down vote
accepted
up vote
1
down vote
accepted
For simplicity, assume that the initial condition of the Markov chain is fixed, say, $X_0=0$ surely, where $0$ is a particular state in $N$. Your equality (1) is equivalent to: For all $k in 0, 1, 2, ...$ we have
$$ |f_k+1(X_k)|leq delta max_x in N |f_k(x)| quad mbox(with prob 1) quad (1)$$
where $delta in (0,1)$ is a given constant.
If the chain is irreducible and aperiodic
Since the chain is finite state, irreducible, and aperiodic, there is a (deterministic) time index $K$ such that for every $y in N$, we have
$$ P[X_k = y] >0 quad forall k geq K$$
(This can be proven from the fact that aperiodic means there is a $tildeK$ such that it is possible to go from state $0$ to state $0$ in $k$ hops whenever $k geq tildeK$.) Fix $y in N, k geq K$. If $f_k+1(y)>delta max_x in N |f_k(x)|$ then
$$Pleft[|f_k+1(X_k)|> delta max_x in N|f_k(x)|right] geq P[X_k=y]>0$$
which contradicts (1). Thus,
$$ |f_k+1(y) |leq delta max_x in N |f_k(x)| quad forall y in N, forall k geq K$$
Taking a max of both sides over all $y in N$ gives
$$max_y in N |f_k+1(y)|leq delta max_xin N |f_k(x)| quad forall k geq K$$
and so $lim_krightarrowinftymax_x in N |f_k(x)|= 0$.
If the chain is irreducible but not aperiodic
Here is a counter-example: Let $N=0,1$ and consider the Markov chain that deterministically alternates between states 0 and 1 over time $k in 0, 1, 2, ...$:
$$ X_k = left{ beginarrayll
0 &mbox if $k$ is even \
1 & mbox if $k$ is odd
endarray
right.$$
It is easy to construct functions $f_k:0,1rightarrowmathbbR$ that satisfy (1) with $delta = 1/2$ such that
$$ lim_krightarrowinftymax_x in 0,1 |f_k(x)| = infty$$
answered Jul 16 at 13:55
Michael
12.2k11325
For simplicity, assume that the initial condition of the Markov chain is fixed, say, $X_0=0$ surely, where $0$ is a particular state in $N$. Your equality (1) is equivalent to: For all $k in 0, 1, 2, ...$ we have
$$ |f_k+1(X_k)|leq delta max_x in N |f_k(x)| quad mbox(with prob 1) quad (1)$$
where $delta in (0,1)$ is a given constant.
If the chain is irreducible and aperiodic
Since the chain is finite state, irreducible, and aperiodic, there is a (deterministic) time index $K$ such that for every $y in N$, we have
$$ P[X_k = y] >0 quad forall k geq K$$
(This can be proven from the fact that aperiodic means there is a $tildeK$ such that it is possible to go from state $0$ to state $0$ in $k$ hops whenever $k geq tildeK$.) Fix $y in N, k geq K$. If $f_k+1(y)>delta max_x in N |f_k(x)|$ then
$$Pleft[|f_k+1(X_k)|> delta max_x in N|f_k(x)|right] geq P[X_k=y]>0$$
which contradicts (1). Thus,
$$ |f_k+1(y) |leq delta max_x in N |f_k(x)| quad forall y in N, forall k geq K$$
Taking a max of both sides over all $y in N$ gives
$$max_y in N |f_k+1(y)|leq delta max_xin N |f_k(x)| quad forall k geq K$$
and so $lim_krightarrowinftymax_x in N |f_k(x)|= 0$.
If the chain is irreducible but not aperiodic
Here is a counter-example: Let $N=0,1$ and consider the Markov chain that deterministically alternates between states 0 and 1 over time $k in 0, 1, 2, ...$:
$$ X_k = left{ beginarrayll
0 &mbox if $k$ is even \
1 & mbox if $k$ is odd
endarray
right.$$
It is easy to construct functions $f_k:0,1rightarrowmathbbR$ that satisfy (1) with $delta = 1/2$ such that
$$ lim_krightarrowinftymax_x in 0,1 |f_k(x)| = infty$$
answered Jul 16 at 13:55
Michael
12.2k11325
edited Jul 16 at 18:17
answered Jul 16 at 13:55
Michael
12.2k11325
answered Jul 16 at 13:55
Michael
12.2k11325
answered Jul 16 at 13:55
Michael
12.2k11325
12.2k11325
So $K$ is random, right? How could that be non-problematic? Sorry if this is a silly question. Also your comment says that (1) implies $|f_k+1(X_k)|leq delta |f_k(X_k-1)|$, but that is stronger than (1) itself, so I doubt the truth of it...
– Shashi
Jul 16 at 14:44
$K$ is not random. I updated my answer to emphasize that, with some explanation.
– Michael
Jul 16 at 16:26
You are right about the extra comment I had after my answer, so I deleted it. It does not affect my answer.
– Michael
Jul 16 at 16:27
Thanks for the explanation. One last question about some possible generalization, if one assumes $f_k:Ntimes Omegatomathbb R$ is random which is fully determined by $sigma(X_1,...,X_k)$ or see $f_k$ as a random vector with dimension $N$, then I think the same argument applies. Is that true or things get non-trivial then?
– Shashi
Jul 16 at 18:05
It depends on your revised condition (1)'. It seems you now have functions $f_k(a, X_1, ..., X_k)$ for $a in N$ and random $X_1, ..., X_k$ in $N$. Then what is the meaning of $||f_k||$? Is it $max_a, x_1, ..., x_k |f_k(a, x_1, ..., x_k)|$? In that case there may be vectors $(a, x_1, ..., x_k)$ that never arise in the Markov chain as states $(X_k-1, X_1, ..., X_k)$, but have very large $f$ values (similar to my counter-example for the periodic case).
– Michael
Jul 16 at 18:13
 |Â
show 3 more comments
So $K$ is random, right? How could that be non-problematic? Sorry if this is a silly question. Also your comment says that (1) implies $|f_k+1(X_k)|leq delta |f_k(X_k-1)|$, but that is stronger than (1) itself, so I doubt the truth of it...
– Shashi
Jul 16 at 14:44
$K$ is not random. I updated my answer to emphasize that, with some explanation.
– Michael
Jul 16 at 16:26
You are right about the extra comment I had after my answer, so I deleted it. It does not affect my answer.
– Michael
Jul 16 at 16:27
Thanks for the explanation. One last question about some possible generalization, if one assumes $f_k:Ntimes Omegatomathbb R$ is random which is fully determined by $sigma(X_1,...,X_k)$ or see $f_k$ as a random vector with dimension $N$, then I think the same argument applies. Is that true or things get non-trivial then?
– Shashi
Jul 16 at 18:05
It depends on your revised condition (1)'. It seems you now have functions $f_k(a, X_1, ..., X_k)$ for $a in N$ and random $X_1, ..., X_k$ in $N$. Then what is the meaning of $||f_k||$? Is it $max_a, x_1, ..., x_k |f_k(a, x_1, ..., x_k)|$? In that case there may be vectors $(a, x_1, ..., x_k)$ that never arise in the Markov chain as states $(X_k-1, X_1, ..., X_k)$, but have very large $f$ values (similar to my counter-example for the periodic case).
– Michael
Jul 16 at 18:13
So $K$ is random, right? How could that be non-problematic? Sorry if this is a silly question. Also your comment says that (1) implies $|f_k+1(X_k)|leq delta |f_k(X_k-1)|$, but that is stronger than (1) itself, so I doubt the truth of it...
– Shashi
Jul 16 at 14:44
So $K$ is random, right? How could that be non-problematic? Sorry if this is a silly question. Also your comment says that (1) implies $|f_k+1(X_k)|leq delta |f_k(X_k-1)|$, but that is stronger than (1) itself, so I doubt the truth of it...
– Shashi
Jul 16 at 14:44
$K$ is not random. I updated my answer to emphasize that, with some explanation.
– Michael
Jul 16 at 16:26
$K$ is not random. I updated my answer to emphasize that, with some explanation.
– Michael
Jul 16 at 16:26
You are right about the extra comment I had after my answer, so I deleted it. It does not affect my answer.
– Michael
Jul 16 at 16:27
You are right about the extra comment I had after my answer, so I deleted it. It does not affect my answer.
– Michael
Jul 16 at 16:27
Thanks for the explanation. One last question about some possible generalization, if one assumes $f_k:Ntimes Omegatomathbb R$ is random which is fully determined by $sigma(X_1,...,X_k)$ or see $f_k$ as a random vector with dimension $N$, then I think the same argument applies. Is that true or things get non-trivial then?
– Shashi
Jul 16 at 18:05
Thanks for the explanation. One last question about some possible generalization, if one assumes $f_k:Ntimes Omegatomathbb R$ is random which is fully determined by $sigma(X_1,...,X_k)$ or see $f_k$ as a random vector with dimension $N$, then I think the same argument applies. Is that true or things get non-trivial then?
– Shashi
Jul 16 at 18:05
It depends on your revised condition (1)'. It seems you now have functions $f_k(a, X_1, ..., X_k)$ for $a in N$ and random $X_1, ..., X_k$ in $N$. Then what is the meaning of $||f_k||$? Is it $max_a, x_1, ..., x_k |f_k(a, x_1, ..., x_k)|$? In that case there may be vectors $(a, x_1, ..., x_k)$ that never arise in the Markov chain as states $(X_k-1, X_1, ..., X_k)$, but have very large $f$ values (similar to my counter-example for the periodic case).
– Michael
Jul 16 at 18:13
It depends on your revised condition (1)'. It seems you now have functions $f_k(a, X_1, ..., X_k)$ for $a in N$ and random $X_1, ..., X_k$ in $N$. Then what is the meaning of $||f_k||$? Is it $max_a, x_1, ..., x_k |f_k(a, x_1, ..., x_k)|$? In that case there may be vectors $(a, x_1, ..., x_k)$ that never arise in the Markov chain as states $(X_k-1, X_1, ..., X_k)$, but have very large $f$ values (similar to my counter-example for the periodic case).
– Michael
Jul 16 at 18:13
 |Â
show 3 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853338%2fconvergence-of-discrete-function-satisfying-f-k1x-k-leq-delta-vert-f-ve%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
@nicomezi yes, I forgot. Edited.
– Shashi
Jul 16 at 12:24
Does equality (1) hold with probability 1? Is the chain aperiodic?
– Michael
Jul 16 at 13:34
@Michael it is actually also aperiodic. I'll add that too.
– Shashi
Jul 16 at 14:40