There is another interesting problem, which cannot be solved without the concept of probability. This is the "random walk" problem. In its simplest form, this task looks like this: Imagine a game in which the player, starting from the point x = 0, for each move can move either forward (to the point x) or backward (to the point -x), and the decision on where to go is completely random, Well, for example, by tossing a coin. How to describe the result of such a movement? In more general form this problem describes the movement of atoms (or other particles) in a gas - the so-called Brownian motion - or the formation of an error in measurements. You will see how the problem of "random walks" is closely related to the coin tossing experience described above.
First of all, let's look at some examples of random walks. They can be described by "pure" progress D N , in N steps. On fig. 6.5 three examples of random walk paths are shown.
What can be said about such a movement? Well, first of all, one might ask: how far, on average, will we get? We must expect that there will be no middle progress at all, since we can go both forward and backward with equal probability. However, it seems that as N increases, we are more and more likely to wander somewhere farther and farther away from the starting point. Therefore, the question arises: what is the average absolute distance, i.e. what is the average value of |D|? However, it is more convenient to deal not with |D|, but with D 2 ; this quantity is positive for both positive and negative motion and therefore can also serve as a reasonable measure of such random walks.
It can be shown that the expected value D 2 N is simply N, the number of steps taken. By the way, by "expected value" we mean the most probable value (guessed the best way), which can be thought of as the expected mean a large number repetitive wandering processes. This value is denoted as
The expected value of D 2 N for N > 1 can be obtained from D N -1 . If after (N - 1) steps we are at a distance of D N -1, then one more step will give either D N \u003d D N -1 + 1, or D N \u003d D N -1 - 1. Or for squares
If the process is repeated a large number of times, then we expect each of these possibilities to occur with a probability of 1/2, so that the average expected value will simply be the arithmetic mean of these values, i.e. the expected value D 2 N will simply be D 2 n- 1 + 1. But what is the value of D 2 n-1 , or rather, what value do we expect? It's just, by definition, clear that it should be the "average expected value"
If we now remember that
The deviation from the initial position can be characterized by a quantity such as the distance (rather than the square of the distance); for this you just need to extract Square root from D< 2 N >and get the so-called "root mean square distance" Dsk:
We have already said that random walks are very similar to the coin tossing experiment with which we started this chapter. If we imagine that each advance or backward is due to the loss of an "eagle" or "tails", then D N . will simply be equal to N 0 - N P, i.e., the difference in the number of heads and tails. Or since N 0 + N P = N (where N is the total number of tosses), then D N = 2N 0 - N. Recall that earlier we already received an expression for the expected distribution of the quantity No [it was then denoted by k; see equation (6.5)]. Well, since N is just a constant, now the same distribution has been obtained for D. (The dropping of each "eagle" means that it does not fall "tails", so a factor of 2 appears in the connection between N 0 and D.) Thus, in Fig. 6.2, the graph also represents the distribution of distances that we can go in 30 random steps (k = 15 corresponds to D = 0, and k= 16 corresponds to D= 2, etc.).
Deviation N 0 from the expected value N/2 will be equal to
whence for the average standard deviation we get
Let us now recall our result for D sc. We expect the average distance traveled in 30 steps to be √30 = 5.5, hence the average deviation of k from 15 should be 5.5: 2 ≈ 2.8. Note that the mean half-width of our curve in Fig. 6.2 (that is, the half-width of the "bell" is somewhere in the middle) is just about 3, which is consistent with this result.
We are now in a position to consider the question we have avoided so far. How do we know if our coin is “honest”? Now we can, at least in part, answer it. If the coin is fair, then we expect it to come up heads half the time, i.e.
At the same time, it is expected that the actual number of heads will differ from N/2 by an amount of the order of √N/2, or, if we talk about the percentage of deviation, it is equal to
i.e., the larger N, the closer to half the ratio N0/N.
On fig. 6.6 the numbers N 0 /N are set aside for those coin tosses we talked about earlier. As you can see, as the number N increases, the curve gets closer and closer to 0.5. But, unfortunately, there is no guarantee that for any given series or combination of series, the observed deviation will be close to the expected deviation. There is always a finite probability that a large fluctuation will occur—the appearance of a large number of heads or tails—that will give an arbitrarily large deviation. The only thing that can be said is that if the deviations are close to the expected 1/2√N (say, by a factor of 2 or 3), then there is no reason to believe the coin is "fake" (or that the partner is cheating).
We have not yet considered cases where for a coin or some other test object like a coin (in the sense that two or more reliably unpredictable outcomes of observation are possible, for example, a stone that can fall only on one of the two sides) , there is sufficient reason to believe that the probabilities of different outcomes are not equal. We have defined the probability P(O) as the ratio
With this notation, it is implied that there is some "true" probability, which in principle can be calculated, but that various fluctuations lead to an error in its experimental determination. However, there is no way to make these arguments logically consistent. Still, it is better for you to understand that probability is in some sense a subjective thing, that it is always based on some kind of uncertainty in our knowledge and its value fluctuates when they change.
In order to test the "validity" of the random walk hypothesis, we need to determine whether the financial results of a particular stock (our function) are stochastic or deterministic. Theoretically, there is an algorithmic and statistical approach to the problem, but in practice only the latter is used (and there are explanations for this).
Algorithmic approach
Computable function theory, also known as recursion theory or Turing computability, is a branch of theoretical computer science that deals with the concept of computable and non-computable functions. A function is said to be computable depending on whether it is possible to write an algorithm that, given some input, can always compute it.If randomness is a property of unpredictability, then the output of a function can never be accurately predicted. It follows logically from this that all random processes are non-computable functions, since it is impossible to create an algorithm for their calculation. The famous Church-Turing thesis postulates that a function is computable only if it can be computed by a Turing machine:
It would seem that everything is simple - you just need to use a Turing machine to determine whether there is an algorithm that predicts the behavior of stock prices (our function). But here we are faced with the halting problem, that is, the task of determining whether the algorithm will run forever, or will it someday terminate.
This problem has been proven to be unsolvable, which means it is impossible to know in advance whether the program will stop or continue running. This means that it is impossible to solve the problem of finding an algorithm that can “calculate” a function (predict the price of a stock) - before stopping, the Turing machine will need to go through all possible algorithms, and this will take an infinitely long time. Therefore, it is impossible to prove that financial market completely random.
If this fact is not taken into account, then such research has led to the emergence of an interesting field called algorithmic information theory. It deals with the relationship between computability theory and information theory. It defines various types of randomness - one of the most popular is Martin-Lef's definition of randomness, according to which, in order for a string to be recognized as random, it must:
- be incompressible- compression involves the search for a representation of information that uses less information. For example, an infinite long binary string 0101010101…. can be expressed more precisely as 01 repeated infinitely many times, while the infinitely long string 0110000101110110101… has no distinct pattern, and therefore cannot be compressed to anything shorter than the same string 0110000101110110101… This means that if the Kolmogorov complexity is greater than or equal to the string length, then the sequence is algorithmically random.
- Pass statistical randomness tests There are many randomness tests that test the difference between the distribution of a sequence relative to the expected distribution of any sequence that is considered random.
- Don't benefit- an interesting concept, which implies that if it is possible to create a certain bet that leads only to success, then it means that it is not random.
In the absence additional information many systems may seem random when they are not - for example, the same generators random numbers. Or more complex example, the price movement of a certain stock may appear to be random. But if you look at financial statements and other fundamental indicators, then everything may turn out to be completely non-random.
Statistical approach
A sequence is statistically random when it contains no detectable patterns. This does not mean real randomness, that is, unpredictability - most pseudo-random random number generators that are not unpredictable are statistically random. The main thing here is to pass the NIST test suite. Most of these tests involve checking how the distribution of the output of a supposedly random system matches the results of a truly random system. The link provides the Python code for such tests.Hacking the market
After review theoretical foundations concepts of randomness and consideration of tests that allow it to be detected, another important question is whether such tests can be used to create a system that will determine the randomness or non-randomness of market sequences better than a person.The researcher decided to conduct his own experiment, for which he used the following data:
Assets of various types were also analyzed:
- Dollar/pound exchange rates (USD vs GBP) from 1990 to 2015 (daily) ~ 25 years
In addition, two simulated datasets were used for comparison. The first one is a binary dataset generated with the Mersenne vortex algorithm sampling strategy (one of the best pseudo-random generators).
The second is binary data generated by the SIN function.
Problems
Each experiment has its own weak spots. Not without them this time too:- Some tests require more data than the market generated (except when using minute or tick charts, which is not always possible), which means that their statistical significance is slightly less than ideal.
- The NIST tests only test for standard randomness - this does not mean that the markets are not normally distributed or otherwise, but random nonetheless.
- Randomly selected time periods (starting on January 1 of each year) and significance level (0.005). Tests need to be run on a much larger set of samples that start every month or quarter. The p-value did not have a significant impact on the final conclusions, because at different values (0.001, 0.005, 0.05), some tests still failed in certain periods(e.g. 1954-1959)
results
Here are the results obtained using two methods of testing with overlapping or non-overlapping windows:
The following conclusions can be drawn:
- The values lie between the values of the two benchmarks, which means that the markets are less random than the Mersenne Twist and more random than the SIN function. But in the end, they are not random.
- Values vary greatly in dimension - window size greatly affects the result, and uniqueness - markets are not equally random, some are more random than others.
- Benchmark values are consistently good for the Mersenne Twist (over 90% of tests passed on average) and bad for the SIN graph (on average 10-30% of tests passed).
When considering random walks, the state of the system is interpreted for clarity as the position of a moving "particle".
A one-dimensional random walk is a Markov chain whose state space consists of a finite or infinite set of integers; if the particle is in state I, then in one step it can either go to one of its neighboring states or , or remain in the state. If the state space is the set of non-negative integers, then the random walk transition probability matrix has the form
Where . The numbers have the following meaning: if then at
the changes for are obvious.
In favor of the name "random walk" for this type of process is the fact that its implementation describes the path of a "totally drunk" person, taking a random step forward or step back.
The capital of a player participating in a series of games gambling, is often described as a random walk process. Suppose that player A, who has capital, plays with an infinitely rich partner, while the probability that he will win the game and increase his capital by one is equal, and the probability that he will lose and thereby decrease his capital by one is equal to . The dependence of the probabilities of winning and losing on reflects the possible dependence of the conditions of the game on capital. Thus, it can be agreed that, once in state O (corresponding to the ruin of player A), the process remains in this state, i.e., the process where the size of the player's capital after games is a random walk process. This process is known as the player ruin problem.
Random walk with corresponds to the same repeated batches; if then in each game the chances of player A are clearly preferable. In ch. 3, we will show that in this case, with probability where is his initial capital, player A goes bankrupt (loses his capital) and, with probability, his capital will increase indefinitely. If then the game is clearly beneficial to the owners gambling establishment, and it is almost certain (with probability 1) that player A will go broke if he plays long enough. Player A is doomed to ruin (with probability 1) even if the game is harmless, that is, when
If the partner, the player, also starts the game with a limited capital y, then the capital of player A is again described by a Markov chain. However, this chain has a finite set of states where initial states players, respectively. The difference is interpreted as the capital of player B after the games. If a draw is allowed among the outcomes of each game, then the matrix of transition probabilities of the chain has the form
As before, there is a possibility that player A, having capital, will increase (decrease) it by one in the next game. Note that, in accordance with the matrix of transition probabilities (2.3), the capital of player A (state of the process), having reached the value a or turning to 0, remains in these states forever. We say that player A is ruined if the process has reached state 0; if the process gets into state a, then we say that the player is ruined
Random walks turn out to be useful not only for describing game situations, but also serve as good models physical processes, in particular particle diffusion. If a particle undergoes random collisions, then its position is subject to random fluctuations, although the trajectory it describes is continuous. If the future position (more precisely, its probability distribution) of a particle depends only on its present position, then the process where the position of the particle at the moment is Markovian. A discrete approximation of such a continuous motion corresponds to a random walk. A symmetric random walk is a classical discrete analogue of Brownian motion (see § 2 ch. 1). By a symmetric random walk on the set of all integers is meant a Markov chain with the state space being the set of all integers, with elements of the matrix of transition probabilities of the form
Where . A symmetric random walk is usually called a Markov chain with
The study of some physical models leads us to the consideration of random walks on the set of non-negative integers. It is possible to give a classification of such processes on the basis of the properties of the zero state. Let the random walk be described by matrix (2.2). If (and hence, and ), then the zero state has the properties of a reflecting screen. Whenever a particle reaches the zero state, the next transition results in it being in state 1. This corresponds to the situation when an elastic wall is at zero and the particle bounces off it without any residual effects.
If then the zero state behaves like an absorbing screen. Once in the zero state, the particle remains
in it forever. If then the null state is a partially reflective screen.
If the random walk is limited to a finite number of states, say both extreme states 0 and a, independently and in any combination, can be reflective, absorbing, or partially reflective screens. We have already dealt with the case when the states 0 and a were absorbing [see. (2.3)].
The classical model of diffusion through a membrane is the Ehrenfest model. The model is described as a random walk process with a finite number of states, with the extreme states a and a being reflective screens. The transition probability matrix is given as follows:
The physical interpretation of this model is as follows. There are two urns containing together 2a balls. Suppose urn A contains balls. At each test, one ball is randomly selected and transferred to another urn; moreover, each of the balls has the same probability as all the others of being transferred, regardless of the urn in which it is located. Each test leads to a change in the state 1) of the system. Characteristic for the movement of the balls will be the predominant direction from the urn with a higher concentration to the urn with a lower concentration. The Ehrenfest model can in some cases be used to study physical systems, under the action of restoring forces, the magnitude of which is proportional to the distance from the equilibrium position.
The classical symmetric -dimensional random walk is defined as follows. The process state space is an integer lattice in (n-dimensional Euclidean space) whose points are sets of integers of the form Transition probabilities are defined as follows:
Similarly to the one-dimensional case, the -dimensional symmetric random walk is a discrete analogue of the -dimensional Brownian motion.
Describing the movement of a particle in a certain phase space under the influence of some random mechanism. The phase space is usually d-dimensional or integer in it. Random mechanisms may be different; more often they consider random variables generated by the summation of independent random variables or Markov chains. The exact generally accepted definition of S. b. No.
Trajectories of the simplest S. b. in the case d=l are described by the initial position S 0 =0 and the sequence of sums
Where X i are independent and have Bernoulli
Meaning S n can be interpreted as the payoff of one of the two players after n games in a game in which this player wins one ruble in each of the games with probability .
and loses it with probability 1- R. If the game is played by tossing a symmetrical coin, then we should put p = 1/2 ( symmetrical walk, cm. Bernoulli wander).
Assuming that the initial capital of the 1st player is equal to b, and the initial capital of the 2nd player is equal to a, the game will end when the wandering particle (with coordinates S 1 , S 2 , . . . ) first touches one of the levels ai or -b. In this one of the players will go broke. This classic. the ruin problem, in which the barriers at the points a and -b can be regarded as absorbing.
In applications related to queuing theory, a particle near the barriers au -b=0 can behave differently: for example, if a=, b=0, then the position Z n+ 1 wandering particle at time n + 1 in accordance with (1) is described by the relation
and the barrier at point 0 can be called. delaying. There are other possibilities for particle behavior near barriers.
If a = then they get tasks for S. b. with one border. If a=b= then get unlimited S. b. The study of the described S. b. usually occurs using the apparatus of discrete Markov chains and, in particular, by studying the corresponding equations in finite differences. Let, for example, uk there are ruins of the 1st player in the ruin problem if his capital is equal to k, 
and the total capital of both players is fixed and equal to a+b. Then from the formula full probability(by the first jump) it follows that and k satisfies the equation
And boundary conditions u a=0, u-b= 1. From here we get
The second of these formulas shows that even the innocent
Mathematical encyclopedia. - M.: Soviet Encyclopedia. I. M. Vinogradov. 1977-1985.
See what "RANDOM WALK" is in other dictionaries:
Random walk theory The theory that changes in the value of securities fluctuate randomly around their objective price opposes the theory of technical analysis. Contents 1 One-dimensional discrete random walk ... Wikipedia
random walk- atsitiktinis klajojimas statusas T sritis fizika atitikmenys: engl. random walk vok. zufällige Irrfahrt, f; zufällige Schrittfolge, f rus. random walk, n pranc. cheminement aléatoire, m; errance, f; marche aléatoire, f … Fizikos terminų žodynas
Random walk generated by Bernoulli trials. On the example of B. b. it is possible to explain some basic features of more general random walks. In particular, already in this the simplest scheme properties of randomness appear, paradoxical from the point of view ... ... Mathematical Encyclopedia
The problem of the ruin of a player is a problem from the field of probability theory. It was considered in detail by the Russian mathematician A.N. Shiryaev in the monograph "Probability" ... Wikipedia
A game that has the character of a process unfolding in discrete time on a tree-like ordered set (also called a tree). Final P. and. called system where 1) I is the set of players (|I| = n); 2) X is a finite tree, vertices to which are called ... ... Mathematical Encyclopedia
Homogeneous Markov process X(t), where T is an additive subsemigroup of the real axis R with values in topological terms. space. with topology and Borel algebra, the transition function P(t, x, B), which has a certain property of smoothness ... Mathematical Encyclopedia
This term has other meanings, see Monte Carlo (meanings). Monte Carlo method (Monte Carlo methods, MMK) common name groups of numerical methods based on obtaining a large number of implementations of a stochastic (random) ... ... Wikipedia
The Monte Carlo method (Monte Carlo methods, MMK) is the general name for a group of numerical methods based on obtaining a large number of implementations of a stochastic (random) process, which is formed in such a way that its probabilistic ... ... Wikipedia
The random motion of Brownian particles in a liquid or gas is an example of random walks. The theory of Brownian motion was built by A. Einstein and M. Smoluchovsky in 1905 - 1906.
The random walk problem is one of the widely studied problems in probability theory and has many other applications.
6.1. Regularities of random walks
Random walk patterns can be understood using simple model, which is easily implemented using a computer.
N particles (which are initially distributed on the y axis for the convenience of observations) are displaced by successive steps ∆x along the x axis. Each step of each particle is chosen randomly and independent of other steps. However, the probability distribution for any step is the same. We assume that displacements in opposite directions are equally probable. This means that the average value of the bias
∆x = 0. |
The meaning of this equality is that the arithmetic mean of the displacements ∆x of a very large number of particles approaches zero as this number grows. This is how averaging is understood. Sometimes such averages are called a priori 19 . In addition, we will use "observed averages" - arithmetic averages for a given number of particles (usually very large). The “observed average” of particle displacement ∆x n is small, but not equal to zero.
After each step, the particles will "spread out" from the y axis. Let x (k ) denote the coordinate of some particle in k steps. Then
x (k + 1) = x (k) + ∆x. |
Averaging this equality (again over the set of particles), we obtain
x(k+1)=x(k) ,
those. the average value x (k) does not change from step to step and, therefore, is equal to x (0) = 0. The observed value x n for a large number of particles
x (k)n \u003d N |
||||
1 x j(k) |
||||
we previously assumed that the probability of getting heads is 1/2.
turns out to be close to zero (here x j is the coordinate of the jth particle)20 .
The width of the band over which the particles are distributed after the kth step is conveniently characterized by x 2 (k ) . To find out the dependence of this value on the number of steps, let's square the equation (2) and average:
x 2 (k + 1) \u003d x 2 (k) + 2x (k)∆x + (∆x)2. |
Since x (k ) and ∆x are independent, we have
x (k )∆x =x (k ) ∆x = 0.
Denote (∆x )2 =a 2 . From (4) it follows
x 2 (k + 1) \u003d x 2 (k) +a 2,
those. the mean square of the coordinate increases with each step by a 2 . Means,
x2 (k) = ka2 . | ||||
Observed value | ||||
n = | xj 2 | |||
varies approximately in proportion to the number of steps.
The distribution of particles in the strip occupied by them is characterized in more detail by the distribution function f (x), which determines the concentration of particles; dW = f (x) dx
is the probability that the coordinate of the j -th particle after the k -th step will be in the interval x ≤ x j ≤ x + dx . The theory of random walks gives for a sufficiently large number of stepsk the Gaussian distribution
f(x) = | |||||||||
√ 2 πka2 | |||||||||
The observed distribution function is obtained by dividing the x-axis into finite intervals and counting the number of particles in each of them. The result of the count is represented graphically by a stepped curve - a histogram (Fig. 7).
Let's pay attention to one property of dependence (5). If we enlarge the time steps by a factor of l, then the average square of the displacement per one step a 2 follows
K/l . Eventually |
||||||
in line with (5 ) replace with a | And the number of steps k - on k |
|||||
(k)=la | k/l = a | k , i.e. the type of dependence (5 ) does not change when enlarged |
||||
20 For a given number of particlesN, this is true for not too big room step k .
Rice. 7. Distribution of particles during diffusion (histogram and theoretical curve)
6.2. Estimation of the Motion Parameters of a Brownian Particle in a Fluid
We give estimates for real Brownian motion. The average speed of the chaotic motion of a Brownian particle v T is defined in the same way as average speed molecules, ratio
If the particle velocity is close to the thermal one, v v T , then the force is naturally much smaller, and its deviations from the mean value −αv are very significant.
21 For a ball of radius R in a liquid with a viscosity coefficient η according to the Stokes law
α = 6πηR.
It is these deviations that are responsible for the non-stop chaotic motion of the particle. If we are talking about such a motion, then τ from (9) can be understood as an estimate of the time after which the particle “forgets” the initial direction of motion. But the same quantity τ gives a rough estimate of the time interval during which the particle "remembers" the direction of motion. (Perhaps, to estimate the time of “guaranteed forgetting” it would be worth taking 2τ , and to estimate the time of guaranteed direction preservation τ/ 2, but we are not interested in “guaranteed”, but average times, so we will assume that the coefficients 2, 1/2 and etc. lie outside the accepted accuracy of estimates.)
In time τ, the particle travels a path equal in order of magnitude to
a vT τ. |
We can consider particle displacements for different time intervals of the order of τ as random, similar to those considered earlier ∆x , only directed not along the x axis, but in an arbitrary direction (for example, as three simultaneous and independent displacements along three coordinate axes). The motion of a particle in time t τ can be divided into k t/τ of such steps. The displacement of a particle over time t is estimated by analogy with (5):
(t) ka(vT τ) | ||||||||
This result is usually presented in the form | ||||||||
r2 (t) = 6 D t, | ||||||||
where D is the diffusion coefficient22. Given (8 ), (9 ), (11 )
D k α B T .(13)
If at first the particles were concentrated in some small volume, then over time they spread further and further, occupying a region of size r(t).
Relations like (12 ), (13 ), obtained by Einstein and Smoluchowski, served as the basis for Perrin's experiments, during which the mass of atoms was determined and which were accepted by the "scientific community" as convincing evidence of the existence of atoms.
The regularities described above should be understood as the limiting case corresponding to the observation of an infinite number of particles. The implementation of random walks of a finite number of particles that perform Brownian motion (real or "computer") demonstrates only an approximate fulfillment of these relationships.
22 For random walks in the x direction, instead of (12 ) we have x 2 (t ) = 2 D t .
