Probability that random walk will reach state $k$ for the first time on step $n$
$begingroup$
We have a random walk which starts in state $0$. At each step, a coin is tossed with probability of heads: $P(H)=p$. If we get a heads, we go to the next higher integer state and on tails, we go to the next lower integer state (so state $n$ would go to $n+1$ on heads and $n-1$ on tails).
Now, I want to know the probability that we will reach state $k$ for the first time after exactly $n$ tosses of the coin. Turning out to be surprisingly hard for me.
Here is my attempt:
I define $a_n^{k}$ as the probability described above and $c_n^k$ as the probability that the random walk will be in state $k$ at toss $n$ (regardless of if it was there in a previous toss).
It's clear that we need $left(frac{n-k}{2}right)$ tails and $left(frac{n+k}{2}right)$ heads. So if $n-k$ is not even, the sequences for those $n$'s become $0$.
To get $a_n^k$, we need to identify all sequences where the cumulative number of heads stays less than $k$ + the cumulative number of tails for all tosses leading upto $n$. This is not so easy to solve.
On the other hand, I got an expression for $c_n^k$ and hoped I could use it to get $a_n^k$. I reasoned that the probability the walk reaches $k$ for the first time on toss $n$ is the probability it is in state $k$ on toss $n$ subtracted by the probabilities that it was in state $k$ in any previous toss. So,
$$a_n^k = c_n^k - sum_{i=1}^{n-1} c_i^k$$
But this can't be right since this expression will become negative for many values of $n$.
probability combinatorics markov-chains random-walk
$endgroup$
add a comment |
$begingroup$
We have a random walk which starts in state $0$. At each step, a coin is tossed with probability of heads: $P(H)=p$. If we get a heads, we go to the next higher integer state and on tails, we go to the next lower integer state (so state $n$ would go to $n+1$ on heads and $n-1$ on tails).
Now, I want to know the probability that we will reach state $k$ for the first time after exactly $n$ tosses of the coin. Turning out to be surprisingly hard for me.
Here is my attempt:
I define $a_n^{k}$ as the probability described above and $c_n^k$ as the probability that the random walk will be in state $k$ at toss $n$ (regardless of if it was there in a previous toss).
It's clear that we need $left(frac{n-k}{2}right)$ tails and $left(frac{n+k}{2}right)$ heads. So if $n-k$ is not even, the sequences for those $n$'s become $0$.
To get $a_n^k$, we need to identify all sequences where the cumulative number of heads stays less than $k$ + the cumulative number of tails for all tosses leading upto $n$. This is not so easy to solve.
On the other hand, I got an expression for $c_n^k$ and hoped I could use it to get $a_n^k$. I reasoned that the probability the walk reaches $k$ for the first time on toss $n$ is the probability it is in state $k$ on toss $n$ subtracted by the probabilities that it was in state $k$ in any previous toss. So,
$$a_n^k = c_n^k - sum_{i=1}^{n-1} c_i^k$$
But this can't be right since this expression will become negative for many values of $n$.
probability combinatorics markov-chains random-walk
$endgroup$
1
$begingroup$
Still working on the solution to the question, but I do know why the reasoning at the end is wrong; the probabilities are not independent, so you can not simply subtract them from each other.
$endgroup$
– SmileyCraft
Dec 16 '18 at 19:07
$begingroup$
Appreciate it. Yeah, I suspected as much. That's almost always the reason when you add/subtract probabilities and get something not between 0 and 1. Thought I'd mention it anyway in case it inspired someone to formulate a correct approach based on the idea.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 19:09
$begingroup$
If you reverse time and flip the y axis, you are counting paths which reach k after n steps without ever returning to 0. This is Bertrand’s ballot problem.
$endgroup$
– Mike Earnest
Dec 16 '18 at 20:24
$begingroup$
Don't completely follow. If I reverse time, I start off at $k$, correct? So, doesn't it become paths that reach 0?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 20:33
$begingroup$
@RohitPandey Sorry, when I said "flip the y-axis,", I meant that you interchange $0$ with $k$.
$endgroup$
– Mike Earnest
Dec 17 '18 at 12:49
add a comment |
$begingroup$
We have a random walk which starts in state $0$. At each step, a coin is tossed with probability of heads: $P(H)=p$. If we get a heads, we go to the next higher integer state and on tails, we go to the next lower integer state (so state $n$ would go to $n+1$ on heads and $n-1$ on tails).
Now, I want to know the probability that we will reach state $k$ for the first time after exactly $n$ tosses of the coin. Turning out to be surprisingly hard for me.
Here is my attempt:
I define $a_n^{k}$ as the probability described above and $c_n^k$ as the probability that the random walk will be in state $k$ at toss $n$ (regardless of if it was there in a previous toss).
It's clear that we need $left(frac{n-k}{2}right)$ tails and $left(frac{n+k}{2}right)$ heads. So if $n-k$ is not even, the sequences for those $n$'s become $0$.
To get $a_n^k$, we need to identify all sequences where the cumulative number of heads stays less than $k$ + the cumulative number of tails for all tosses leading upto $n$. This is not so easy to solve.
On the other hand, I got an expression for $c_n^k$ and hoped I could use it to get $a_n^k$. I reasoned that the probability the walk reaches $k$ for the first time on toss $n$ is the probability it is in state $k$ on toss $n$ subtracted by the probabilities that it was in state $k$ in any previous toss. So,
$$a_n^k = c_n^k - sum_{i=1}^{n-1} c_i^k$$
But this can't be right since this expression will become negative for many values of $n$.
probability combinatorics markov-chains random-walk
$endgroup$
We have a random walk which starts in state $0$. At each step, a coin is tossed with probability of heads: $P(H)=p$. If we get a heads, we go to the next higher integer state and on tails, we go to the next lower integer state (so state $n$ would go to $n+1$ on heads and $n-1$ on tails).
Now, I want to know the probability that we will reach state $k$ for the first time after exactly $n$ tosses of the coin. Turning out to be surprisingly hard for me.
Here is my attempt:
I define $a_n^{k}$ as the probability described above and $c_n^k$ as the probability that the random walk will be in state $k$ at toss $n$ (regardless of if it was there in a previous toss).
It's clear that we need $left(frac{n-k}{2}right)$ tails and $left(frac{n+k}{2}right)$ heads. So if $n-k$ is not even, the sequences for those $n$'s become $0$.
To get $a_n^k$, we need to identify all sequences where the cumulative number of heads stays less than $k$ + the cumulative number of tails for all tosses leading upto $n$. This is not so easy to solve.
On the other hand, I got an expression for $c_n^k$ and hoped I could use it to get $a_n^k$. I reasoned that the probability the walk reaches $k$ for the first time on toss $n$ is the probability it is in state $k$ on toss $n$ subtracted by the probabilities that it was in state $k$ in any previous toss. So,
$$a_n^k = c_n^k - sum_{i=1}^{n-1} c_i^k$$
But this can't be right since this expression will become negative for many values of $n$.
probability combinatorics markov-chains random-walk
probability combinatorics markov-chains random-walk
edited Dec 18 '18 at 2:28
Rohit Pandey
asked Dec 16 '18 at 19:00
Rohit PandeyRohit Pandey
1,4901023
1,4901023
1
$begingroup$
Still working on the solution to the question, but I do know why the reasoning at the end is wrong; the probabilities are not independent, so you can not simply subtract them from each other.
$endgroup$
– SmileyCraft
Dec 16 '18 at 19:07
$begingroup$
Appreciate it. Yeah, I suspected as much. That's almost always the reason when you add/subtract probabilities and get something not between 0 and 1. Thought I'd mention it anyway in case it inspired someone to formulate a correct approach based on the idea.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 19:09
$begingroup$
If you reverse time and flip the y axis, you are counting paths which reach k after n steps without ever returning to 0. This is Bertrand’s ballot problem.
$endgroup$
– Mike Earnest
Dec 16 '18 at 20:24
$begingroup$
Don't completely follow. If I reverse time, I start off at $k$, correct? So, doesn't it become paths that reach 0?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 20:33
$begingroup$
@RohitPandey Sorry, when I said "flip the y-axis,", I meant that you interchange $0$ with $k$.
$endgroup$
– Mike Earnest
Dec 17 '18 at 12:49
add a comment |
1
$begingroup$
Still working on the solution to the question, but I do know why the reasoning at the end is wrong; the probabilities are not independent, so you can not simply subtract them from each other.
$endgroup$
– SmileyCraft
Dec 16 '18 at 19:07
$begingroup$
Appreciate it. Yeah, I suspected as much. That's almost always the reason when you add/subtract probabilities and get something not between 0 and 1. Thought I'd mention it anyway in case it inspired someone to formulate a correct approach based on the idea.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 19:09
$begingroup$
If you reverse time and flip the y axis, you are counting paths which reach k after n steps without ever returning to 0. This is Bertrand’s ballot problem.
$endgroup$
– Mike Earnest
Dec 16 '18 at 20:24
$begingroup$
Don't completely follow. If I reverse time, I start off at $k$, correct? So, doesn't it become paths that reach 0?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 20:33
$begingroup$
@RohitPandey Sorry, when I said "flip the y-axis,", I meant that you interchange $0$ with $k$.
$endgroup$
– Mike Earnest
Dec 17 '18 at 12:49
1
1
$begingroup$
Still working on the solution to the question, but I do know why the reasoning at the end is wrong; the probabilities are not independent, so you can not simply subtract them from each other.
$endgroup$
– SmileyCraft
Dec 16 '18 at 19:07
$begingroup$
Still working on the solution to the question, but I do know why the reasoning at the end is wrong; the probabilities are not independent, so you can not simply subtract them from each other.
$endgroup$
– SmileyCraft
Dec 16 '18 at 19:07
$begingroup$
Appreciate it. Yeah, I suspected as much. That's almost always the reason when you add/subtract probabilities and get something not between 0 and 1. Thought I'd mention it anyway in case it inspired someone to formulate a correct approach based on the idea.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 19:09
$begingroup$
Appreciate it. Yeah, I suspected as much. That's almost always the reason when you add/subtract probabilities and get something not between 0 and 1. Thought I'd mention it anyway in case it inspired someone to formulate a correct approach based on the idea.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 19:09
$begingroup$
If you reverse time and flip the y axis, you are counting paths which reach k after n steps without ever returning to 0. This is Bertrand’s ballot problem.
$endgroup$
– Mike Earnest
Dec 16 '18 at 20:24
$begingroup$
If you reverse time and flip the y axis, you are counting paths which reach k after n steps without ever returning to 0. This is Bertrand’s ballot problem.
$endgroup$
– Mike Earnest
Dec 16 '18 at 20:24
$begingroup$
Don't completely follow. If I reverse time, I start off at $k$, correct? So, doesn't it become paths that reach 0?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 20:33
$begingroup$
Don't completely follow. If I reverse time, I start off at $k$, correct? So, doesn't it become paths that reach 0?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 20:33
$begingroup$
@RohitPandey Sorry, when I said "flip the y-axis,", I meant that you interchange $0$ with $k$.
$endgroup$
– Mike Earnest
Dec 17 '18 at 12:49
$begingroup$
@RohitPandey Sorry, when I said "flip the y-axis,", I meant that you interchange $0$ with $k$.
$endgroup$
– Mike Earnest
Dec 17 '18 at 12:49
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
After some investigation, it seems to be the case that there are $$f(k,ell)=frac{k+1}{k+1+ell}{k+2ellchooseell}$$ paths to state $kgeq0$ in $k+2ell$ steps that never pass the $k$'th state. This is equivalent to the amount of ways to move to state $k+1$ for the first time after $k+1+2ell$ steps. By substitution and simple probability, we get a $$frac{k}{k+ell}{k-1+2ellchooseell}p^{k+ell}q^{ell}$$ probability of reaching state $k$ for the first time after $k+2ell$ steps.
We can prove our formula for $f$ by induction. For $ell=0$ the answer is obviously $1$, which coincides with the given formula. For $k=-1$ the answer is obviously $0$, which also coincides with the given formula. For $ell>0$ and $kgeq0$ we have two options for the first move: right or left. If we go left, there are $f(k+1,ell-1)$ options, and if we go right there are $f(k-1,ell)$ options. Hence, in total we have
begin{align}
f(k+1,ell-1)+f(k-1,ell)
&=frac{k+2}{k+2+ell-1}{k+1+2(ell-1)chooseell-1}+frac{k}{k+ell}{k-1+2ellchooseell}
\&=frac{(k+2)(k+2ell-1)!}{(k+ell+1)(ell-1)!(k+ell)!}+frac{k(k+2ell-1)!}{(k+ell)ell!(k+ell-1)!}
\&=frac{(k+2)(k+2ell-1)!}{(ell-1)!(k+ell+1)!}+frac{k(k+2ell-1)!}{ell!(k+ell)!}
\&=frac{ell(k+2)(k+2ell-1)!}{ell!(k+ell+1)!}+frac{(k+ell+1)k(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(ell(k+2)+(k+ell+1)k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell k+2ell+k^2+k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell+k)(k+1)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(k+1)(k+2ell)!}{ell!(k+ell+1)!}
\&=f(k,ell)
end{align}
options. By principle of induction, this proves the correctness of the formula for $f$.
Now admittedly, even though this solves the problem, it is not a nice solution. I found the formula by simply experimenting for half an hour, and the proof is very algebraic and not very nice to look at. If someone comes up with a combinatorical proof, that would be much better! I am certainly going to think about it now.
$endgroup$
$begingroup$
I see, thanks. Can you briefly explain how you came up with this formula via experimentation? What was your approach to first discover it?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:11
2
$begingroup$
I took a fixed $ell$ and I expected the formula would be a polynomial of degree $ell-1$, so simply finding $ell$ terms determines the polynomial. The first few polynomials were $1$; $k+1$; $(k+1)(k+4)/2$; $(k+1)(k+5)(k+6)/6$; $(k+1)(k+6)(k+7)(k+8)/24$. At this point I found the pattern and I got the formula.
$endgroup$
– SmileyCraft
Dec 16 '18 at 21:14
$begingroup$
Sorry, one last thing I haven't understood - why didn't you just call the probability $f(k,l) p^{k+l}q^l$? Instead, you wrote it as $f(k-1,l) p^{k+l} q^l$.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:52
1
$begingroup$
To go to state $k$ for the first time after $k+2ell$ steps means to go to state $k-1$ after $k-1+2ell$ steps without going past state $k-1$ and then going right.
$endgroup$
– SmileyCraft
Dec 16 '18 at 22:09
$begingroup$
Ahh, without going past being they key. Got it, thanks again! Impressive solution.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 22:12
|
show 1 more comment
$begingroup$
This answer is an extension to the one by @SmileyCraft. As he says in his answer, it would be nice to have a combinatorial proof. I might have found one. The problem seems similar in spirit to the one where you have a square grid, start at the bottom left corner and need to get to the top-right corner and find the number of paths where you don't cross the main diagonal of the grid (ok to touch it). In that instance, the number of such paths is the catalan numbers.
$$C_n = frac{2n choose n}{n+1} = {2n choose n} - {2n choose n-1}$$
Now, taking a cue from this, the formula @SmileyCraft has above can also be written as:
$$f(k,l) = frac{k+1}{k+1+l} {k+2l choose l} = {k+2l choose l} - {k+2l choose l-1} tag{1}$$
Now, the problem here for the random walk not crossing $k$ can be converted to a grid problem. We basically have (per @SmileyCraft's convention) $l$ tails and $l+k$ heads and need to arrange them in such a way as to never cross the $k$. This is completely equivalent to saying we'll go right if we get a tails and up if we get a heads on a grid which has $l+k$ rows and $l$ columns.
Another way to see this is to plot on the x-axis the toss number and on the y-axis the score of the random walk. Now, imagine any path going from $(0,0)$ to $(k+2l,k)$. Now, simply rotate the whole picture by 45 degrees and you'll get the grid.
So the formula for $f(k,l)$ above is simply the number of ways to go from the bottom left to top right of a grid with $l$ rows and $l+k$ columns in such a way that the path never crosses the line $y=x+k$.
But how do we show that is equivalent to equation (1) above? I cheated and used the same reasoning as the answer by @Marcus M here. It goes like this:
We know the total paths in our grid are $k+2l choose l$.
The good paths are ones that never cross the line $y=x+k$. Then,
# good paths = # paths - # bad paths
Now, any bad path does cross the line $y=x+k$. So, it must touch the line $y=x+k+1$ (the diagonal just above it).
Divide any such path into two portions. The portion from the origin to when it touches the $y=x+k+1$ line and the portion after that. The first portion can be reflected about the $y=x+k+1$. And this leads to a bijection to a path from $(-(k+1),(k+1))$ to $(l,k+l)$. So, the bad paths can be mapped to paths from the bottom left to top-right of another grid whose height is $(k+l)-(k+1)=l-1$. But we didn't change the total path length, so the total length of the bad paths is still $k+2l$. Hence, the number of bad paths is $k+2l choose l-1$.
Putting all of this together, we get equation (1) above. The picture below shows this for $k=3$ and $t=2$.
$endgroup$
1
$begingroup$
I believe you are confusing your lefts and rights somewhere, but I get the proof and it is very satisfying :)
$endgroup$
– SmileyCraft
Dec 18 '18 at 16:55
$begingroup$
Yes, I did have left and right mixed up in one place. Fixed that - thanks!
$endgroup$
– Rohit Pandey
Dec 18 '18 at 20:47
add a comment |
$begingroup$
A Generating Function
Let the number of ways for getting to position $s$ for the first time on step $n$ be $a_{s,n}$. The number of unilateral walks of length $2k$ is $frac1{k+1}binom{2k}{k}$, with generating function $frac{1-sqrt{1-4x}}{2x}$. To first get to position $s$ on step $n$, we can count the number of ways to first get to position $s-1$ in $n-2k-1$ steps times the number of unilateral walks of length $2k$ and sum for all $k$. That is,
$$
a_{s,n}=sum_{k=0}^inftyfrac1{k+1}binom{2k}{k},a_{s-1,n-2k-1}tag1
$$
If we set the generating function
$$
f_s(x)=sum_{n=0}^infty a_{s,n}x^ntag2
$$
then $(1)$ implies
$$
f_s(x)=f_{s-1}(x)left(frac{1-sqrt{1-4x^2}}{2x}right)tag3
$$
and since $f_0(x)=1$, induction yields
$$
bbox[5px,border:2px solid #C0A000]{f_s(x)=left(frac{1-sqrt{1-4x^2}}{2x}right)^{large s}}tag4
$$
Therefore, if the probability of a '$+1$' step is $p$ and of a '$-1$' step is $1-p$, then the probability of $frac{n+s}2$ '$+1$' steps and $frac{n-s}2$ '$-1$' steps is $a_{s,n}p^{frac{n+s}2}(1-p)^{frac{n-s}2}=left(frac{p}{1-p}right)^{s/2}a_{s,n}(p(1-p))^{n/2}$. Summing over $n$ gives the probability of getting to position $s$ at all to be
$$
begin{align}
left(frac{p}{1-p}right)^{s/2}f_s!left(sqrt{p(1-p)}right)
&=left(frac{1-|1-2p|}{2(1-p)}right)^{large s}\[3pt]
&=left{begin{array}{}left(frac{p}{1-p}right)^s&text{if }pltfrac12\1&text{if }pgefrac12end{array}right.tag5
end{align}
$$
A Closed Form
To derive a closed form for $a_{s,n}$, we first consider the series
$$
sum_{n=0}^infty b_{s,n}x^n=left(frac{1-sqrt{1-4x}}{2x}right)^{large s}tag6
$$
where, comparing $(4)$ and $(6)$, we get
$$
begin{align}
a_{s,s+2n}&=b_{s,n}\
a_{s,s+2n+1}&=0
end{align}tag7
$$
Using the fact that
$$
left(frac{1-sqrt{1-4x}}{2x}right)^2=frac1xfrac{1-sqrt{1-4x}}{2x}-frac1xtag8
$$
we get the relation
$$
b_{s,n}=b_{s-1,n+1}-b_{s-2,n+1}tag9
$$
We know that
$$
begin{align}
b_{0,n}&=[n=0]\[3pt]
b_{1,n}&=frac1{n+1}binom{2n}{n}=binom{2n}{n}-binom{2n}{n-1}
end{align}tag{10}
$$
which implies that
$$
begin{align}
b_{2,n}&=frac1{n+2}binom{2n+2}{n+1}=binom{2n+1}{n}-binom{2n+1}{n-1}tag{11}\[6pt]
b_{3,n}&=frac1{n+3}binom{2n+4}{n+2}-frac1{n+2}binom{2n+2}{n+1}
=binom{2n+2}{n}-binom{2n+2}{n-1}tag{12}
end{align}
$$
A pattern is appearing; that is,
$$
begin{align}
b_{s,n}
&=binom{2n+s-1}{n}-binom{2n+s-1}{n-1}\[3pt]
&=frac{s}{2n+s}binom{2n+s}{n}tag{13}
end{align}
$$
which satisfies $(9)$ using Pascal's Formula. Therefore, applying $(7)$ yields
$$
bbox[5px,border:2px solid #C0A000]{a_{s,n}=left{begin{array}{}
frac snbinom{n}{(n-s)/2}=binom{n-1}{(n-s)/2}-binom{n-1}{(n-s-2)/2}&text{if }2mid n-s\
0&text{if }2nmid n-s
end{array}right.}tag{14}
$$
$endgroup$
$begingroup$
In equation (2), should the index be on $n$ instead of $k$?
$endgroup$
– Rohit Pandey
Jan 20 at 18:54
$begingroup$
Very beautiful proof. To get an actual expression for $a_{s,n}$, we can use (5.70) here (in conjunction with equation (4)): math.stackexchange.com/questions/3064256/…. This identity isn't super easy to prove, but it gets one there.
$endgroup$
– Rohit Pandey
Jan 20 at 19:39
$begingroup$
@RohitPandey: Indeed. I am working on more for the answer. As soon as I post that, the correction will be there.
$endgroup$
– robjohn♦
Jan 20 at 23:27
1
$begingroup$
@RohitPandey: I have added a derivation of the closed form as well.
$endgroup$
– robjohn♦
Jan 21 at 19:07
$begingroup$
Thanks a lot, reading through. In the meantime, I'm writing a paper on how races of wealthy gamblers can be used to estimate $pi$. I think this provides a method that converges to $pi$ reasonably fast and has a nice interpretation as well. I'll be done with the first draft very soon. Would love to have you as a co-author since your answers have helped a lot with the effort. Let me know if you're fine with it. If not, is it OK to cite your answers in it?
$endgroup$
– Rohit Pandey
Jan 21 at 19:56
|
show 2 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3043013%2fprobability-that-random-walk-will-reach-state-k-for-the-first-time-on-step-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
After some investigation, it seems to be the case that there are $$f(k,ell)=frac{k+1}{k+1+ell}{k+2ellchooseell}$$ paths to state $kgeq0$ in $k+2ell$ steps that never pass the $k$'th state. This is equivalent to the amount of ways to move to state $k+1$ for the first time after $k+1+2ell$ steps. By substitution and simple probability, we get a $$frac{k}{k+ell}{k-1+2ellchooseell}p^{k+ell}q^{ell}$$ probability of reaching state $k$ for the first time after $k+2ell$ steps.
We can prove our formula for $f$ by induction. For $ell=0$ the answer is obviously $1$, which coincides with the given formula. For $k=-1$ the answer is obviously $0$, which also coincides with the given formula. For $ell>0$ and $kgeq0$ we have two options for the first move: right or left. If we go left, there are $f(k+1,ell-1)$ options, and if we go right there are $f(k-1,ell)$ options. Hence, in total we have
begin{align}
f(k+1,ell-1)+f(k-1,ell)
&=frac{k+2}{k+2+ell-1}{k+1+2(ell-1)chooseell-1}+frac{k}{k+ell}{k-1+2ellchooseell}
\&=frac{(k+2)(k+2ell-1)!}{(k+ell+1)(ell-1)!(k+ell)!}+frac{k(k+2ell-1)!}{(k+ell)ell!(k+ell-1)!}
\&=frac{(k+2)(k+2ell-1)!}{(ell-1)!(k+ell+1)!}+frac{k(k+2ell-1)!}{ell!(k+ell)!}
\&=frac{ell(k+2)(k+2ell-1)!}{ell!(k+ell+1)!}+frac{(k+ell+1)k(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(ell(k+2)+(k+ell+1)k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell k+2ell+k^2+k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell+k)(k+1)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(k+1)(k+2ell)!}{ell!(k+ell+1)!}
\&=f(k,ell)
end{align}
options. By principle of induction, this proves the correctness of the formula for $f$.
Now admittedly, even though this solves the problem, it is not a nice solution. I found the formula by simply experimenting for half an hour, and the proof is very algebraic and not very nice to look at. If someone comes up with a combinatorical proof, that would be much better! I am certainly going to think about it now.
$endgroup$
$begingroup$
I see, thanks. Can you briefly explain how you came up with this formula via experimentation? What was your approach to first discover it?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:11
2
$begingroup$
I took a fixed $ell$ and I expected the formula would be a polynomial of degree $ell-1$, so simply finding $ell$ terms determines the polynomial. The first few polynomials were $1$; $k+1$; $(k+1)(k+4)/2$; $(k+1)(k+5)(k+6)/6$; $(k+1)(k+6)(k+7)(k+8)/24$. At this point I found the pattern and I got the formula.
$endgroup$
– SmileyCraft
Dec 16 '18 at 21:14
$begingroup$
Sorry, one last thing I haven't understood - why didn't you just call the probability $f(k,l) p^{k+l}q^l$? Instead, you wrote it as $f(k-1,l) p^{k+l} q^l$.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:52
1
$begingroup$
To go to state $k$ for the first time after $k+2ell$ steps means to go to state $k-1$ after $k-1+2ell$ steps without going past state $k-1$ and then going right.
$endgroup$
– SmileyCraft
Dec 16 '18 at 22:09
$begingroup$
Ahh, without going past being they key. Got it, thanks again! Impressive solution.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 22:12
|
show 1 more comment
$begingroup$
After some investigation, it seems to be the case that there are $$f(k,ell)=frac{k+1}{k+1+ell}{k+2ellchooseell}$$ paths to state $kgeq0$ in $k+2ell$ steps that never pass the $k$'th state. This is equivalent to the amount of ways to move to state $k+1$ for the first time after $k+1+2ell$ steps. By substitution and simple probability, we get a $$frac{k}{k+ell}{k-1+2ellchooseell}p^{k+ell}q^{ell}$$ probability of reaching state $k$ for the first time after $k+2ell$ steps.
We can prove our formula for $f$ by induction. For $ell=0$ the answer is obviously $1$, which coincides with the given formula. For $k=-1$ the answer is obviously $0$, which also coincides with the given formula. For $ell>0$ and $kgeq0$ we have two options for the first move: right or left. If we go left, there are $f(k+1,ell-1)$ options, and if we go right there are $f(k-1,ell)$ options. Hence, in total we have
begin{align}
f(k+1,ell-1)+f(k-1,ell)
&=frac{k+2}{k+2+ell-1}{k+1+2(ell-1)chooseell-1}+frac{k}{k+ell}{k-1+2ellchooseell}
\&=frac{(k+2)(k+2ell-1)!}{(k+ell+1)(ell-1)!(k+ell)!}+frac{k(k+2ell-1)!}{(k+ell)ell!(k+ell-1)!}
\&=frac{(k+2)(k+2ell-1)!}{(ell-1)!(k+ell+1)!}+frac{k(k+2ell-1)!}{ell!(k+ell)!}
\&=frac{ell(k+2)(k+2ell-1)!}{ell!(k+ell+1)!}+frac{(k+ell+1)k(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(ell(k+2)+(k+ell+1)k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell k+2ell+k^2+k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell+k)(k+1)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(k+1)(k+2ell)!}{ell!(k+ell+1)!}
\&=f(k,ell)
end{align}
options. By principle of induction, this proves the correctness of the formula for $f$.
Now admittedly, even though this solves the problem, it is not a nice solution. I found the formula by simply experimenting for half an hour, and the proof is very algebraic and not very nice to look at. If someone comes up with a combinatorical proof, that would be much better! I am certainly going to think about it now.
$endgroup$
$begingroup$
I see, thanks. Can you briefly explain how you came up with this formula via experimentation? What was your approach to first discover it?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:11
2
$begingroup$
I took a fixed $ell$ and I expected the formula would be a polynomial of degree $ell-1$, so simply finding $ell$ terms determines the polynomial. The first few polynomials were $1$; $k+1$; $(k+1)(k+4)/2$; $(k+1)(k+5)(k+6)/6$; $(k+1)(k+6)(k+7)(k+8)/24$. At this point I found the pattern and I got the formula.
$endgroup$
– SmileyCraft
Dec 16 '18 at 21:14
$begingroup$
Sorry, one last thing I haven't understood - why didn't you just call the probability $f(k,l) p^{k+l}q^l$? Instead, you wrote it as $f(k-1,l) p^{k+l} q^l$.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:52
1
$begingroup$
To go to state $k$ for the first time after $k+2ell$ steps means to go to state $k-1$ after $k-1+2ell$ steps without going past state $k-1$ and then going right.
$endgroup$
– SmileyCraft
Dec 16 '18 at 22:09
$begingroup$
Ahh, without going past being they key. Got it, thanks again! Impressive solution.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 22:12
|
show 1 more comment
$begingroup$
After some investigation, it seems to be the case that there are $$f(k,ell)=frac{k+1}{k+1+ell}{k+2ellchooseell}$$ paths to state $kgeq0$ in $k+2ell$ steps that never pass the $k$'th state. This is equivalent to the amount of ways to move to state $k+1$ for the first time after $k+1+2ell$ steps. By substitution and simple probability, we get a $$frac{k}{k+ell}{k-1+2ellchooseell}p^{k+ell}q^{ell}$$ probability of reaching state $k$ for the first time after $k+2ell$ steps.
We can prove our formula for $f$ by induction. For $ell=0$ the answer is obviously $1$, which coincides with the given formula. For $k=-1$ the answer is obviously $0$, which also coincides with the given formula. For $ell>0$ and $kgeq0$ we have two options for the first move: right or left. If we go left, there are $f(k+1,ell-1)$ options, and if we go right there are $f(k-1,ell)$ options. Hence, in total we have
begin{align}
f(k+1,ell-1)+f(k-1,ell)
&=frac{k+2}{k+2+ell-1}{k+1+2(ell-1)chooseell-1}+frac{k}{k+ell}{k-1+2ellchooseell}
\&=frac{(k+2)(k+2ell-1)!}{(k+ell+1)(ell-1)!(k+ell)!}+frac{k(k+2ell-1)!}{(k+ell)ell!(k+ell-1)!}
\&=frac{(k+2)(k+2ell-1)!}{(ell-1)!(k+ell+1)!}+frac{k(k+2ell-1)!}{ell!(k+ell)!}
\&=frac{ell(k+2)(k+2ell-1)!}{ell!(k+ell+1)!}+frac{(k+ell+1)k(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(ell(k+2)+(k+ell+1)k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell k+2ell+k^2+k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell+k)(k+1)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(k+1)(k+2ell)!}{ell!(k+ell+1)!}
\&=f(k,ell)
end{align}
options. By principle of induction, this proves the correctness of the formula for $f$.
Now admittedly, even though this solves the problem, it is not a nice solution. I found the formula by simply experimenting for half an hour, and the proof is very algebraic and not very nice to look at. If someone comes up with a combinatorical proof, that would be much better! I am certainly going to think about it now.
$endgroup$
After some investigation, it seems to be the case that there are $$f(k,ell)=frac{k+1}{k+1+ell}{k+2ellchooseell}$$ paths to state $kgeq0$ in $k+2ell$ steps that never pass the $k$'th state. This is equivalent to the amount of ways to move to state $k+1$ for the first time after $k+1+2ell$ steps. By substitution and simple probability, we get a $$frac{k}{k+ell}{k-1+2ellchooseell}p^{k+ell}q^{ell}$$ probability of reaching state $k$ for the first time after $k+2ell$ steps.
We can prove our formula for $f$ by induction. For $ell=0$ the answer is obviously $1$, which coincides with the given formula. For $k=-1$ the answer is obviously $0$, which also coincides with the given formula. For $ell>0$ and $kgeq0$ we have two options for the first move: right or left. If we go left, there are $f(k+1,ell-1)$ options, and if we go right there are $f(k-1,ell)$ options. Hence, in total we have
begin{align}
f(k+1,ell-1)+f(k-1,ell)
&=frac{k+2}{k+2+ell-1}{k+1+2(ell-1)chooseell-1}+frac{k}{k+ell}{k-1+2ellchooseell}
\&=frac{(k+2)(k+2ell-1)!}{(k+ell+1)(ell-1)!(k+ell)!}+frac{k(k+2ell-1)!}{(k+ell)ell!(k+ell-1)!}
\&=frac{(k+2)(k+2ell-1)!}{(ell-1)!(k+ell+1)!}+frac{k(k+2ell-1)!}{ell!(k+ell)!}
\&=frac{ell(k+2)(k+2ell-1)!}{ell!(k+ell+1)!}+frac{(k+ell+1)k(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(ell(k+2)+(k+ell+1)k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell k+2ell+k^2+k)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(2ell+k)(k+1)(k+2ell-1)!}{ell!(k+ell+1)!}
\&=frac{(k+1)(k+2ell)!}{ell!(k+ell+1)!}
\&=f(k,ell)
end{align}
options. By principle of induction, this proves the correctness of the formula for $f$.
Now admittedly, even though this solves the problem, it is not a nice solution. I found the formula by simply experimenting for half an hour, and the proof is very algebraic and not very nice to look at. If someone comes up with a combinatorical proof, that would be much better! I am certainly going to think about it now.
answered Dec 16 '18 at 20:40
SmileyCraftSmileyCraft
3,709519
3,709519
$begingroup$
I see, thanks. Can you briefly explain how you came up with this formula via experimentation? What was your approach to first discover it?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:11
2
$begingroup$
I took a fixed $ell$ and I expected the formula would be a polynomial of degree $ell-1$, so simply finding $ell$ terms determines the polynomial. The first few polynomials were $1$; $k+1$; $(k+1)(k+4)/2$; $(k+1)(k+5)(k+6)/6$; $(k+1)(k+6)(k+7)(k+8)/24$. At this point I found the pattern and I got the formula.
$endgroup$
– SmileyCraft
Dec 16 '18 at 21:14
$begingroup$
Sorry, one last thing I haven't understood - why didn't you just call the probability $f(k,l) p^{k+l}q^l$? Instead, you wrote it as $f(k-1,l) p^{k+l} q^l$.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:52
1
$begingroup$
To go to state $k$ for the first time after $k+2ell$ steps means to go to state $k-1$ after $k-1+2ell$ steps without going past state $k-1$ and then going right.
$endgroup$
– SmileyCraft
Dec 16 '18 at 22:09
$begingroup$
Ahh, without going past being they key. Got it, thanks again! Impressive solution.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 22:12
|
show 1 more comment
$begingroup$
I see, thanks. Can you briefly explain how you came up with this formula via experimentation? What was your approach to first discover it?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:11
2
$begingroup$
I took a fixed $ell$ and I expected the formula would be a polynomial of degree $ell-1$, so simply finding $ell$ terms determines the polynomial. The first few polynomials were $1$; $k+1$; $(k+1)(k+4)/2$; $(k+1)(k+5)(k+6)/6$; $(k+1)(k+6)(k+7)(k+8)/24$. At this point I found the pattern and I got the formula.
$endgroup$
– SmileyCraft
Dec 16 '18 at 21:14
$begingroup$
Sorry, one last thing I haven't understood - why didn't you just call the probability $f(k,l) p^{k+l}q^l$? Instead, you wrote it as $f(k-1,l) p^{k+l} q^l$.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:52
1
$begingroup$
To go to state $k$ for the first time after $k+2ell$ steps means to go to state $k-1$ after $k-1+2ell$ steps without going past state $k-1$ and then going right.
$endgroup$
– SmileyCraft
Dec 16 '18 at 22:09
$begingroup$
Ahh, without going past being they key. Got it, thanks again! Impressive solution.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 22:12
$begingroup$
I see, thanks. Can you briefly explain how you came up with this formula via experimentation? What was your approach to first discover it?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:11
$begingroup$
I see, thanks. Can you briefly explain how you came up with this formula via experimentation? What was your approach to first discover it?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:11
2
2
$begingroup$
I took a fixed $ell$ and I expected the formula would be a polynomial of degree $ell-1$, so simply finding $ell$ terms determines the polynomial. The first few polynomials were $1$; $k+1$; $(k+1)(k+4)/2$; $(k+1)(k+5)(k+6)/6$; $(k+1)(k+6)(k+7)(k+8)/24$. At this point I found the pattern and I got the formula.
$endgroup$
– SmileyCraft
Dec 16 '18 at 21:14
$begingroup$
I took a fixed $ell$ and I expected the formula would be a polynomial of degree $ell-1$, so simply finding $ell$ terms determines the polynomial. The first few polynomials were $1$; $k+1$; $(k+1)(k+4)/2$; $(k+1)(k+5)(k+6)/6$; $(k+1)(k+6)(k+7)(k+8)/24$. At this point I found the pattern and I got the formula.
$endgroup$
– SmileyCraft
Dec 16 '18 at 21:14
$begingroup$
Sorry, one last thing I haven't understood - why didn't you just call the probability $f(k,l) p^{k+l}q^l$? Instead, you wrote it as $f(k-1,l) p^{k+l} q^l$.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:52
$begingroup$
Sorry, one last thing I haven't understood - why didn't you just call the probability $f(k,l) p^{k+l}q^l$? Instead, you wrote it as $f(k-1,l) p^{k+l} q^l$.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 21:52
1
1
$begingroup$
To go to state $k$ for the first time after $k+2ell$ steps means to go to state $k-1$ after $k-1+2ell$ steps without going past state $k-1$ and then going right.
$endgroup$
– SmileyCraft
Dec 16 '18 at 22:09
$begingroup$
To go to state $k$ for the first time after $k+2ell$ steps means to go to state $k-1$ after $k-1+2ell$ steps without going past state $k-1$ and then going right.
$endgroup$
– SmileyCraft
Dec 16 '18 at 22:09
$begingroup$
Ahh, without going past being they key. Got it, thanks again! Impressive solution.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 22:12
$begingroup$
Ahh, without going past being they key. Got it, thanks again! Impressive solution.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 22:12
|
show 1 more comment
$begingroup$
This answer is an extension to the one by @SmileyCraft. As he says in his answer, it would be nice to have a combinatorial proof. I might have found one. The problem seems similar in spirit to the one where you have a square grid, start at the bottom left corner and need to get to the top-right corner and find the number of paths where you don't cross the main diagonal of the grid (ok to touch it). In that instance, the number of such paths is the catalan numbers.
$$C_n = frac{2n choose n}{n+1} = {2n choose n} - {2n choose n-1}$$
Now, taking a cue from this, the formula @SmileyCraft has above can also be written as:
$$f(k,l) = frac{k+1}{k+1+l} {k+2l choose l} = {k+2l choose l} - {k+2l choose l-1} tag{1}$$
Now, the problem here for the random walk not crossing $k$ can be converted to a grid problem. We basically have (per @SmileyCraft's convention) $l$ tails and $l+k$ heads and need to arrange them in such a way as to never cross the $k$. This is completely equivalent to saying we'll go right if we get a tails and up if we get a heads on a grid which has $l+k$ rows and $l$ columns.
Another way to see this is to plot on the x-axis the toss number and on the y-axis the score of the random walk. Now, imagine any path going from $(0,0)$ to $(k+2l,k)$. Now, simply rotate the whole picture by 45 degrees and you'll get the grid.
So the formula for $f(k,l)$ above is simply the number of ways to go from the bottom left to top right of a grid with $l$ rows and $l+k$ columns in such a way that the path never crosses the line $y=x+k$.
But how do we show that is equivalent to equation (1) above? I cheated and used the same reasoning as the answer by @Marcus M here. It goes like this:
We know the total paths in our grid are $k+2l choose l$.
The good paths are ones that never cross the line $y=x+k$. Then,
# good paths = # paths - # bad paths
Now, any bad path does cross the line $y=x+k$. So, it must touch the line $y=x+k+1$ (the diagonal just above it).
Divide any such path into two portions. The portion from the origin to when it touches the $y=x+k+1$ line and the portion after that. The first portion can be reflected about the $y=x+k+1$. And this leads to a bijection to a path from $(-(k+1),(k+1))$ to $(l,k+l)$. So, the bad paths can be mapped to paths from the bottom left to top-right of another grid whose height is $(k+l)-(k+1)=l-1$. But we didn't change the total path length, so the total length of the bad paths is still $k+2l$. Hence, the number of bad paths is $k+2l choose l-1$.
Putting all of this together, we get equation (1) above. The picture below shows this for $k=3$ and $t=2$.
$endgroup$
1
$begingroup$
I believe you are confusing your lefts and rights somewhere, but I get the proof and it is very satisfying :)
$endgroup$
– SmileyCraft
Dec 18 '18 at 16:55
$begingroup$
Yes, I did have left and right mixed up in one place. Fixed that - thanks!
$endgroup$
– Rohit Pandey
Dec 18 '18 at 20:47
add a comment |
$begingroup$
This answer is an extension to the one by @SmileyCraft. As he says in his answer, it would be nice to have a combinatorial proof. I might have found one. The problem seems similar in spirit to the one where you have a square grid, start at the bottom left corner and need to get to the top-right corner and find the number of paths where you don't cross the main diagonal of the grid (ok to touch it). In that instance, the number of such paths is the catalan numbers.
$$C_n = frac{2n choose n}{n+1} = {2n choose n} - {2n choose n-1}$$
Now, taking a cue from this, the formula @SmileyCraft has above can also be written as:
$$f(k,l) = frac{k+1}{k+1+l} {k+2l choose l} = {k+2l choose l} - {k+2l choose l-1} tag{1}$$
Now, the problem here for the random walk not crossing $k$ can be converted to a grid problem. We basically have (per @SmileyCraft's convention) $l$ tails and $l+k$ heads and need to arrange them in such a way as to never cross the $k$. This is completely equivalent to saying we'll go right if we get a tails and up if we get a heads on a grid which has $l+k$ rows and $l$ columns.
Another way to see this is to plot on the x-axis the toss number and on the y-axis the score of the random walk. Now, imagine any path going from $(0,0)$ to $(k+2l,k)$. Now, simply rotate the whole picture by 45 degrees and you'll get the grid.
So the formula for $f(k,l)$ above is simply the number of ways to go from the bottom left to top right of a grid with $l$ rows and $l+k$ columns in such a way that the path never crosses the line $y=x+k$.
But how do we show that is equivalent to equation (1) above? I cheated and used the same reasoning as the answer by @Marcus M here. It goes like this:
We know the total paths in our grid are $k+2l choose l$.
The good paths are ones that never cross the line $y=x+k$. Then,
# good paths = # paths - # bad paths
Now, any bad path does cross the line $y=x+k$. So, it must touch the line $y=x+k+1$ (the diagonal just above it).
Divide any such path into two portions. The portion from the origin to when it touches the $y=x+k+1$ line and the portion after that. The first portion can be reflected about the $y=x+k+1$. And this leads to a bijection to a path from $(-(k+1),(k+1))$ to $(l,k+l)$. So, the bad paths can be mapped to paths from the bottom left to top-right of another grid whose height is $(k+l)-(k+1)=l-1$. But we didn't change the total path length, so the total length of the bad paths is still $k+2l$. Hence, the number of bad paths is $k+2l choose l-1$.
Putting all of this together, we get equation (1) above. The picture below shows this for $k=3$ and $t=2$.
$endgroup$
1
$begingroup$
I believe you are confusing your lefts and rights somewhere, but I get the proof and it is very satisfying :)
$endgroup$
– SmileyCraft
Dec 18 '18 at 16:55
$begingroup$
Yes, I did have left and right mixed up in one place. Fixed that - thanks!
$endgroup$
– Rohit Pandey
Dec 18 '18 at 20:47
add a comment |
$begingroup$
This answer is an extension to the one by @SmileyCraft. As he says in his answer, it would be nice to have a combinatorial proof. I might have found one. The problem seems similar in spirit to the one where you have a square grid, start at the bottom left corner and need to get to the top-right corner and find the number of paths where you don't cross the main diagonal of the grid (ok to touch it). In that instance, the number of such paths is the catalan numbers.
$$C_n = frac{2n choose n}{n+1} = {2n choose n} - {2n choose n-1}$$
Now, taking a cue from this, the formula @SmileyCraft has above can also be written as:
$$f(k,l) = frac{k+1}{k+1+l} {k+2l choose l} = {k+2l choose l} - {k+2l choose l-1} tag{1}$$
Now, the problem here for the random walk not crossing $k$ can be converted to a grid problem. We basically have (per @SmileyCraft's convention) $l$ tails and $l+k$ heads and need to arrange them in such a way as to never cross the $k$. This is completely equivalent to saying we'll go right if we get a tails and up if we get a heads on a grid which has $l+k$ rows and $l$ columns.
Another way to see this is to plot on the x-axis the toss number and on the y-axis the score of the random walk. Now, imagine any path going from $(0,0)$ to $(k+2l,k)$. Now, simply rotate the whole picture by 45 degrees and you'll get the grid.
So the formula for $f(k,l)$ above is simply the number of ways to go from the bottom left to top right of a grid with $l$ rows and $l+k$ columns in such a way that the path never crosses the line $y=x+k$.
But how do we show that is equivalent to equation (1) above? I cheated and used the same reasoning as the answer by @Marcus M here. It goes like this:
We know the total paths in our grid are $k+2l choose l$.
The good paths are ones that never cross the line $y=x+k$. Then,
# good paths = # paths - # bad paths
Now, any bad path does cross the line $y=x+k$. So, it must touch the line $y=x+k+1$ (the diagonal just above it).
Divide any such path into two portions. The portion from the origin to when it touches the $y=x+k+1$ line and the portion after that. The first portion can be reflected about the $y=x+k+1$. And this leads to a bijection to a path from $(-(k+1),(k+1))$ to $(l,k+l)$. So, the bad paths can be mapped to paths from the bottom left to top-right of another grid whose height is $(k+l)-(k+1)=l-1$. But we didn't change the total path length, so the total length of the bad paths is still $k+2l$. Hence, the number of bad paths is $k+2l choose l-1$.
Putting all of this together, we get equation (1) above. The picture below shows this for $k=3$ and $t=2$.
$endgroup$
This answer is an extension to the one by @SmileyCraft. As he says in his answer, it would be nice to have a combinatorial proof. I might have found one. The problem seems similar in spirit to the one where you have a square grid, start at the bottom left corner and need to get to the top-right corner and find the number of paths where you don't cross the main diagonal of the grid (ok to touch it). In that instance, the number of such paths is the catalan numbers.
$$C_n = frac{2n choose n}{n+1} = {2n choose n} - {2n choose n-1}$$
Now, taking a cue from this, the formula @SmileyCraft has above can also be written as:
$$f(k,l) = frac{k+1}{k+1+l} {k+2l choose l} = {k+2l choose l} - {k+2l choose l-1} tag{1}$$
Now, the problem here for the random walk not crossing $k$ can be converted to a grid problem. We basically have (per @SmileyCraft's convention) $l$ tails and $l+k$ heads and need to arrange them in such a way as to never cross the $k$. This is completely equivalent to saying we'll go right if we get a tails and up if we get a heads on a grid which has $l+k$ rows and $l$ columns.
Another way to see this is to plot on the x-axis the toss number and on the y-axis the score of the random walk. Now, imagine any path going from $(0,0)$ to $(k+2l,k)$. Now, simply rotate the whole picture by 45 degrees and you'll get the grid.
So the formula for $f(k,l)$ above is simply the number of ways to go from the bottom left to top right of a grid with $l$ rows and $l+k$ columns in such a way that the path never crosses the line $y=x+k$.
But how do we show that is equivalent to equation (1) above? I cheated and used the same reasoning as the answer by @Marcus M here. It goes like this:
We know the total paths in our grid are $k+2l choose l$.
The good paths are ones that never cross the line $y=x+k$. Then,
# good paths = # paths - # bad paths
Now, any bad path does cross the line $y=x+k$. So, it must touch the line $y=x+k+1$ (the diagonal just above it).
Divide any such path into two portions. The portion from the origin to when it touches the $y=x+k+1$ line and the portion after that. The first portion can be reflected about the $y=x+k+1$. And this leads to a bijection to a path from $(-(k+1),(k+1))$ to $(l,k+l)$. So, the bad paths can be mapped to paths from the bottom left to top-right of another grid whose height is $(k+l)-(k+1)=l-1$. But we didn't change the total path length, so the total length of the bad paths is still $k+2l$. Hence, the number of bad paths is $k+2l choose l-1$.
Putting all of this together, we get equation (1) above. The picture below shows this for $k=3$ and $t=2$.
edited Feb 3 at 6:47
answered Dec 18 '18 at 2:27
Rohit PandeyRohit Pandey
1,4901023
1,4901023
1
$begingroup$
I believe you are confusing your lefts and rights somewhere, but I get the proof and it is very satisfying :)
$endgroup$
– SmileyCraft
Dec 18 '18 at 16:55
$begingroup$
Yes, I did have left and right mixed up in one place. Fixed that - thanks!
$endgroup$
– Rohit Pandey
Dec 18 '18 at 20:47
add a comment |
1
$begingroup$
I believe you are confusing your lefts and rights somewhere, but I get the proof and it is very satisfying :)
$endgroup$
– SmileyCraft
Dec 18 '18 at 16:55
$begingroup$
Yes, I did have left and right mixed up in one place. Fixed that - thanks!
$endgroup$
– Rohit Pandey
Dec 18 '18 at 20:47
1
1
$begingroup$
I believe you are confusing your lefts and rights somewhere, but I get the proof and it is very satisfying :)
$endgroup$
– SmileyCraft
Dec 18 '18 at 16:55
$begingroup$
I believe you are confusing your lefts and rights somewhere, but I get the proof and it is very satisfying :)
$endgroup$
– SmileyCraft
Dec 18 '18 at 16:55
$begingroup$
Yes, I did have left and right mixed up in one place. Fixed that - thanks!
$endgroup$
– Rohit Pandey
Dec 18 '18 at 20:47
$begingroup$
Yes, I did have left and right mixed up in one place. Fixed that - thanks!
$endgroup$
– Rohit Pandey
Dec 18 '18 at 20:47
add a comment |
$begingroup$
A Generating Function
Let the number of ways for getting to position $s$ for the first time on step $n$ be $a_{s,n}$. The number of unilateral walks of length $2k$ is $frac1{k+1}binom{2k}{k}$, with generating function $frac{1-sqrt{1-4x}}{2x}$. To first get to position $s$ on step $n$, we can count the number of ways to first get to position $s-1$ in $n-2k-1$ steps times the number of unilateral walks of length $2k$ and sum for all $k$. That is,
$$
a_{s,n}=sum_{k=0}^inftyfrac1{k+1}binom{2k}{k},a_{s-1,n-2k-1}tag1
$$
If we set the generating function
$$
f_s(x)=sum_{n=0}^infty a_{s,n}x^ntag2
$$
then $(1)$ implies
$$
f_s(x)=f_{s-1}(x)left(frac{1-sqrt{1-4x^2}}{2x}right)tag3
$$
and since $f_0(x)=1$, induction yields
$$
bbox[5px,border:2px solid #C0A000]{f_s(x)=left(frac{1-sqrt{1-4x^2}}{2x}right)^{large s}}tag4
$$
Therefore, if the probability of a '$+1$' step is $p$ and of a '$-1$' step is $1-p$, then the probability of $frac{n+s}2$ '$+1$' steps and $frac{n-s}2$ '$-1$' steps is $a_{s,n}p^{frac{n+s}2}(1-p)^{frac{n-s}2}=left(frac{p}{1-p}right)^{s/2}a_{s,n}(p(1-p))^{n/2}$. Summing over $n$ gives the probability of getting to position $s$ at all to be
$$
begin{align}
left(frac{p}{1-p}right)^{s/2}f_s!left(sqrt{p(1-p)}right)
&=left(frac{1-|1-2p|}{2(1-p)}right)^{large s}\[3pt]
&=left{begin{array}{}left(frac{p}{1-p}right)^s&text{if }pltfrac12\1&text{if }pgefrac12end{array}right.tag5
end{align}
$$
A Closed Form
To derive a closed form for $a_{s,n}$, we first consider the series
$$
sum_{n=0}^infty b_{s,n}x^n=left(frac{1-sqrt{1-4x}}{2x}right)^{large s}tag6
$$
where, comparing $(4)$ and $(6)$, we get
$$
begin{align}
a_{s,s+2n}&=b_{s,n}\
a_{s,s+2n+1}&=0
end{align}tag7
$$
Using the fact that
$$
left(frac{1-sqrt{1-4x}}{2x}right)^2=frac1xfrac{1-sqrt{1-4x}}{2x}-frac1xtag8
$$
we get the relation
$$
b_{s,n}=b_{s-1,n+1}-b_{s-2,n+1}tag9
$$
We know that
$$
begin{align}
b_{0,n}&=[n=0]\[3pt]
b_{1,n}&=frac1{n+1}binom{2n}{n}=binom{2n}{n}-binom{2n}{n-1}
end{align}tag{10}
$$
which implies that
$$
begin{align}
b_{2,n}&=frac1{n+2}binom{2n+2}{n+1}=binom{2n+1}{n}-binom{2n+1}{n-1}tag{11}\[6pt]
b_{3,n}&=frac1{n+3}binom{2n+4}{n+2}-frac1{n+2}binom{2n+2}{n+1}
=binom{2n+2}{n}-binom{2n+2}{n-1}tag{12}
end{align}
$$
A pattern is appearing; that is,
$$
begin{align}
b_{s,n}
&=binom{2n+s-1}{n}-binom{2n+s-1}{n-1}\[3pt]
&=frac{s}{2n+s}binom{2n+s}{n}tag{13}
end{align}
$$
which satisfies $(9)$ using Pascal's Formula. Therefore, applying $(7)$ yields
$$
bbox[5px,border:2px solid #C0A000]{a_{s,n}=left{begin{array}{}
frac snbinom{n}{(n-s)/2}=binom{n-1}{(n-s)/2}-binom{n-1}{(n-s-2)/2}&text{if }2mid n-s\
0&text{if }2nmid n-s
end{array}right.}tag{14}
$$
$endgroup$
$begingroup$
In equation (2), should the index be on $n$ instead of $k$?
$endgroup$
– Rohit Pandey
Jan 20 at 18:54
$begingroup$
Very beautiful proof. To get an actual expression for $a_{s,n}$, we can use (5.70) here (in conjunction with equation (4)): math.stackexchange.com/questions/3064256/…. This identity isn't super easy to prove, but it gets one there.
$endgroup$
– Rohit Pandey
Jan 20 at 19:39
$begingroup$
@RohitPandey: Indeed. I am working on more for the answer. As soon as I post that, the correction will be there.
$endgroup$
– robjohn♦
Jan 20 at 23:27
1
$begingroup$
@RohitPandey: I have added a derivation of the closed form as well.
$endgroup$
– robjohn♦
Jan 21 at 19:07
$begingroup$
Thanks a lot, reading through. In the meantime, I'm writing a paper on how races of wealthy gamblers can be used to estimate $pi$. I think this provides a method that converges to $pi$ reasonably fast and has a nice interpretation as well. I'll be done with the first draft very soon. Would love to have you as a co-author since your answers have helped a lot with the effort. Let me know if you're fine with it. If not, is it OK to cite your answers in it?
$endgroup$
– Rohit Pandey
Jan 21 at 19:56
|
show 2 more comments
$begingroup$
A Generating Function
Let the number of ways for getting to position $s$ for the first time on step $n$ be $a_{s,n}$. The number of unilateral walks of length $2k$ is $frac1{k+1}binom{2k}{k}$, with generating function $frac{1-sqrt{1-4x}}{2x}$. To first get to position $s$ on step $n$, we can count the number of ways to first get to position $s-1$ in $n-2k-1$ steps times the number of unilateral walks of length $2k$ and sum for all $k$. That is,
$$
a_{s,n}=sum_{k=0}^inftyfrac1{k+1}binom{2k}{k},a_{s-1,n-2k-1}tag1
$$
If we set the generating function
$$
f_s(x)=sum_{n=0}^infty a_{s,n}x^ntag2
$$
then $(1)$ implies
$$
f_s(x)=f_{s-1}(x)left(frac{1-sqrt{1-4x^2}}{2x}right)tag3
$$
and since $f_0(x)=1$, induction yields
$$
bbox[5px,border:2px solid #C0A000]{f_s(x)=left(frac{1-sqrt{1-4x^2}}{2x}right)^{large s}}tag4
$$
Therefore, if the probability of a '$+1$' step is $p$ and of a '$-1$' step is $1-p$, then the probability of $frac{n+s}2$ '$+1$' steps and $frac{n-s}2$ '$-1$' steps is $a_{s,n}p^{frac{n+s}2}(1-p)^{frac{n-s}2}=left(frac{p}{1-p}right)^{s/2}a_{s,n}(p(1-p))^{n/2}$. Summing over $n$ gives the probability of getting to position $s$ at all to be
$$
begin{align}
left(frac{p}{1-p}right)^{s/2}f_s!left(sqrt{p(1-p)}right)
&=left(frac{1-|1-2p|}{2(1-p)}right)^{large s}\[3pt]
&=left{begin{array}{}left(frac{p}{1-p}right)^s&text{if }pltfrac12\1&text{if }pgefrac12end{array}right.tag5
end{align}
$$
A Closed Form
To derive a closed form for $a_{s,n}$, we first consider the series
$$
sum_{n=0}^infty b_{s,n}x^n=left(frac{1-sqrt{1-4x}}{2x}right)^{large s}tag6
$$
where, comparing $(4)$ and $(6)$, we get
$$
begin{align}
a_{s,s+2n}&=b_{s,n}\
a_{s,s+2n+1}&=0
end{align}tag7
$$
Using the fact that
$$
left(frac{1-sqrt{1-4x}}{2x}right)^2=frac1xfrac{1-sqrt{1-4x}}{2x}-frac1xtag8
$$
we get the relation
$$
b_{s,n}=b_{s-1,n+1}-b_{s-2,n+1}tag9
$$
We know that
$$
begin{align}
b_{0,n}&=[n=0]\[3pt]
b_{1,n}&=frac1{n+1}binom{2n}{n}=binom{2n}{n}-binom{2n}{n-1}
end{align}tag{10}
$$
which implies that
$$
begin{align}
b_{2,n}&=frac1{n+2}binom{2n+2}{n+1}=binom{2n+1}{n}-binom{2n+1}{n-1}tag{11}\[6pt]
b_{3,n}&=frac1{n+3}binom{2n+4}{n+2}-frac1{n+2}binom{2n+2}{n+1}
=binom{2n+2}{n}-binom{2n+2}{n-1}tag{12}
end{align}
$$
A pattern is appearing; that is,
$$
begin{align}
b_{s,n}
&=binom{2n+s-1}{n}-binom{2n+s-1}{n-1}\[3pt]
&=frac{s}{2n+s}binom{2n+s}{n}tag{13}
end{align}
$$
which satisfies $(9)$ using Pascal's Formula. Therefore, applying $(7)$ yields
$$
bbox[5px,border:2px solid #C0A000]{a_{s,n}=left{begin{array}{}
frac snbinom{n}{(n-s)/2}=binom{n-1}{(n-s)/2}-binom{n-1}{(n-s-2)/2}&text{if }2mid n-s\
0&text{if }2nmid n-s
end{array}right.}tag{14}
$$
$endgroup$
$begingroup$
In equation (2), should the index be on $n$ instead of $k$?
$endgroup$
– Rohit Pandey
Jan 20 at 18:54
$begingroup$
Very beautiful proof. To get an actual expression for $a_{s,n}$, we can use (5.70) here (in conjunction with equation (4)): math.stackexchange.com/questions/3064256/…. This identity isn't super easy to prove, but it gets one there.
$endgroup$
– Rohit Pandey
Jan 20 at 19:39
$begingroup$
@RohitPandey: Indeed. I am working on more for the answer. As soon as I post that, the correction will be there.
$endgroup$
– robjohn♦
Jan 20 at 23:27
1
$begingroup$
@RohitPandey: I have added a derivation of the closed form as well.
$endgroup$
– robjohn♦
Jan 21 at 19:07
$begingroup$
Thanks a lot, reading through. In the meantime, I'm writing a paper on how races of wealthy gamblers can be used to estimate $pi$. I think this provides a method that converges to $pi$ reasonably fast and has a nice interpretation as well. I'll be done with the first draft very soon. Would love to have you as a co-author since your answers have helped a lot with the effort. Let me know if you're fine with it. If not, is it OK to cite your answers in it?
$endgroup$
– Rohit Pandey
Jan 21 at 19:56
|
show 2 more comments
$begingroup$
A Generating Function
Let the number of ways for getting to position $s$ for the first time on step $n$ be $a_{s,n}$. The number of unilateral walks of length $2k$ is $frac1{k+1}binom{2k}{k}$, with generating function $frac{1-sqrt{1-4x}}{2x}$. To first get to position $s$ on step $n$, we can count the number of ways to first get to position $s-1$ in $n-2k-1$ steps times the number of unilateral walks of length $2k$ and sum for all $k$. That is,
$$
a_{s,n}=sum_{k=0}^inftyfrac1{k+1}binom{2k}{k},a_{s-1,n-2k-1}tag1
$$
If we set the generating function
$$
f_s(x)=sum_{n=0}^infty a_{s,n}x^ntag2
$$
then $(1)$ implies
$$
f_s(x)=f_{s-1}(x)left(frac{1-sqrt{1-4x^2}}{2x}right)tag3
$$
and since $f_0(x)=1$, induction yields
$$
bbox[5px,border:2px solid #C0A000]{f_s(x)=left(frac{1-sqrt{1-4x^2}}{2x}right)^{large s}}tag4
$$
Therefore, if the probability of a '$+1$' step is $p$ and of a '$-1$' step is $1-p$, then the probability of $frac{n+s}2$ '$+1$' steps and $frac{n-s}2$ '$-1$' steps is $a_{s,n}p^{frac{n+s}2}(1-p)^{frac{n-s}2}=left(frac{p}{1-p}right)^{s/2}a_{s,n}(p(1-p))^{n/2}$. Summing over $n$ gives the probability of getting to position $s$ at all to be
$$
begin{align}
left(frac{p}{1-p}right)^{s/2}f_s!left(sqrt{p(1-p)}right)
&=left(frac{1-|1-2p|}{2(1-p)}right)^{large s}\[3pt]
&=left{begin{array}{}left(frac{p}{1-p}right)^s&text{if }pltfrac12\1&text{if }pgefrac12end{array}right.tag5
end{align}
$$
A Closed Form
To derive a closed form for $a_{s,n}$, we first consider the series
$$
sum_{n=0}^infty b_{s,n}x^n=left(frac{1-sqrt{1-4x}}{2x}right)^{large s}tag6
$$
where, comparing $(4)$ and $(6)$, we get
$$
begin{align}
a_{s,s+2n}&=b_{s,n}\
a_{s,s+2n+1}&=0
end{align}tag7
$$
Using the fact that
$$
left(frac{1-sqrt{1-4x}}{2x}right)^2=frac1xfrac{1-sqrt{1-4x}}{2x}-frac1xtag8
$$
we get the relation
$$
b_{s,n}=b_{s-1,n+1}-b_{s-2,n+1}tag9
$$
We know that
$$
begin{align}
b_{0,n}&=[n=0]\[3pt]
b_{1,n}&=frac1{n+1}binom{2n}{n}=binom{2n}{n}-binom{2n}{n-1}
end{align}tag{10}
$$
which implies that
$$
begin{align}
b_{2,n}&=frac1{n+2}binom{2n+2}{n+1}=binom{2n+1}{n}-binom{2n+1}{n-1}tag{11}\[6pt]
b_{3,n}&=frac1{n+3}binom{2n+4}{n+2}-frac1{n+2}binom{2n+2}{n+1}
=binom{2n+2}{n}-binom{2n+2}{n-1}tag{12}
end{align}
$$
A pattern is appearing; that is,
$$
begin{align}
b_{s,n}
&=binom{2n+s-1}{n}-binom{2n+s-1}{n-1}\[3pt]
&=frac{s}{2n+s}binom{2n+s}{n}tag{13}
end{align}
$$
which satisfies $(9)$ using Pascal's Formula. Therefore, applying $(7)$ yields
$$
bbox[5px,border:2px solid #C0A000]{a_{s,n}=left{begin{array}{}
frac snbinom{n}{(n-s)/2}=binom{n-1}{(n-s)/2}-binom{n-1}{(n-s-2)/2}&text{if }2mid n-s\
0&text{if }2nmid n-s
end{array}right.}tag{14}
$$
$endgroup$
A Generating Function
Let the number of ways for getting to position $s$ for the first time on step $n$ be $a_{s,n}$. The number of unilateral walks of length $2k$ is $frac1{k+1}binom{2k}{k}$, with generating function $frac{1-sqrt{1-4x}}{2x}$. To first get to position $s$ on step $n$, we can count the number of ways to first get to position $s-1$ in $n-2k-1$ steps times the number of unilateral walks of length $2k$ and sum for all $k$. That is,
$$
a_{s,n}=sum_{k=0}^inftyfrac1{k+1}binom{2k}{k},a_{s-1,n-2k-1}tag1
$$
If we set the generating function
$$
f_s(x)=sum_{n=0}^infty a_{s,n}x^ntag2
$$
then $(1)$ implies
$$
f_s(x)=f_{s-1}(x)left(frac{1-sqrt{1-4x^2}}{2x}right)tag3
$$
and since $f_0(x)=1$, induction yields
$$
bbox[5px,border:2px solid #C0A000]{f_s(x)=left(frac{1-sqrt{1-4x^2}}{2x}right)^{large s}}tag4
$$
Therefore, if the probability of a '$+1$' step is $p$ and of a '$-1$' step is $1-p$, then the probability of $frac{n+s}2$ '$+1$' steps and $frac{n-s}2$ '$-1$' steps is $a_{s,n}p^{frac{n+s}2}(1-p)^{frac{n-s}2}=left(frac{p}{1-p}right)^{s/2}a_{s,n}(p(1-p))^{n/2}$. Summing over $n$ gives the probability of getting to position $s$ at all to be
$$
begin{align}
left(frac{p}{1-p}right)^{s/2}f_s!left(sqrt{p(1-p)}right)
&=left(frac{1-|1-2p|}{2(1-p)}right)^{large s}\[3pt]
&=left{begin{array}{}left(frac{p}{1-p}right)^s&text{if }pltfrac12\1&text{if }pgefrac12end{array}right.tag5
end{align}
$$
A Closed Form
To derive a closed form for $a_{s,n}$, we first consider the series
$$
sum_{n=0}^infty b_{s,n}x^n=left(frac{1-sqrt{1-4x}}{2x}right)^{large s}tag6
$$
where, comparing $(4)$ and $(6)$, we get
$$
begin{align}
a_{s,s+2n}&=b_{s,n}\
a_{s,s+2n+1}&=0
end{align}tag7
$$
Using the fact that
$$
left(frac{1-sqrt{1-4x}}{2x}right)^2=frac1xfrac{1-sqrt{1-4x}}{2x}-frac1xtag8
$$
we get the relation
$$
b_{s,n}=b_{s-1,n+1}-b_{s-2,n+1}tag9
$$
We know that
$$
begin{align}
b_{0,n}&=[n=0]\[3pt]
b_{1,n}&=frac1{n+1}binom{2n}{n}=binom{2n}{n}-binom{2n}{n-1}
end{align}tag{10}
$$
which implies that
$$
begin{align}
b_{2,n}&=frac1{n+2}binom{2n+2}{n+1}=binom{2n+1}{n}-binom{2n+1}{n-1}tag{11}\[6pt]
b_{3,n}&=frac1{n+3}binom{2n+4}{n+2}-frac1{n+2}binom{2n+2}{n+1}
=binom{2n+2}{n}-binom{2n+2}{n-1}tag{12}
end{align}
$$
A pattern is appearing; that is,
$$
begin{align}
b_{s,n}
&=binom{2n+s-1}{n}-binom{2n+s-1}{n-1}\[3pt]
&=frac{s}{2n+s}binom{2n+s}{n}tag{13}
end{align}
$$
which satisfies $(9)$ using Pascal's Formula. Therefore, applying $(7)$ yields
$$
bbox[5px,border:2px solid #C0A000]{a_{s,n}=left{begin{array}{}
frac snbinom{n}{(n-s)/2}=binom{n-1}{(n-s)/2}-binom{n-1}{(n-s-2)/2}&text{if }2mid n-s\
0&text{if }2nmid n-s
end{array}right.}tag{14}
$$
edited Jan 21 at 20:01
answered Jan 20 at 15:27
robjohn♦robjohn
269k27311638
269k27311638
$begingroup$
In equation (2), should the index be on $n$ instead of $k$?
$endgroup$
– Rohit Pandey
Jan 20 at 18:54
$begingroup$
Very beautiful proof. To get an actual expression for $a_{s,n}$, we can use (5.70) here (in conjunction with equation (4)): math.stackexchange.com/questions/3064256/…. This identity isn't super easy to prove, but it gets one there.
$endgroup$
– Rohit Pandey
Jan 20 at 19:39
$begingroup$
@RohitPandey: Indeed. I am working on more for the answer. As soon as I post that, the correction will be there.
$endgroup$
– robjohn♦
Jan 20 at 23:27
1
$begingroup$
@RohitPandey: I have added a derivation of the closed form as well.
$endgroup$
– robjohn♦
Jan 21 at 19:07
$begingroup$
Thanks a lot, reading through. In the meantime, I'm writing a paper on how races of wealthy gamblers can be used to estimate $pi$. I think this provides a method that converges to $pi$ reasonably fast and has a nice interpretation as well. I'll be done with the first draft very soon. Would love to have you as a co-author since your answers have helped a lot with the effort. Let me know if you're fine with it. If not, is it OK to cite your answers in it?
$endgroup$
– Rohit Pandey
Jan 21 at 19:56
|
show 2 more comments
$begingroup$
In equation (2), should the index be on $n$ instead of $k$?
$endgroup$
– Rohit Pandey
Jan 20 at 18:54
$begingroup$
Very beautiful proof. To get an actual expression for $a_{s,n}$, we can use (5.70) here (in conjunction with equation (4)): math.stackexchange.com/questions/3064256/…. This identity isn't super easy to prove, but it gets one there.
$endgroup$
– Rohit Pandey
Jan 20 at 19:39
$begingroup$
@RohitPandey: Indeed. I am working on more for the answer. As soon as I post that, the correction will be there.
$endgroup$
– robjohn♦
Jan 20 at 23:27
1
$begingroup$
@RohitPandey: I have added a derivation of the closed form as well.
$endgroup$
– robjohn♦
Jan 21 at 19:07
$begingroup$
Thanks a lot, reading through. In the meantime, I'm writing a paper on how races of wealthy gamblers can be used to estimate $pi$. I think this provides a method that converges to $pi$ reasonably fast and has a nice interpretation as well. I'll be done with the first draft very soon. Would love to have you as a co-author since your answers have helped a lot with the effort. Let me know if you're fine with it. If not, is it OK to cite your answers in it?
$endgroup$
– Rohit Pandey
Jan 21 at 19:56
$begingroup$
In equation (2), should the index be on $n$ instead of $k$?
$endgroup$
– Rohit Pandey
Jan 20 at 18:54
$begingroup$
In equation (2), should the index be on $n$ instead of $k$?
$endgroup$
– Rohit Pandey
Jan 20 at 18:54
$begingroup$
Very beautiful proof. To get an actual expression for $a_{s,n}$, we can use (5.70) here (in conjunction with equation (4)): math.stackexchange.com/questions/3064256/…. This identity isn't super easy to prove, but it gets one there.
$endgroup$
– Rohit Pandey
Jan 20 at 19:39
$begingroup$
Very beautiful proof. To get an actual expression for $a_{s,n}$, we can use (5.70) here (in conjunction with equation (4)): math.stackexchange.com/questions/3064256/…. This identity isn't super easy to prove, but it gets one there.
$endgroup$
– Rohit Pandey
Jan 20 at 19:39
$begingroup$
@RohitPandey: Indeed. I am working on more for the answer. As soon as I post that, the correction will be there.
$endgroup$
– robjohn♦
Jan 20 at 23:27
$begingroup$
@RohitPandey: Indeed. I am working on more for the answer. As soon as I post that, the correction will be there.
$endgroup$
– robjohn♦
Jan 20 at 23:27
1
1
$begingroup$
@RohitPandey: I have added a derivation of the closed form as well.
$endgroup$
– robjohn♦
Jan 21 at 19:07
$begingroup$
@RohitPandey: I have added a derivation of the closed form as well.
$endgroup$
– robjohn♦
Jan 21 at 19:07
$begingroup$
Thanks a lot, reading through. In the meantime, I'm writing a paper on how races of wealthy gamblers can be used to estimate $pi$. I think this provides a method that converges to $pi$ reasonably fast and has a nice interpretation as well. I'll be done with the first draft very soon. Would love to have you as a co-author since your answers have helped a lot with the effort. Let me know if you're fine with it. If not, is it OK to cite your answers in it?
$endgroup$
– Rohit Pandey
Jan 21 at 19:56
$begingroup$
Thanks a lot, reading through. In the meantime, I'm writing a paper on how races of wealthy gamblers can be used to estimate $pi$. I think this provides a method that converges to $pi$ reasonably fast and has a nice interpretation as well. I'll be done with the first draft very soon. Would love to have you as a co-author since your answers have helped a lot with the effort. Let me know if you're fine with it. If not, is it OK to cite your answers in it?
$endgroup$
– Rohit Pandey
Jan 21 at 19:56
|
show 2 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3043013%2fprobability-that-random-walk-will-reach-state-k-for-the-first-time-on-step-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Still working on the solution to the question, but I do know why the reasoning at the end is wrong; the probabilities are not independent, so you can not simply subtract them from each other.
$endgroup$
– SmileyCraft
Dec 16 '18 at 19:07
$begingroup$
Appreciate it. Yeah, I suspected as much. That's almost always the reason when you add/subtract probabilities and get something not between 0 and 1. Thought I'd mention it anyway in case it inspired someone to formulate a correct approach based on the idea.
$endgroup$
– Rohit Pandey
Dec 16 '18 at 19:09
$begingroup$
If you reverse time and flip the y axis, you are counting paths which reach k after n steps without ever returning to 0. This is Bertrand’s ballot problem.
$endgroup$
– Mike Earnest
Dec 16 '18 at 20:24
$begingroup$
Don't completely follow. If I reverse time, I start off at $k$, correct? So, doesn't it become paths that reach 0?
$endgroup$
– Rohit Pandey
Dec 16 '18 at 20:33
$begingroup$
@RohitPandey Sorry, when I said "flip the y-axis,", I meant that you interchange $0$ with $k$.
$endgroup$
– Mike Earnest
Dec 17 '18 at 12:49