Nikolaj said:
I don't know even how to begin, so if you could direct me, maybe some good article on internet that would help me to solve this, don't really know math terminology in English so don't know how to find it.
Are you still working on this problem? You should take bpet's advice about using a
recurrence relation. Here's how I would start on the first problem:
\pi_{i,j} is the probability of getting a series of k successful shots given that the last k-i shots have been successful (he needs i more to win right now) and he has j shots left. This probability satisfies the recurrence
\pi_{i,j} = p \pi_{i-1,j-1} + (1-p)\pi_{k,j-1}
\pi_{0,j} = 1 for j = 0, 1, 2, 3, ...
\pi_{i,0} = 0 for i = 1, 2, 3, ...
which can be seen by conditioning on whether the next shot is successful or not. The next shot is successful with probability p, in which case he will need i-1 more consecutive successes to win, and will have j-1 chances left. The next shot is unsuccessful with probability 1-p, in which case he will need k consecutive successes to win, and will have j-1 shots left. If you can solve the recurrence, then \pi_{k,n} is the probability you are looking for.
The second problem sounds like a
random walk of length n, and you are looking for the probability that it stays between -d and d. The random walk is called
biased if p is not 1/2.
BTW: if you don't need a general formula in terms of k, n, and p, but only need a way to compute the answer, there is a much easier way to do this using matrices. For the first problem, there are k+1 states: 0, 1, 2, ..., k. The man is in state i when the last i shots have been successful. If he gets to state k at some point during the series of n shots, he wins, and remains in state k for all later shots. Set up a matrix P where the element P_ij is the probability of going from state i to state j. For k = 3 the matrix would look like this
P =
q p 0 0
q 0 p 0
q 0 0 p
0 0 0 1
where q = 1-p
Then you would first figure out the probability that the man does not reach state k during the n shots. If n = 10, for example, then you raise the matrix P to the 10th power and sum the first three elements of the first row of the result. This is the probability that, starting in state 0, the man is in state 0, 1, or 2 after 10 shots. Call this probability x. Then the probability that he does reach state 3 (that is, he does have a series of 3 consecutive successful shots) will be 1-x.
