On the real line place an object at 1. After every flip of a fair coin move the object to the right by 1 unit...
$begingroup$
On the real line place an object at 1. After every flip of a fair coin move the object to the right by 1 unit if the outcome is head and to the left by 1 unit if the outcome is tail.
Let $N$ be a fixed positive integer.Game ends when the object reaches either $0$ or $N$.
What is the probability of the object reaching at $N$, i.e $P(N)$.
Give me some hint..
probability combinatorics
asked Jan 12 at 7:55
Supriyo BanerjeeSupriyo Banerjee
1056
$endgroup$
closed as off-topic by Saad, Arnaud D., Xander Henderson, Did, user21820 Jan 14 at 15:05
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Arnaud D., Xander Henderson, Did, user21820
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
On the real line place an object at 1. After every flip of a fair coin move the object to the right by 1 unit if the outcome is head and to the left by 1 unit if the outcome is tail.
Let $N$ be a fixed positive integer.Game ends when the object reaches either $0$ or $N$.
What is the probability of the object reaching at $N$, i.e $P(N)$.
Give me some hint..
probability combinatorics
asked Jan 12 at 7:55
Supriyo BanerjeeSupriyo Banerjee
1056
$endgroup$
closed as off-topic by Saad, Arnaud D., Xander Henderson, Did, user21820 Jan 14 at 15:05
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Arnaud D., Xander Henderson, Did, user21820
If this question can be reworded to fit the rules in the help center, please edit the question.
1
$begingroup$
This is a case of the famous "gambler's ruin" problem. For this version with a fair game, looking at the probability of reaching one state before another, the easiest approach is to track expected values. OK, where's a good version of this to link to on MSE?
$endgroup$
– jmerry
Jan 12 at 8:08
add a comment |
$begingroup$
On the real line place an object at 1. After every flip of a fair coin move the object to the right by 1 unit if the outcome is head and to the left by 1 unit if the outcome is tail.
Let $N$ be a fixed positive integer.Game ends when the object reaches either $0$ or $N$.
What is the probability of the object reaching at $N$, i.e $P(N)$.
Give me some hint..
probability combinatorics
asked Jan 12 at 7:55
Supriyo BanerjeeSupriyo Banerjee
1056
$endgroup$
On the real line place an object at 1. After every flip of a fair coin move the object to the right by 1 unit if the outcome is head and to the left by 1 unit if the outcome is tail.
Let $N$ be a fixed positive integer.Game ends when the object reaches either $0$ or $N$.
What is the probability of the object reaching at $N$, i.e $P(N)$.
Give me some hint..
probability combinatorics
probability combinatorics
asked Jan 12 at 7:55
Supriyo BanerjeeSupriyo Banerjee
1056
asked Jan 12 at 7:55
Supriyo BanerjeeSupriyo Banerjee
1056
asked Jan 12 at 7:55
Supriyo BanerjeeSupriyo Banerjee
1056
asked Jan 12 at 7:55
Supriyo BanerjeeSupriyo Banerjee
1056
asked Jan 12 at 7:55
Supriyo BanerjeeSupriyo Banerjee
1056
1056
closed as off-topic by Saad, Arnaud D., Xander Henderson, Did, user21820 Jan 14 at 15:05
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Arnaud D., Xander Henderson, Did, user21820
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Saad, Arnaud D., Xander Henderson, Did, user21820 Jan 14 at 15:05
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Arnaud D., Xander Henderson, Did, user21820
If this question can be reworded to fit the rules in the help center, please edit the question.
1
$begingroup$
This is a case of the famous "gambler's ruin" problem. For this version with a fair game, looking at the probability of reaching one state before another, the easiest approach is to track expected values. OK, where's a good version of this to link to on MSE?
$endgroup$
– jmerry
Jan 12 at 8:08
add a comment |
1
$begingroup$
This is a case of the famous "gambler's ruin" problem. For this version with a fair game, looking at the probability of reaching one state before another, the easiest approach is to track expected values. OK, where's a good version of this to link to on MSE?
$endgroup$
– jmerry
Jan 12 at 8:08
1
1
$begingroup$
This is a case of the famous "gambler's ruin" problem. For this version with a fair game, looking at the probability of reaching one state before another, the easiest approach is to track expected values. OK, where's a good version of this to link to on MSE?
$endgroup$
– jmerry
Jan 12 at 8:08
$begingroup$
This is a case of the famous "gambler's ruin" problem. For this version with a fair game, looking at the probability of reaching one state before another, the easiest approach is to track expected values. OK, where's a good version of this to link to on MSE?
$endgroup$
– jmerry
Jan 12 at 8:08
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here is a short proof using induction and symmetry. We use induction on $N$ to show that $P(N) = frac{1}{N}$. For $N = 1$, this is obvious.
Now, suppose that $P(k) = frac{1}{k}$ for $k leq n$. We shall show that the statement holds for $N = n+1$. Note that, in order to reach $n+1$, we must reach $n$. The probability of this is $P(n) = frac{1}{n}$. Now, the probability of reaching $n+1$ when standing on $n$ is the same as the probability of reaching $0$ when standing on $1$, by symmetry. So we get
$$P(n+1) = P(n)(1 - P(n+1)) Leftrightarrow P(n+1) = frac{P(n)}{1+P(n)} = frac{frac{1}{n}}{frac{n+1}{n}} = frac{1}{n+1}$$
So by the principle of induction, $P(N) = frac{1}{N}$ for all positive integers $N$
edited Jan 12 at 9:26
drhab
104k545136
answered Jan 12 at 8:21
nesHannesHan
1785
$endgroup$
$begingroup$
+1 Nice solution.
$endgroup$
– drhab
Jan 12 at 9:26
$begingroup$
Good answer, but you switches from k to n there
$endgroup$
– DreamConspiracy
Jan 12 at 12:56
$begingroup$
Why is the probability of reaching 0 standing on 1 equal to $1 - P(n+1)$? Did the "standing on 1" have any relevance to that value?
$endgroup$
– Pedro A
Jan 12 at 13:13
$begingroup$
The game ends when we reach either $n+1$ or $0$, and the probability of reaching $n+1$ standing on $1$ is (by definition) $P(n+1)$ so the probability of reaching $0$ becomes $1 - P(n+1)$.
$endgroup$
– nesHan
Jan 12 at 14:01
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here is a short proof using induction and symmetry. We use induction on $N$ to show that $P(N) = frac{1}{N}$. For $N = 1$, this is obvious.
Now, suppose that $P(k) = frac{1}{k}$ for $k leq n$. We shall show that the statement holds for $N = n+1$. Note that, in order to reach $n+1$, we must reach $n$. The probability of this is $P(n) = frac{1}{n}$. Now, the probability of reaching $n+1$ when standing on $n$ is the same as the probability of reaching $0$ when standing on $1$, by symmetry. So we get
$$P(n+1) = P(n)(1 - P(n+1)) Leftrightarrow P(n+1) = frac{P(n)}{1+P(n)} = frac{frac{1}{n}}{frac{n+1}{n}} = frac{1}{n+1}$$
So by the principle of induction, $P(N) = frac{1}{N}$ for all positive integers $N$
edited Jan 12 at 9:26
drhab
104k545136
answered Jan 12 at 8:21
nesHannesHan
1785
$endgroup$
$begingroup$
+1 Nice solution.
$endgroup$
– drhab
Jan 12 at 9:26
$begingroup$
Good answer, but you switches from k to n there
$endgroup$
– DreamConspiracy
Jan 12 at 12:56
$begingroup$
Why is the probability of reaching 0 standing on 1 equal to $1 - P(n+1)$? Did the "standing on 1" have any relevance to that value?
$endgroup$
– Pedro A
Jan 12 at 13:13
$begingroup$
The game ends when we reach either $n+1$ or $0$, and the probability of reaching $n+1$ standing on $1$ is (by definition) $P(n+1)$ so the probability of reaching $0$ becomes $1 - P(n+1)$.
$endgroup$
– nesHan
Jan 12 at 14:01
add a comment |
$begingroup$
Here is a short proof using induction and symmetry. We use induction on $N$ to show that $P(N) = frac{1}{N}$. For $N = 1$, this is obvious.
Now, suppose that $P(k) = frac{1}{k}$ for $k leq n$. We shall show that the statement holds for $N = n+1$. Note that, in order to reach $n+1$, we must reach $n$. The probability of this is $P(n) = frac{1}{n}$. Now, the probability of reaching $n+1$ when standing on $n$ is the same as the probability of reaching $0$ when standing on $1$, by symmetry. So we get
$$P(n+1) = P(n)(1 - P(n+1)) Leftrightarrow P(n+1) = frac{P(n)}{1+P(n)} = frac{frac{1}{n}}{frac{n+1}{n}} = frac{1}{n+1}$$
So by the principle of induction, $P(N) = frac{1}{N}$ for all positive integers $N$
edited Jan 12 at 9:26
drhab
104k545136
answered Jan 12 at 8:21
nesHannesHan
1785
$endgroup$
$begingroup$
+1 Nice solution.
$endgroup$
– drhab
Jan 12 at 9:26
$begingroup$
Good answer, but you switches from k to n there
$endgroup$
– DreamConspiracy
Jan 12 at 12:56
$begingroup$
Why is the probability of reaching 0 standing on 1 equal to $1 - P(n+1)$? Did the "standing on 1" have any relevance to that value?
$endgroup$
– Pedro A
Jan 12 at 13:13
$begingroup$
The game ends when we reach either $n+1$ or $0$, and the probability of reaching $n+1$ standing on $1$ is (by definition) $P(n+1)$ so the probability of reaching $0$ becomes $1 - P(n+1)$.
$endgroup$
– nesHan
Jan 12 at 14:01
add a comment |
$begingroup$
Here is a short proof using induction and symmetry. We use induction on $N$ to show that $P(N) = frac{1}{N}$. For $N = 1$, this is obvious.
Now, suppose that $P(k) = frac{1}{k}$ for $k leq n$. We shall show that the statement holds for $N = n+1$. Note that, in order to reach $n+1$, we must reach $n$. The probability of this is $P(n) = frac{1}{n}$. Now, the probability of reaching $n+1$ when standing on $n$ is the same as the probability of reaching $0$ when standing on $1$, by symmetry. So we get
$$P(n+1) = P(n)(1 - P(n+1)) Leftrightarrow P(n+1) = frac{P(n)}{1+P(n)} = frac{frac{1}{n}}{frac{n+1}{n}} = frac{1}{n+1}$$
So by the principle of induction, $P(N) = frac{1}{N}$ for all positive integers $N$
edited Jan 12 at 9:26
drhab
104k545136
answered Jan 12 at 8:21
nesHannesHan
1785
$endgroup$
Here is a short proof using induction and symmetry. We use induction on $N$ to show that $P(N) = frac{1}{N}$. For $N = 1$, this is obvious.
Now, suppose that $P(k) = frac{1}{k}$ for $k leq n$. We shall show that the statement holds for $N = n+1$. Note that, in order to reach $n+1$, we must reach $n$. The probability of this is $P(n) = frac{1}{n}$. Now, the probability of reaching $n+1$ when standing on $n$ is the same as the probability of reaching $0$ when standing on $1$, by symmetry. So we get
$$P(n+1) = P(n)(1 - P(n+1)) Leftrightarrow P(n+1) = frac{P(n)}{1+P(n)} = frac{frac{1}{n}}{frac{n+1}{n}} = frac{1}{n+1}$$
So by the principle of induction, $P(N) = frac{1}{N}$ for all positive integers $N$
edited Jan 12 at 9:26
drhab
104k545136
answered Jan 12 at 8:21
nesHannesHan
1785
edited Jan 12 at 9:26
drhab
104k545136
edited Jan 12 at 9:26
drhab
104k545136
edited Jan 12 at 9:26
drhab
104k545136
104k545136
answered Jan 12 at 8:21
nesHannesHan
1785
answered Jan 12 at 8:21
nesHannesHan
1785
answered Jan 12 at 8:21
nesHannesHan
1785
1785
$begingroup$
+1 Nice solution.
$endgroup$
– drhab
Jan 12 at 9:26
$begingroup$
Good answer, but you switches from k to n there
$endgroup$
– DreamConspiracy
Jan 12 at 12:56
$begingroup$
Why is the probability of reaching 0 standing on 1 equal to $1 - P(n+1)$? Did the "standing on 1" have any relevance to that value?
$endgroup$
– Pedro A
Jan 12 at 13:13
$begingroup$
The game ends when we reach either $n+1$ or $0$, and the probability of reaching $n+1$ standing on $1$ is (by definition) $P(n+1)$ so the probability of reaching $0$ becomes $1 - P(n+1)$.
$endgroup$
– nesHan
Jan 12 at 14:01
add a comment |
$begingroup$
+1 Nice solution.
$endgroup$
– drhab
Jan 12 at 9:26
$begingroup$
Good answer, but you switches from k to n there
$endgroup$
– DreamConspiracy
Jan 12 at 12:56
$begingroup$
Why is the probability of reaching 0 standing on 1 equal to $1 - P(n+1)$? Did the "standing on 1" have any relevance to that value?
$endgroup$
– Pedro A
Jan 12 at 13:13
$begingroup$
The game ends when we reach either $n+1$ or $0$, and the probability of reaching $n+1$ standing on $1$ is (by definition) $P(n+1)$ so the probability of reaching $0$ becomes $1 - P(n+1)$.
$endgroup$
– nesHan
Jan 12 at 14:01
$begingroup$
+1 Nice solution.
$endgroup$
– drhab
Jan 12 at 9:26
$begingroup$
+1 Nice solution.
$endgroup$
– drhab
Jan 12 at 9:26
$begingroup$
Good answer, but you switches from k to n there
$endgroup$
– DreamConspiracy
Jan 12 at 12:56
$begingroup$
Good answer, but you switches from k to n there
$endgroup$
– DreamConspiracy
Jan 12 at 12:56
$begingroup$
Why is the probability of reaching 0 standing on 1 equal to $1 - P(n+1)$? Did the "standing on 1" have any relevance to that value?
$endgroup$
– Pedro A
Jan 12 at 13:13
$begingroup$
Why is the probability of reaching 0 standing on 1 equal to $1 - P(n+1)$? Did the "standing on 1" have any relevance to that value?
$endgroup$
– Pedro A
Jan 12 at 13:13
$begingroup$
The game ends when we reach either $n+1$ or $0$, and the probability of reaching $n+1$ standing on $1$ is (by definition) $P(n+1)$ so the probability of reaching $0$ becomes $1 - P(n+1)$.
$endgroup$
– nesHan
Jan 12 at 14:01
$begingroup$
The game ends when we reach either $n+1$ or $0$, and the probability of reaching $n+1$ standing on $1$ is (by definition) $P(n+1)$ so the probability of reaching $0$ becomes $1 - P(n+1)$.
$endgroup$
– nesHan
Jan 12 at 14:01
add a comment |
1
$begingroup$
This is a case of the famous "gambler's ruin" problem. For this version with a fair game, looking at the probability of reaching one state before another, the easiest approach is to track expected values. OK, where's a good version of this to link to on MSE?
$endgroup$
– jmerry
Jan 12 at 8:08