Random walks (Feller probability theory)

Statement of the problem
A drunk stands one step away from the edge of a cliff. He steps randomly either toward or away from the edge of the cliff. Each step has a 2/3 probability of moving away from the edge, and a step toward the edge has a 1/3 probability. What are the drunk's chances of avoiding falling?

Solution to the problem
Before solving a problem, it is useful to think about the possible answer. Consider what might happen in the first few steps. The diagram in Figure 35.1 illustrates the fact that a person can fall only after an odd number of steps. After one step, the probability of falling is 1/3 (Figure 35.1). The path 1 → 2 → 1 → 0 adds another 2/27 to the probability of falling, giving a total probability of misfortune of 11/27. After five steps, the paths 1 → 2 → 1 → 2 → 1 → 0 and 1 → 2 → 3 → 2 → 1 → 0 together add 8/243 to the probability of falling, giving a total of 107/243. The list could go on, but we will now take a different approach.

The real problem of wandering is very popular and has many formulations. From now on we will treat it as a problem of a particle moving along an axis.

Consider a particle that is initially at position x = 1 on the axis. The structure of the problem will be clearer if the probability of a step to the right is p instead of 2/3. The particle moves from position 1 either to point x = 2 with probability p or to point x = 0 with probability 1 - p (Fig. 35.2). In general, if a particle is at position x = n, n > 0, n is an integer, then it moves either to point x = n + 1 with probability p or to point x = n - 1 with probability 1 - p. If the particle gets to position x = 0, then it is absorbed there (does not take any other steps). We are interested in the value of the probability P₁ that the particle is absorbed at point x = 0 if it leaves point x = 1. Of course, the value of P₁ depends on p. It seems natural that if p is close to 1, then the probability of P₁ is small, and if p is close to zero, then P₁ differs little from 1.



Consider the situation after the first step: either the particle has moved to the left, hit the point x = 0 and been absorbed there (this event has probability 1 - p), or it has moved to the right to the point x = 2 (this event occurs with probability p). Let P₂ denote the probability that the particle is absorbed at the origin x = 0 if it comes out of the point x = 2. Then we have
P₁ = 1 - p + p•P₂, (1)
since 1 - p is the probability of absorption at the first step and p•P₂ is the probability of absorption at subsequent steps.

Each path leading to absorption from x = 2 can be broken down into two parts:
(1) A path starting from a point x = 2 and reaching a position x = 1 for the first time (not necessarily in one step)
And
(2) A path from x = 1 to x = 0 (also not necessarily in one step). The probability of a path from x = 2 to x = 1 is P₁ since the structure of the walk here is identical to the structure of the original walk (see Fig. 35.1), except that the origin is moved one step to the right. The probability of getting from x = 1 to x = 0 is also P₁ as in the original problem. The quantity P₂ is therefore P₁², since events A (the particle moves along the path from point x = 2 to x = 1) and B (the particle moves along the path from point x = 1 to x = 0) are independent, and P(A) = P( = P₁.
We can rewrite equation (1) as
P₁ = 1 - p + p•P₁², (2)
Equation (2) is quadratic with respect to P₁ and has two solutions:
P₁ = 1; P₁ = (1 - p)/p. (3)

In such problems, one or both solutions may be suitable, depending on the values of p.

If p = 1/2, then both solutions coincide, and P₁ = 1. When p = 1, P₁ = 0, since the particle always moves to the right. And when p = 0, obviously, P₁ = 1. When p 1, and by the meaning of the problem P₁ ≤ 1. Therefore, when 0 ≤ p ≤ 1/2 we have P₁ = 1.

To prove that the second solution P₁ = (1 - p)/p holds for p > 1/2, we only need to establish that P₁ is a continuous function of p (roughly speaking, that P₁ does not change much when p changes little). We assume this continuity, but do not prove it.
The curve (see Fig. 35.3) starts at the point P₁ = 1 for p = 1/2; it must descend to P = 0 for p = 1, and its ordinate must always be equal to 1 or (1 - p)/p. The curve has no discontinuities only if, for p > 1/2, the corresponding value is equal to (1 - p)/p. Thus, assuming the continuity of the function P₁, we obtain P₁ = (1 - p)/p for p > 1/2.
Therefore, our drunkard will fall down with a probability of 1/2.



Let us give another interpretation. Consider a player with an initial capital of one monetary unit (x = 1). He can play indefinitely, and in each round of the game he wins or loses this unit with some probability. In order for the probability of the player's bankruptcy to be no more than 1/2, the probability of winning in a single game must be no less than 2/3. The fact that bankruptcy is inevitable at p = 1/2 is a surprise to most of us.

Here is another way of looking at the problem. Consider a player with initial capital x = 1, playing indefinitely against a casino with infinite capital in a "harmless game" (p = 1/2), in which he wins or loses one unit in each round. He will probably go bankrupt (P₁ = 1). In order for him not to go bankrupt with probability 1/2, the probability of his winning in each individual game must be p = 2/3.

That bankruptcy is inevitable even at p WIN = 1/2 (net 50%) is unexpected for most of us.

It is commonly assumed that if individual games are "harmless" (average loss is zero), then the entire game is harmless. Of course, this notion is true in the usual sense. If we imagine such a game with p = 1/2 and a large number of games, then the average value of the money in hand after n games is 1 for each finite number n.

Thus, the absence of "harmlessness" is one of the paradoxes of the infinite.

Another surprising fact is that for p = 1/2 the average number of steps required for absorption is infinite. The case p = 1/2 is strange and profound.
You may be interested in applying the method given here to a particle emerging from x = m rather than from x = 1. Generalizing the above result, the probability of absorption from the x = m axis is [(1 - p)/p]^m or 1, depending on whether p is greater or less than 1/2. If p > 1/2 and m is large, then it is very likely that the particle will escape absorption, and so the probability of absorption is small rather than 1.
If a particle starts from the origin 0 and is allowed to take steps in both directions with probability p = 1/2, then another classical random walk problem asks whether the particle will ever return to the origin. We have already seen that this will indeed be the case, since it will certainly return from positions x = 1 and x = -1.

Further details about this problem can be found in the "Player's Ruin" problem.

Coin wrote: Greetings alt2005 and all miners!

The question is what to base forecasts on.

It is a mistake to think about leveling out the distortions of the entire system.

The alignment takes place, but it far exceeds the player's expectations in time. You play 100-200 spins, you see that the 3rd dozen clearly dominates in places and there is a clear bias in throws in its direction.

It is correct to use the existing trend, rather than go against the facts of the session and expect that the 3rd dozen has already exceeded the plan and will now freeze.

1) The market almost always goes beyond the wildest expectations of the participants.
2) The alignment can be very extended in time (for example, over the next 1000 spins) and practically imperceptible to the eye.

P.S. All roads lead to Rome.

Let's take some random roulette statistics from the neighboring topic with a layout by dozens:

NUM D
29 - 3
31 - 3
20 - 2
23 - 2
26 - 3
11 - 1
7 - 1
6 - 1
22 - 2
10 - 1
6 - 1
22 - 2
9 - 1
7 - 1
17 - 2
25 - 3
5 - 1
7 - 1
29 - 3
33 - 3
28 - 3
35 - 3
7 - 1
18 - 2
0 - 0
29 - 3
0 - 0
21 - 2
25 - 3
24 - 2

26 - 3
9 - 1
0 - 0
36 - 3
0 - 0
14 - 2
10 - 1
26 - 3
36 - 3
17 - 2
25 - 3
31 - 3
1 - 1
28 - 3
31 - 3
36 - 3
17 - 2
29 - 3
29 - 3
7 - 1
18 - 2
10 - 1
24 - 2
22 - 2
36 - 3
21 - 2
16 - 2
27 - 3
4 - 1
26 - 3

14 - 2
0 - 0
8 - 1
26 - 3
30 - 3
7 - 1
8 - 1
30 - 3
4 - 1
15 - 2
2 - 1
15 - 2
3 - 1
22 - 2
8 - 1
14 - 2
15 - 2
24 - 2
1 - 1
0 - 0
27 - 3
21 - 2
2 - 1
32 - 3
3 - 1
17 - 2
18 - 2
28 - 3
3 - 1
24 - 2

We calculate the offsets from the current dozen: to the right +1, to the left -1, in place 0. We regard zero as 0 offset. The transitions are circular, i.e. if after the 3rd dozen the 1st one fell, then it is to the right +1.

Let's collect all the obtained movements into one graph, i.e. add the current transition +/-1 or 0 to the current coordinate. We geta classic random walk graph



In this particular case there are no strong deviations and long compensations - the game is going normally.

I've always wondered why people build a foundation and then abandon it?

The obvious conclusion from the previous post is that the RM atom "Signatur" needs to be revised.

1) Maintain a random walk graph of session predicates.
2) The forecast should be based on the continuation of the GROUPS of the most frequent throws of the short and medium statistical horizons.
3) Only give it to work on real rates in those cases when the forecast direction coincides with the current skew (half-plane) of the random walk graph.

P.S. point 2 can be deepened by analyzing IN/OUT throws from the current sector of the wheel

in Odessa you said that in roulette everything is like a ball of rubber and no matter how much you pull it forcibly in one direction, then everything returns to its original position... = this was a very correct remark

Two-dimensional random walk
Leaving the origin 0, the particle moves with equal probability one step either to the south or to the north, and simultaneously (also with equal probability) one step either to the east or to the west. After the step is taken, the movement continues in a similar way from the new position, and so on ad infinitum. What is the probability that the particle will ever return to the origin?

Classical calculations on random walks, contrary to logic, prove that

...the particle will not only return, but will return an infinite number of times. More precisely, it should be said that almost every particle returns infinitely often, since there are paths, such as the constant direction to the northeast, which allow some particles to go to infinity. But the proportion of such particles is zero.

///////////////
in predicates it is necessary not only to use the most frequent vectors, to observe the trend, but also to know the critical level of "tension", after which the system will begin to return to the origin of coordinates.... = to compensate for the deviation
we would use both the wave growth and its reverse movement

alt2005 could help us with this issue, he is a cool mathematician

Well, yes, it will come back. In relation to roulette - any event will repeat itself, if I understood the topic correctly. But the question is - when? What's the point if the number repeats itself, say, in 100 times, if we, while we wait for it, go into the minus?
It is useless to wait for the first (closest in time) return of a particle or something else. I have already said this on CGM. The problem is that any random event tends to appear as soon as possible. And this is very bad. We do not know when exactly it will appear. Rather, we need to wait for the appearance of an event, like in cards. When the ace of spades has not appeared 33 times, it is clear that it is in the remaining 3 cards. The probability of guessing it is no longer 1/36, as at the beginning, when the deck is still full, but already only 1/3.

in predicates it is necessary not only to use the most frequent vectors, to observe the trend, but also to know the critical level of "tension", after which the system will begin to return to the origin of coordinates.... = to compensate for the deviation
we would use both the wave growth and its reverse movement

There are no trends on the roulette wheel, and no tensions either. The system does not strive to compensate for anything at all, it is just that such "compensation" occurs within the framework of the law of large numbers. And then we are talking only about relative compensation, I talked about this on the neighboring thread.
There are no waves either. There is dispersion, but it has nothing to do with waves.

We look forward to explanations on the theory of "large numbers"!