Grade 12 - Exp. / Markov chains 29 exercises (100% corrected)

a
1. 1st-order linear recurrent sequences of matrices E.6870 Consider the matrices M and R defined by: M = 0.9 0.15 0.1 0.85 ; R = − 5 5 We define the matrix sequence X n defined by: X 0 = 1100 1100 ; X n +1 = M · X n + R for any n ∈ N Using reasoning by recurrence, show that for any natural num-ber n , we have : X n = 1300 − 200 × 0.75 n 900 + 200 × 0.75 n E.108 Consider the matrices A , B defined by: A = 3 3 0 2 ; B = 1 1 ; C = 1 − 1 Consider the sequence U n of column matrices defined by: U 0 = 1 2 ; U n +1 = A · U n + B ∀ n ∈ N 1 Justify that the matrix C verifies the equality: C = A · C + B 2 We define the sequence V n of row matrices by the rela-tion : V n = U n − C for all n ∈ N a Justify the equality: V n +1 = A · V n for all n ∈ N b Using reasoning by recurrence, show that for any nat-ural number n , we have : U n = 3 n +2 − 9 × 2 n +1 3 × 2 n − 1 2. Linear recurrent sequences of matrices of order 1: stable state and joint sequence E.6395 Definition: For any k ∈ N ∗ , consider a sequence U n of column matrix with k rows verifying a relation of the form : U n +1 = A · U n + B for any n ∈ N where A is a square matrix of order k and B is a column matrix with k rows. We call steady state of the sequence U n , the column matrix S (having k rows) and verifying: S = A · S + B Consider a sequence U n verifying the relation: U n +1 = 2 1 − 1 1 · U n + − 2 − 1 Check that the matrix S = − 1 3 is a stable state of the se-quence U n of matrices. E.8647 Consider the sequence X n of column matrices, verifying: X 0 = 1 1 ; X n +1 = − 2 1 − 20 7 · X n + 1 2 ∀ n ∈ N 1 Verify that the matrix S = − 2 − 7 represents the stable state of this recurrence relation. 2 Consider the sequence V n of column matrices defined, for any natural number n , by: V n = X n − S a Establish, for any n ∈ N : V n +1 = A · V n b Using reasoning by recurrence, show that for any nat-ural number n , we have : V n = 7 × 2 n − 4 × 3 n 7 × 2 n +2 − 20 × 3 n c Deduce the expression of the matrix X n as a function of n . 3. 1st-order linear recurrent sequences of matrices: steady-state study E.5514 Consider the two real sequences x n and y n whose terms verify the following system : x n +1 = x n + y n + 1 y n +1 = − 2 x n + 4 y n + 3 1 Consider the column matrix B and, for any integer n , the column matrix X n defined by: B = 1 3 ; X n = x n y n Determine the square matrix A of dimension 2 verifying the relation: X n +1 = A · X n + B 2 a Justify that the matrix I 2 − A is invertible. The ma-trix expression I 2 − A − 1 will be given. b Determine the matrix X realizing the equality: X = A · X + B c If the sequences x n and y n are convergent, give the values of their limit. https://chingmath.fr chapExoCorrec/6870 sacados/6870 chapExoCorrec/108 sacados/108 chapExoCorrec/6395 sacados/6395 chapExoCorrec/8647 sacados/8647 chapExoCorrec/5514 sacados/5514
AB0,350,70,650,3 3 Consider the sequence V n of matrix-colone defined by: V n = X n − X Deduce that, for any natural integer n , the relation: V n = A n · V 0 4 Consider the square matrix P defined by: P = 1 − 1 1 − 2 a Justify that the matrix P is invertible. b Let D be the matrix defined by: D = P − 1 · A · P . Give an expression for the matrix D n for any natural number n . c Deduce an expression for the matrix A n for any natu-ral number n . 5 We take as initial value of the sequences : x 0 = 1 ; y 0 = 2 What can we say about the convergence of the sequences x n and y n ? E.5515 Consider the two real sequences x n and y n whose terms verify the following system : x n +1 = 1.4 x n − 0.6 y n + 0.2 y n +1 = 0.9 x n − 0.1 y n + 0.3 1 Consider the column matrix B and, for any integer n , the column matrix X n defined by: B = 0.2 0.3 ; X n = x n y n Determine the square matrix A of dimension 2 verifying the relation: X n +1 = A · X n + B 2 a Justify that the matrix I 2 − A is invertible, then give a the expression of the matrix ( I 2 − A ) − 1 . b Determine the matrix X realizing the equality: X = A · X + B c If the sequences x n and y n are convergent, give the values of their limit. 3 Consider the sequence V n of matrix-columns defined by: V n = X n − X for all n ∈ N Deduce that, for any natural integer n , the relation: V n = A n · V 0 4 Consider the square matrix P defined by: P = 1 2 1 3 a Justify that the matrix P is invertible. b Note D the matrix defined by: D = P − 1 · A · P . Give an expression for the matrix D n for any natural number n . c Deduce an expression for the matrix A n for any natu-ral number n . 5 Considering the starting values : x 0 = 0.5 ; y 0 = 0.5 What can we say about the convergence of the sequences x n and y n ? 4. Markov chain: associated weighted directed graph E.8216 Consider the Markov chain X n in the state space Ω= e 1 ; e 2 whose evolution of distributions is given, for any n ∈ N , by: P ( X n = e 1 ) X n +1 = e 1 = 0.2 ; P ( X n = e 1 ) X n +1 = e 2 = 0.8 P ( X n = e 2 ) X n +1 = e 1 = 0.7 ; P ( X n = e 2 ) X n +1 = e 2 = 0.3 Give the weighted directed graph associated with this Markov chain. E.8217 Consider the Markov chain X n in state space Ω= e 1 ; e 2 ; e 3 whose evolution of distributions is given, for any n ∈ N , by: P ( X n = e 1 ) X n +1 = e 1 = 0.2 ; P ( X n = e 1 ) X n +1 = e 2 = 0.1 P ( X n = e 1 ) X n +1 = e 3 = 0.7 ; P ( X n = e 2 ) X n +1 = e 1 = 0.6 P ( X n = e 2 ) X n +1 = e 2 = 0.2 ; P ( X n = e 2 ) X n +1 = e 3 = 0.2 P ( X n = e 3 ) X n +1 = e 1 = 0.5 ; P ( X n = e 3 ) X n +1 = e 2 = 0.1 P ( X n = e 3 ) X n +1 = e 3 = 0.4 Give the weighted directed graph associated with this Markov chain. 5. Markov chain: from graph to transition matrix E.5390 We consider an evolutionary phe-nomenon between two states A and B . We note respectively a n and b n the headcount associated with these two states at rank n . Below is the weighted directed graph associated with this evo-lution : Determine the T transition matrix verifying the relationship : a n +1 b n +1 = a n b n · T https://chingmath.fr chapExoCorrec/5515 sacados/5515 chapExoCorrec/8216 sacados/8216 chapExoCorrec/8217 sacados/8217 chapExoCorrec/5390 sacados/5390 AB0,350,70,650,3
AB0,20,60,80,4 ABC0,30,50,60,30,40,30,20,10,3 ABC0,40,50,40,30,50,30,10,30,2 ABC0,350,150,20,60,580,290,50,20,13 A1A20,20,60,80,4 E.8640 We consider an evolutionary phe-nomenon between two states A and B . We note respectively a n and b n the headcount associated with these two states at rank n . The graph below represents the associated weighted directed graph. Determine the T transition matrix verifying the relation: a n +1 b n +1 = T · a n b n E.6393 We are interested in the repetition of a random experiment with three outcomes A , B , C . At each repeti-tion, the evolution of the probabil-ities of its outcomes is subject to the conditional probabilities sum-marized in the probabilistic graphs below. Let a n , b n , c n be the respective probabilities of the events A , B , C during the n ième repetition. Determine the M transition matrix verifying: a n +1 b n +1 c n +1 = M · a n b n c n E.5487 The graph below represents a ran-dom walk between three states A , B and C : We note a n , b n , c n the probabilities associated with each of the states at step n . 1 Determine an expression for each of the terms a n +1 , b n +1 , c n +1 as a function of a n , b n and c n . 2 Modeling states by a matrix ligne Note U n = a n b n c n the matrix-line representing the state at step n . Determine the A transition matrix realizing equality: U n +1 = U n · A 3 Modeling states by a matrix colonne Note V n = a n b n c n the column-matrix representing the state at step n . Determine the B transition matrix achieving equality: V n +1 = B · V n E.8638 We are interested in the repetition of a random experiment with three outcomes A , B , C . At each repeti-tion, the evolution of the probabil-ities of its outcomes is subject to the conditional probabilities sum-marized in the probabilistic graphs below Let us denote a n , b n , c n the respective probabilities of the events A , B , C during the n ième repetition. Determine the M transition matrix verifying: a n +1 b n +1 c n +1 = a n b n c n · M E.6128 Consider two cities A 1 and A 2 in the same region, and study the migratory movements between these two cities: 1 The study shows that : Every year 20 % of the city’s population A 1 move to the city A 2 Every year 60 % of the city’s population A 2 move to the city A 1 This situation is illustrated by the graph below : We wish to assemble this data into the matrix M com-posed of two rows and two columns. The coefficient m ij , located at the i e row and the j e column, represent the frequency of people living the first year in the city A i and living the following year in the city A j . a What interpretation can be given to the coefficients m 21 and m 22 ? b Write the matrix representing this situation. 2 A new study yields the following figures : Every year 65 % of the city’s population A 1 doesn’t move. Every year 30 % of the city’s population A 2 does not move. a Produce the graph representing this situation. b Retaining the conventions of question 1 b , write the matrix corresponding to this matrix. 6. Markov chain: using the transition matrix https://chingmath.fr chapExoCorrec/8640 sacados/8640 AB0,20,60,80,4 chapExoCorrec/6393 sacados/6393 ABC0,30,50,60,30,40,30,20,10,3 chapExoCorrec/5487 sacados/5487 ABC0,40,50,40,30,50,30,10,30,2 chapExoCorrec/8638 sacados/8638 ABC0,350,150,20,60,580,290,50,20,13 chapExoCorrec/6128 sacados/6128 A1A20,20,60,80,4
:::::::::e1:::e2e1::::::e1:::e2e2e1:::::::::e1:::e2e1::::::e1:::e2e2e2 AB0,20,60,80,4 ABC0,30,60,40,40,50,30,10,20,2 E.8641 Consider a Markov chain in state space Ω= e 1 ; e 2 ; e 3 For n ∈ N , the distribution of states at step n is represented by the matrix ı n defined by: ı n = P X n = e 1 P X n = e 2 P X n = e 3 The transition matrix A associated with this evolution verify-ing the relationship ı n +1 = ı n · A is given below : A = 0.1 0.4 0.5 0.2 0.1 0.7 0.3 0.6 0.1 Determine the following probabilities : a P ( X n = e 2 ) X n +1 = e 1 b P ( X n = e 3 ) X n +1 = e 2 E.8639 Consider a Markov chain in state space Ω= e 1 ; e 2 For n ∈ N , the distribution of states at step n is represented by the matrix ı n defined by: ı n = P X n = e 1 P X n = e 2 The transition matrix A associated with this evolution verify-ing the relationship ı n +1 = ı n · A is given below : A = 0.1 0.9 0.4 0.6 1 Determine the probability: P ( X n = e 2 ) X n +2 = e 1 2 a Give the matrix A 2 . b What remark can be made? What conjecture can be made? 7. Markov chain: finding the value of states E.8643 Consider the chaîne X n of Markov in state space e 1 ; e 2 defined, for any natural number n , by: P X = e 1 = 0.3 ; P X = e 2 = 0.7 P ( X n = e 1 ) X n +1 = e 1 = 0.8 ; P ( X n = e 1 ) X n +1 = e 2 = 0.2 P ( X n = e 2 ) X n +1 = e 1 = 0.4 ; P ( X n = e 2 ) X n +1 = e 2 = 0.6 1 a Complete the probability tree below : b Determine the following probabilities : P X 2 = e 1 ; P X 2 = e 2 2 For any natural number n , let M n denote the distribu-tion matrix at step n defined by: M n = P X n = e 1 P X n = e 2 Let A be the transition matrix associated with the Markov chain realizing the relationship : M n +1 = M n · A a Give the matrix A . b Using the calculator, give the matrix: M 0 · A 2 c What do we notice? E.6391 Consider two gases A and B which on contact turn into each other. Initially, the mixture consists of 20 ‘ gas A and 50 ‘ gas B . A study shows that every hour : 20 % gas A turns into gas B ; 60 % gas B turns into gas A . We schematize this phenomenon with the following weighted graph : 1 Determine the composition of the mixture after 3 h . 2 Using the calculator, perform the calculation: 20 50 · 0.8 0.2 0.6 0.4 3 E.6392 The graph below represents a ran-dom walk between three states A , B and C : We note a n , b n , c n the probabilities associated with each of the states at step n . The initial values are: a 0 =5 ; b 0 =2 ; c 0 =7 1 Give the transition matrix M associated with this prob-abilistic graph verifying: a n +1 b n +1 c n +1 = a n b n c n · M 2 Using the calculator, determine the values associated with each of its states at step 3 . Results will be rounded to the nearest thousandth. https://chingmath.fr chapExoCorrec/8641 sacados/8641 chapExoCorrec/8639 sacados/8639 chapExoCorrec/8643 sacados/8643 :::::::::e1:::e2e1::::::e1:::e2e2e1:::::::::e1:::e2e1::::::e1:::e2e2e2 chapExoCorrec/6391 sacados/6391 AB0,20,60,80,4 chapExoCorrec/6392 sacados/6392 ABC0,30,60,40,40,50,30,10,20,2
ABC0,10,30,20,60,10,10,60,20,8 ABC0,50,10,20,70,50,20,40,10,3 AB e1e2e30,10,60,30,10,10,70,30,60,2 E.6394 The graph below represents a ran-dom walk between three states A , B and C : Consider the matrix-column U 0 = 0.3 0.4 0.3 representing the value of the probabilities of being located on each of the vertices at step 0 . Using calculator and observing different terms U 1 , U 2 , U 3 ,. . . , U 20 , what conjecture can be made? E.5488 The graph below represents a ran-dom walk between three states A , B and C : Consider the matrix-column U 2 = 0.4 0.3 0.3 represent-ing the value of the probabilities of being located on each of the vertices at step 2 . 1 Give the transition matrix A realizing the recurrence re-lation: U n +1 = U n · A for any integer n ∈ N 2 Using the calculator, determine the initial value of the probabilities. E.5374 A city is mainly made up of two districts, A and B . The A neighborhood is made up of 251 inhabitants and the B neighborhood is made up of 386 inhabitants. 1 By randomly choosing an inhabitant in the city, what is the probability that he or she comes from the A neighbor-hood? We’ll round the probabilities to the thousandth. Let a 0 be the probability of choosing an inhabitant of the neighborhood A and b 0 the probability of choosing an inhab-itant of the neighborhood B . The row matrix U 0 defined by a 0 b 0 represent the state of these probabilities in the first year of study in this city. Each year, we estimate : 5 % of the inhabitants of the neighborhood A moves to the neighborhood B ; 12 % neighborhood residents B move to neighborhood A ; We denote a n (resp. b n ) the probability of choosing respec-tively a resident of the neighborhood A (resp. of the neigh-borhood B ) in the n-th year of study. Consider the row matrix U n defined by: U n = a n b n 2 a Copy and complete the diagram below to represent the population flows between these two neighborhoods. b Write the terms a n +1 and b n +1 in terms of the values of a n and b n . c Determine the square matrix T of dimension 2 realiz-ing the equality for any natural number n : U n +1 = U n · T 3 Using reasoning by recurrence, establish the following re-lationship for any natural number n : U n = U 0 · T n 4 Using a calculator or matrix calculator software, deter-mine the matrices row U 5 , U 10 and U 20 whose coefficients will be rounded to 10 − 5 . 8. Markov chain: invariant distribution E.8646 Consider a X n Markov chain in state space e 1 ; e 2 ; e 3 whose associated graph is given opposite. Check that the matrix ı representing the invariant distribution is : ı = 0.25 0.5 0.25 E.6117 A company E orders its supplies every week from two suppliers A and H . The observations made in the first few weeks lead us to model the evolution of supplier choice for orders from one week to the next by a probabilistic graph with vertices A and H où : A denotes status : ˇ order is placed with supplier A ı ; H denotes status : ˇ the order is placed with supplier H ı. The transition matrix M of this graph, considering the ver-tices in the order A and H , is : M = 0.95 0.05 0.1 0.9 1 Draw the probabilistic graph associated with the matrix M . 2 Give the meaning of the number 0.95 in the matrix M . 3 Check that the row matrix P = 2 3 1 3 corresponds to the stable state of the system. Give an interpretation. 9. Markov chain: finding the invariant distribution https://chingmath.fr chapExoCorrec/6394 sacados/6394 ABC0,10,30,20,60,10,10,60,20,8 chapExoCorrec/5488 sacados/5488 ABC0,50,10,20,70,50,20,40,10,3 chapExoCorrec/5374 sacados/5374 AB chapExoCorrec/8646 sacados/8646 e1e2e30,10,60,30,10,10,70,30,60,2 chapExoCorrec/6117 sacados/6117
e1e2e30,10,60,20,40,60,20,30,40,2 e1e20,90,60,10,4 e1e2 E.8645 Consider a X n Markov chain in state space e 1 ; e 2 ; e 3 whose step-by-step evolutions of the distrubtions are represented by the graph : 1 Give the A transition matrix associated with this graph. Note ı = x y z the matrix representing the invariant dis-tribution of the chain X n . It verifies the equality: ı · A = ı 2 Consider the matrix B : B = − 0.7 0.1 0.6 0.2 − 0.6 0.4 0.6 0.2 − 0.8 a Justify equality: ı · B = 0 0 0 b Using the calculator, give the determinant of the ma-trix B . c Justify the equivalence of the two systems of linear equations : − 0.7 · x + 0.2 · y + 0.6 · z = 0 0.1 · x − 0.6 · y + 0.2 · z = 0 0.6 · x + 0.4 · y − 0.8 · z = 0 ⇐⇒ − 0.7 · x + 0.2 · y + 0.6 · z = 0 0.1 · x − 0.6 · y + 0.2 · z = 0 0.1 · x − 0.6 · y + 0.2 · z = 0 d What can we deduce about the set of solutions of this system? 3 Consider the matrix C : C = − 0.7 0.1 1 0.2 − 0.6 1 0.6 0.2 1 a Justify that the matrix ı verifies : ı · C = 0 0 1 b Justify : C · − 0.8 0.1 0.7 0.4 − 1.3 0.9 0.4 0.2 0.4 = I 3 c Deduce the coefficients of the matrix ı . E.8644 Consider a Markov chain X n whose state space is e 1 ; e 2 and whose initial distribution is : P X 0 = e 1 = 0.3 ; P X 0 = e 2 = 0.7 The graph below represents the evolution of the distributions, step by step :: Determine the matrix representing the invariant distribution of this Markov chain. 10. Markov chain: asymptotic behavior E.5391 Consider the universe composed of the two states Ω= e 1 ; e 2 . The initial distribution X 0 has probability law : P X 0 = e 1 = 1 3 ; P X 0 = e 2 = 2 3 We note X n the Markov chain defined by the following re-lations : P ( X n = e 1 ) X n +1 = e 1 = 3 5 ; P ( X n = e 2 ) X n +1 = e 1 = 2 5 P ( X n = e 1 ) X n +1 = e 2 = 2 5 ; P ( X n = e 2 ) X n +1 = e 2 = 3 5 1 a Complete the oriented weighted graph associated with this Markob chain : b Give the A transition matrix associated with this graph. 2 Consider the matrix M defined by: M = 1 1 − 1 1 a Justify that M is an inverse matrix, then give M − 1 . b Determine the matrix D = x 0 0 y verifying: A = M · D · M − 1 c Using reasoning by recurrence, establish the following identity for any natural number n : A n = M · D n · M − 1 d Deduce that, for any natural number n , the distribu-tion at step n is defined by: P X n = e 1 P X n = e 2 = − 1 6 × 5 n + 1 2 1 6 × 5 n + 1 2 e Deduce the invariant distribution ı https://chingmath.fr chapExoCorrec/8645 sacados/8645 e1e2e30,10,60,20,40,60,20,30,40,2 chapExoCorrec/8644 sacados/8644 e1e20,90,60,10,4 chapExoCorrec/5391 sacados/5391 e1e2
E.8642 Consider a chain X n of Markovs in the state space e 1 ; e 2 . For any natural number n , note ı n the distribution at step n as a row matrix: ı n = P X n = e 1 P X n = e 2 Consider the identity ı n +1 = ı n · A , for any natural number n , where the transition matrix A is defined by: A = 7 15 8 15 4 15 11 15 The initial distribution is : ı 0 = 1 2 1 2 1 Using reasoning by recurrence, establish for any natural number n : ı n = 1 3 + 1 6 × 5 n 2 3 − 1 6 × 5 n 2 Deduce the invariant distribution of this Markov chain. 11. Study of a probabilistic graph E.6400 A company E orders its supplies each week from two suppliers A and H . The observations made in the first few weeks lead us to model the evolution of supplier choice for orders from one week to the next by a probabilistic graph with vertices A and H where : A designates the state : ˇ the order is placed with the supplier A ı ; H denotes status : ˇ order is placed aurpès supplier H ı. For any natural number n , note : a n the probability of the event : ˇ In the week n , the com-pany E orders its supplies from the supplier A ı ; h n the probability of the event : ˇ The week n , the com-pany E orders its supplies from the supplier H ı ; P n the matrix a n h n corresponding to the probabilis-tic state for the week n . The transition matrix M of this graph, considering the ver-tices in the order A and H , is defined by: M = 0.95 0.05 0.1 0.9 ; P n +1 = P n · M 1 Draw the probabilistic graph associated with the matrix M . 2 Give the meaning of the number 0.95 in the matrix M . 3 Check that the matrix P = 2 3 1 3 corresponding to the stable state of the system. Give an interpretation. 4 We give P 0 = 0.4 0.6 and recall that : P k = P 0 × M k for k natural integer. Determine the week où, for the first time, the probability that the company E orders its supplies from supplier A exceeds the probability that it orders them from supplier H . https://chingmath.fr chapExoCorrec/8642 sacados/8642 chapExoCorrec/6400 sacados/6400 Extrait d'Asie Juin 2014