How to deal with probability questions of this type?

First of all, I would like to say that I still didn´t have a proper probability class (only some introductory class that dealt more with statistics than with pure probability) that would cover this kind of problem, but I would like to see the solution, even if the solution deals with concepts that are not familiar or are vaguely familiar to me and the game goes like this:

Suppose that we have two balls in the box, one red and one blue, and that we take one ball from the box with the probability of $1/2$ that the taken ball is blue and with the probability $1/2$ that the taken ball is red. If the taken ball is red the game stops. If the taken ball is blue we put back that blue ball in the box and add one more blue ball in the box, so we have now three balls in the box, and we take again one ball from the box, now with probability $1/3$ that the taken ball is red and with probability $2/3$ that the taken ball is blue. Again, if the taken ball is red the game stops and if the taken ball is blue we put back that blue ball in the box and add one more blue ball in the box, continuing in this way, we have that when taking the ball from the box $n$-th time we have in the box $n+1$ balls and the probability $\frac {1}{n+1}$ that the taken ball will be red ball and probability $\frac {n}{n+1}$ that the taken ball will be blue ball.

And the questions are:

1) What is the probability that the game will stop after $k$ steps (the game stops when the red ball is taken from the box)?

2) What is the probability that the game will never stop?

-
Thus: Your trouble with all three answers is due to a language confusion: when you say "the probability that the red ball will be chosen after k steps", what you really mean is "the probability that the red ball will be chosen at some step during the k first steps" while the answerers mean "the probability that the red ball will be chosen exactly at step k, not before and not after". If you read again the answers and the comments with this point in mind, they should become clear. – Did Apr 7 '13 at 10:13
@Did Yes I know, that is what I have been clarifying to them! But the user Ju´x gave the complete and satisfactory edited answer that solves the question with that remark in mind.. – user67878 Apr 7 '13 at 10:14
@Did But now the answer to the question begs for another question, if you see the answer then it follows that the probability that the red ball will be chosen after k steps is equal to the probability that the blue ball will be chosen at the k-th step? Do you know of some combinatorial explanation of this or this should be posted as a new question? – user67878 Apr 7 '13 at 10:21
Rephrasing , you wonder why $P(S\geqslant k+1)=P(S=k\mid S\geqslant k)$ for every $k$. This is equivalent to the condition that $P(S=k)=1/(k(k+1))$ for every $k$, but I cannot think of a combinatorial explanation just off the top of my head. You might want to check some literature on Pólya urn models. – Did Apr 7 '13 at 10:42
@Did I do not know if I understood your notation, I meant this, if we denote by $R=k$ the outcome of choosing the red ball at the k-th step and by $B=k$ the outcome of choosing the blue ball at the k-th step then we have here in this problem that $P(R \leq k)=P(B=k)$. And for that I need combinatorial explanation. – user67878 Apr 7 '13 at 10:49

1. Write $S$ the number of steps of the game (before the end). $S=k$ if and only if we took a blue ball in the $k-1$ first steps and a red ball in the last step. Assuming that the steps are independent, this yields $$P(S = k) = \frac{1}{2}\times\frac{2}{3}\times\dots\times \frac{k-1}{k}\times\frac{1}{k+1} = \frac{1}{k(k+1)}$$ so $$P(S \leq k) = \sum_{j=1}^j P(S=j) = \sum_{j=1}^k \left(\frac{1}{j}-\frac{1}{j+1}\right) = 1-\frac{1}{k+1} = \frac{k}{k+1}$$
2. Since $P(S=\infty)=1-P(S<\infty)$, it is enough to compute $$P(S<\infty) = \sum_{k=1}^\infty P(S=k) = \sum_{k=1}^\infty \left(\frac{1}{k}-\frac{1}{k+1}\right) = 1$$
-
As I said below to other user, it is not possible (at least for me), that $P(k)$, the probability that the red ball will be chosen after $k$ steps is decreasing as a function of $k$, so I think this is not the answer to the proposed problem. – user67878 Apr 7 '13 at 9:17
Yes, it is decreasing. Why is that a problem for you? – Siméon Apr 7 '13 at 9:27
I think you made a confusion. What is clearly increasing is $P(S\leq k)$, the probability that the red ball will be chosen in at most $k$ steps. It is not possible for $P(S=k)$ to be increasing since $\sum_k P(S=k) = P(S<\infty) \leq 1$. – Siméon Apr 7 '13 at 9:30
Well, it is not very clear. You should edit the question. – Siméon Apr 7 '13 at 9:39
Anyway, I edited my answer. – Siméon Apr 7 '13 at 9:42

Let denote $B_k$: the ball taken at $k$th step is blue and we have $P(B_k)=\frac{k}{k+1}$ and since the events $B_k$ are independant then $$P(B_1\cap B_2\cap\cdots\cap B_{k-1}\cap B_k^c)=\frac{1}{2}\times\frac{2}{3}\times\cdots\times\frac{k-1}{k}\times\frac{1}{k+1}=\frac{1}{k(k+1)}$$

and $$P(\cap_{k\geq1}B_k)=\prod_{k\geq1}\frac{k}{k+1}=0$$ since we have $$\sum_{k=1}^n\log k-\log( k+1)=-\log(n+1)\to-\infty$$

-
You all gave practically the same answer, which I do not believe is true, because with this approach, you have, for instance, that the probability that the game stops after the first step is $1/2$ and the probability that the game stops after two steps is $1/6$, but how can it be the case that the probability that the red ball will be chosen after $k$ steps decreases as $k$ increases? – user67878 Apr 7 '13 at 9:24
@Thus My explanation is that despite the growing number of blue balls but still there is a possibility of pulling the red ball and the fact that we never take the red blue is practically impossible. – user63181 Apr 7 '13 at 9:32
I understand what you mean but $P(k)$ in my first question is the probability that the game will end after $k$ steps (and is clearly increasing as a function of $k$), it is not the probability that the game will end at the $k$-th step, which is what you calculated and is really decreasing, do you understand me now? – user67878 Apr 7 '13 at 9:39
@Thus According to you intuition what's more probable: take the red ball where let's say there's on the box 5 blue balls and the game end at this step or take this ball where there's 1000 blue balls so tell me the probability should be increasing or decreasing. – user63181 Apr 7 '13 at 9:49

\begin{align*} P(\text{game ends in 1 draw})&= \frac 12\\ P(\text{game ends in 2 draws})&= \frac 12 \times \frac 13\\ P(\text{game ends in 3 draws})&= \frac 12 \times \frac 23 \times \frac 14\\ P(\text{game ends in 4 draws})&= \frac 12 \times \frac 23 \times \frac 34 \times \frac 15\\ P(\text{game ends in 5 draws})&= \frac 12 \times \frac 23 \times \frac 34 \times \frac 45 \times \frac 16\\ \end{align*}

Clearly, we are seeing a pattern here...

$$P(\text{game ends in } k \text{ draws})= \frac{1 \times 2 \times ... \times (k-1)}{2 \times 3 \times ... \times k} \times \frac 1k$$

and

$$P(\text{game never ends})= \frac{1 \times 2 \times ... }{2 \times 3 \times ... }$$ You should be able to finish the solution from here.

-
This is clearly not the solution of the problem because with this approach you have that $P(k)$, the probability that the game will stop after $k$ draws is decreasing as a function of $k$ but surely it must be increasing. – user67878 Apr 7 '13 at 9:14