2 Special cases of Gaussian [Tutorial]

Revision en66, by MazzForces, 2018-07-12 14:00:20

Hello Codeforces. Today I'm writing about a Math topic that is really simple, but resources are limited.

SLAE stands for system of linear algebraic equations. Basically, consider we have a set of equations of the form :

a0·x0 + a1·x1 + a2·x2 + ... + an - 1·xn - 1 = val0

b0·x0 + b1·x1 + b2·x2 + .... + bn - 1·xn - 1 = val1

c0·x0 + c1·x1 + c2·x2 + .... + cn - 1·xn - 1 = val2

.....

Note that all a, b, c... are real-valued arrays and all vali, xi are arbitrary reals. Realize how x0, x1, ...xn - 1 appear in each of the equations. In the post below, it is assumed we are dealing with reals, and not only integers.

Now, we want to find values of [x0, x1...xn - 1] that satisfy each of the given equations listed, given all a, b, c... and vali. The simplest method to find such solutions is to use Gaussian Elimination, that solves the problem in O(N3), where N = number of equations = number of variables .

To Learn about Gaussian Elimination, click here. Today, we shall learn about 2 special class of problems that can be solved using Gaussian Elimination.

Problem 1 : Markov Chains and Cyclic Expected Values :

Pre-requisite : Gaussian-Elimination, Expectation of a random variable.

Many a times as a part of expected value problems, you are expected to sum up infinite series that hold as limits, as probabilities lie in the closed interval [0, 1]. For example,

, as

However, not always can we expect the variables whose Expected value we need to calculate to be independent. Consider you have N random variables , where , there are cyclic dependencies among the variables for their expected values, i.e consider depends on , on and depends on . So, there exists an infinite loop for calculating the Expected values of the random variables.

For example, consider the following problem :

You are given Tree T consisting of N nodes. Initially there is a player in node S. In a single move, he moves to one of the adjacent nodes of the node he is currently at, each with equal probability. What is the expected number of moves before he reaches node T ?.

Here, we need to understand that the expected values are infinite sums as well as cyclic. Creating a simple formula for the answer is quite hard. The Expected value starting from node S depends on some neighbor of node S, however, the Expected value of some neighbor of node S depends on Expected value of node S. Notice that whenever we reach a particular node, the probability of moving to any other node regardless of the number of steps performed always remains the same. So, this is a Markov Chain. Let's consider the transition matrix of this chain.

Create a matrix P, where P[i][j]= probability of moving from node i to j in a single move. Now, Let denote the expected number of steps needed to reach node T from node i.

.

Try and take a moment and think about why this formula is correct.

Spoiler

Surprise Surprise, this can be modeled as SLAE. Rewrite equations as :

. So the system is :

$$\begin{pmatrix} 1-P[0][0] & -P[0][1] & ... & -P[0][N-1] \newline -P[1][0] & 1-P[1][1] & ... & -P[1][N-1] \newline .... \newline -P[N-1][0] & -P[N-1][1] & ... & 1-P[N-1][N-1] \end{pmatrix} \cdot \begin{pmatrix} \mathbb E(0) \newline \mathbb E(1) \newline .. \newline .. \newline \mathbb E(n-1) \end{pmatrix} = \begin{pmatrix} 1 \newline 1 \newline .. \newline 1 \end{pmatrix}$$

This is the equation (IN - PE = 1, We need to find the column vector E. Note that for node T, we need to have P[t][i] = 0, t ≠ i and P[t][t] = 1, as we won't move from node T, it is an absorbent state of the Markov chain. So, the Tth row of matrix IN - P will be all zeros. Also, the equation does not hold true for node T. Also, we know . So, the part does not affect any of the equations. So, just remove the Tth row and column from both sides of the equation.

The matrix is now a square (N - 1)·(N - 1) matrix, that is invertible. Invert the matrix using Gaussian Elimination augmenting with the RHS, to obtain E, i.e.

We can use this generic technique in all cases where the expected values are cyclic in nature , i.e expected value of state A depends on state B, and expected value of state B depends on state A. We can use any prime mod too, to obtain expected value in Modulo. Just remember : dependent random variables, use this. Practice Problems :

One (Same problem as above) My Code

Problem 2 : Xor's using SLAE

Pr-requisite : Vector Space properties, Linear Algebra.

mod 2

mod 2

mod 2

So, xor is just bit-wise addition mod 2. We can represent the xor of two integer's x, y as vector addition in . For example ,

i.e. ,

\begin{pmatrix} 0 \newline 1 \newline 0 \end{pmatrix} + \begin{pmatrix} 1 \newline 1 \newline 1 \end{pmatrix} \equiv \begin{pmatrix} 1 \newline 0 \newline 1 \end{pmatrix}
Mod \space 2

So, we can use this addition to replace xor.The main advantage of this scheme is that we have converted the subset xor problem to solving a linear system instead. Consider we want to find a, b, c such that:

a·v1 + b·v2 + c·v3 ≡ x Mod 2, given v1, v2, v3 and x. Here v1, v2, v3, x are arbitrary binary column vectors. This is equivalent to solving the linear system :

$$\begin{pmatrix} v1 & v2 & v3 \end{pmatrix} \cdot \begin{pmatrix} a \newline b \newline c \end{pmatrix} \equiv x \hspace{0.2cm} Mod \hspace{0.2cm} 2$$.

Since a, b, c can only belong to {0, 1}, this is precisely finding a solution to subset xor.

Note that the span of any given set of size N is a vector space. There is a concept called as Basis of a vector space , i.e a smallest size subset of a given set that spans the entire vector space spanned by the original set given. We can solve the same problem over smaller sized basis rather than using all the elements of the set.

Via the Basis, we can solve useful xor based problems such as :

1> Given a set S of size N, find the number of distinct integers that can be represented using xor over the set of the given elements.

Solution

2> How many sub sequences of a given set S of size N have xor equal to X. (Do it yourself).

Hint

3> What is the maximum possible xor you can have using a subset of a given set :

Solution

All of these problems can be modeled using SLAE in Mod 2. We can do operations faster in Mod 2 using bitset having complexity .

Problems :

One

Two

This is my first time wiring a tutorial blog, so please excuse any minor mistakes. Please give you feedback, it is always useful. Thank You.

History

Revisions

Rev. Lang. By When Δ Comment
en66 MazzForces 2018-07-12 14:00:20 4
en65 MazzForces 2018-06-29 19:00:27 23
en64 MazzForces 2018-06-29 17:43:14 8
en63 MazzForces 2018-06-29 16:20:35 30
en62 MazzForces 2018-06-29 16:18:29 19
en61 MazzForces 2018-06-29 04:16:09 24
en60 MazzForces 2018-06-28 19:10:43 0 (published)
en59 MazzForces 2018-06-26 13:36:11 174
en58 MazzForces 2018-06-23 15:26:12 20
en57 MazzForces 2018-06-23 14:43:15 145
en56 MazzForces 2018-06-23 14:41:38 305
en55 MazzForces 2018-06-21 14:36:53 25
en54 MazzForces 2018-06-21 14:35:52 10
en53 MazzForces 2018-06-19 16:10:21 10
en52 MazzForces 2018-06-19 16:01:40 57
en51 MazzForces 2018-06-19 14:48:09 35
en50 MazzForces 2018-06-19 14:44:05 10
en49 MazzForces 2018-06-19 14:42:50 1147
en48 MazzForces 2018-06-19 14:20:26 300
en47 MazzForces 2018-06-19 02:52:44 46
en46 MazzForces 2018-06-19 02:51:31 311
en45 MazzForces 2018-06-19 02:39:49 397
en44 MazzForces 2018-06-18 18:38:16 95
en43 MazzForces 2018-06-18 18:35:15 449
en42 MazzForces 2018-06-18 18:25:37 1
en41 MazzForces 2018-06-18 18:22:47 419
en40 MazzForces 2018-06-18 15:30:43 1
en39 MazzForces 2018-06-18 15:28:38 25
en38 MazzForces 2018-06-18 15:26:54 28
en37 MazzForces 2018-06-18 15:24:44 2
en36 MazzForces 2018-06-18 15:23:06 77
en35 MazzForces 2018-06-18 15:18:55 192
en34 MazzForces 2018-06-18 13:28:47 11
en33 MazzForces 2018-06-18 13:27:50 183
en32 MazzForces 2018-06-18 13:25:45 10
en31 MazzForces 2018-06-18 13:24:22 258
en30 MazzForces 2018-06-18 13:21:38 46
en29 MazzForces 2018-06-14 01:37:31 49
en28 MazzForces 2018-06-14 01:36:14 23
en27 MazzForces 2018-06-14 01:34:56 351
en26 MazzForces 2018-06-14 01:29:07 122
en25 MazzForces 2018-06-14 01:26:02 3
en24 MazzForces 2018-06-14 01:25:29 10
en23 MazzForces 2018-06-14 01:23:41 10
en22 MazzForces 2018-06-14 01:22:47 2
en21 MazzForces 2018-06-14 01:21:08 616
en20 MazzForces 2018-06-14 01:12:44 8
en19 MazzForces 2018-06-14 01:12:20 30
en18 MazzForces 2018-06-14 01:10:35 26
en17 MazzForces 2018-06-14 01:09:47 296
en16 MazzForces 2018-06-14 01:05:44 435
en15 MazzForces 2018-06-14 00:49:59 33
en14 MazzForces 2018-06-14 00:46:47 561
en13 MazzForces 2018-06-14 00:39:17 725
en12 MazzForces 2018-06-13 23:57:55 3
en11 MazzForces 2018-06-13 23:57:32 4
en10 MazzForces 2018-06-13 23:57:00 48
en9 MazzForces 2018-06-13 23:44:26 6
en8 MazzForces 2018-06-13 23:43:54 916
en7 MazzForces 2018-06-13 23:18:06 1008
en6 MazzForces 2018-06-13 22:40:02 42 Tiny change: ' as $\lim{ x \to \inft} i^x =0$' -> ' as $\lim_{ x \to \infty} i^x =0$'
en5 MazzForces 2018-06-13 16:14:26 8 Tiny change: 'n-1} \cdot3000000 x_{n-1} =' -> 'n-1} \cdot x_{n-1} ='
en4 MazzForces 2018-06-13 16:13:54 385 Tiny change: 'expect to calculate such sums. Con' -> 'expect to reach such simple sums. Con'
en3 MazzForces 2018-06-13 12:57:35 532
en2 MazzForces 2018-06-13 12:49:16 239 Tiny change: 'Codeforces,\n\nSLAE s' -> 'Codeforces.\n\nSLAE s'
en1 MazzForces 2018-06-13 12:43:24 594 Initial revision (saved to drafts)