Evaluating U(l) with Applied Linear Algebra: A Gambler's Demise

[Schwarzschild90]

Okay. I didn't recognize that using the inverse should be avoided.

But would this count as solving the problem numerically?

 

[Ray Vickson]

Okay. I didn't recognize that using the inverse should be avoided.

But would this count as solving the problem numerically?

I don't know what "this" refers to.

Also, I do not know Matlab syntax, so I have no idea what you are doing. Perhaps if you just stated what you are calculating (in standard mathematical language) I could comment knowledgably.

 

[Schwarzschild90]

I don't know what "this" refers to.

Also, I do not know Matlab syntax, so I have no idea what you are doing. Perhaps if you just stated what you are calculating (in standard mathematical language) I could comment knowledgably.

By "this" I mean the method you employ to calculate the transition probabilities.

Sorry, I misread your post as your stating that most of you are very familiar with MATLAB and its syntax. Hency why I didn't take care to explain the syntax.

The MATLAB code (see below) produces a transition matrix T of size M x M. The matrix is slightly more difficult to produce in matlab, as you must "compose" it of a variety of "constituent" matrices. Irregardless, the following code produces a matrix T equal to the one you produced manually.

clear
M=6;
X = ones(M,1);
A = diag(-2*X,0);
clear X
X = ones(M-1,1);
B = diag(X,1);
C = diag(X,-1);
T = A+B+C;
T(1,:)=0;
T(M,:)=0;
clear X B C;

U(l) = \frac{ T^{-1} }{\tau} * n_0 correctly produces the ultimate probability, but only if the first and last row are not equal to zero, in which case MATLAB cannot determine the inverse matrix of T.

 

[Schwarzschild90]

I want to expound on the ultimate probability as determined by matlab.

Taking tau = 1, we get the following expression for the ultimate probability, taking l = 1. (So the first position in the n_0 column vector is = 1.)

U(l) = - \frac{T^{-1}}{\tau} n_0 =<br /> \left[\begin{array}{cc}<br /> 0.8 &amp; 0.6 &amp; 0.4 &amp; 0.2 \\<br /> 0.6 &amp; 1.2 &amp; 0.8 &amp; 0.4 \\<br /> 0.4 &amp; 0.8 &amp; 1.2 &amp; 0.6 \\<br /> 0.2 &amp; 0.4 &amp; 0.6 &amp; 0.8 \\<br /> \end{array} \right]<br /> <br /> \left[\begin{array}{cc}<br /> 1 \\<br /> 0 \\<br /> 0 \\<br /> 0 \\<br /> \end{array} \right]<br /> <br /> =<br /> <br /> \left[\begin{array}{cc}<br /> 0.8 \\<br /> 0.6 \\<br /> 0.4 \\<br /> 0.2 \\<br /> \end{array} \right]<br /> <br />

Where n_0 is the initial state. Do I use n_0 to "pluck" out the first row? As it is, I don't use n_0 for any purpose whatsoever.

But taking out the first row determines the ultimate probability of ruin as a function of the initial state?

Pr = \left[\begin{array}{cc}<br /> 0.8 &amp; 0.6 &amp; 0.4 &amp; 0.2 \\<br /> \end{array} \right]<br />

 

[haruspex]

the ruin probabilities do not depend in any way on the value of ττ\tau you choose. The value of ττ\tau affects the speed at which the limits are attained

Yet the equation used for U(l) in post #34 and earlier divides by tau, and taking different values of tau is producing different probabilities.
I cannot understand why tau features there in conjunction with T. T should already be rate-independent.

 

[Schwarzschild90]

Yet the equation used for U(l) in post #34 and earlier divides by tau, and taking different values of tau is producing different probabilities.
I cannot understand why tau features there in conjunction with T. T should already be rate-independent.

Supposedly it's just the rate the ultimate probability is reached with. The ultimate probability is inversely proportional to tau, so large values of tau might correspond to years.

I've emailed the professor to clarify things.

 

[Ray Vickson]

Supposedly it's just the rate the ultimate probability is reached with. The ultimate probability is inversely proportional to tau, so large values of tau might correspond to years.

I've emailed the professor to clarify things.

If you are given a specific matrix $\mathbf{T}$ with actual numerical values, then there is no choice for $\tau$. Your $(M-1) \times (M-1)$ matrix $\mathbf{T}$ must be a submatrix of the $(M+1) \times (M+1)$ matrix whose first and last rows equal zero and whose rows all sum to zero (just as in post #28). So, if the first row of your $T$ has the form $[-2r, r, 0, \ldots, 0]$ then your equations to detemine the vector of ruin probabilities
$$\mathbf{u} = \pmatrix{u_1\\ u_2\\ \vdots \\u_{M-1}} $$
read as
$$ \mathbf{0} = \mathbf{h} + \mathbf{T u}, $$
where
$$\mathbf{h} = \pmatrix{r \\ 0 \\ \vdots \\ 0} = r \pmatrix{1\\0\\ \vdots\\0} \equiv r \mathbf{e}$$
Thus
$$ \mathbf{u} = - r \mathbf{T}^{-1} \mathbf{e}$$.
The answer you get will be independent of the actual numerical value of $r$.

 

[Schwarzschild90]

If you are given a specific matrix $\mathbf{T}$ with actual numerical values, then there is no choice for $\tau$. Your $(M-1) \times (M-1)$ matrix $\mathbf{T}$ must be a submatrix of the $(M+1) \times (M+1)$ matrix whose first and last rows equal zero and whose rows all sum to zero (just as in post #28). So, if the first row of your $T$ has the form $[-2r, r, 0, \ldots, 0]$ then your equations to detemine the vector of ruin probabilities
$$\mathbf{u} = \pmatrix{u_1\\ u_2\\ \vdots \\u_{M-1}} $$
read as
$$ \mathbf{0} = \mathbf{h} + \mathbf{T u}, $$
where
$$\mathbf{h} = \pmatrix{r \\ 0 \\ \vdots \\ 0} = r \pmatrix{1\\0\\ \vdots\\0} \equiv r \mathbf{e}$$
Thus
$$ \mathbf{u} = - r \mathbf{T}^{-1} \mathbf{e}$$.
The answer you get will be independent of the actual numerical value of $r$.

Correct. I am given a specific matrix. What do you mean by no choice for tau? (I might have difficulties putting your explanation into context, as I am not familiar with your notation)

I determined the ultimate probability by taking tau = 1 and computing the inverse of T, like so:

U=-(inv(T)/tau).

 

[Ray Vickson]

Correct. I am given a specific matrix. What do you mean by no choice for tau? (I might have difficulties putting your explanation into context, as I am not familiar with your notation)

I determined the ultimate probability by taking tau = 1 and computing the inverse of T, like so:

U=-(inv(T)/tau).

My notation is essentially the same as yours in post #1, except that what you call N0 I call $\mathbf{u}$ and what you call n0 I call $\mathbf{e}$ (and I write $\mathbf{T}^{-1}$ instead of Inv(T)). Otherwise, there is no difference at all!

Look at the formula I wrote: it $\mathbf{u} = - r \mathbf{T}^{-1} \mathbf{e}$. This is using $\tau = 1/r$ is it not? For the case of your specific $T$ you take $r = 1$ and so $\tau = 1/1$, and you really have no choice: any other value of $\tau$ would give incorrect results.

 

[Schwarzschild90]

My notation is essentially the same as yours in post #1, except that what you call N0 I call $\mathbf{u}$ and what you call n0 I call $\mathbf{e}$ (and I write $\mathbf{T}^{-1}$ instead of Inv(T)). Otherwise, there is no difference at all!

Look at the formula I wrote: it $\mathbf{u} = - r \mathbf{T}^{-1} \mathbf{e}$. This is using $\tau = 1/r$ is it not? For the case of your specific $T$ you take $r = 1$ and so $\tau = 1/1$, and you really have no choice: any other value of $\tau$ would give incorrect results.

I figured as much, but I wanted to know for sure.

I set tau=1 for simplicity, as I thought it simplified the expression, but I also see there's a rigorous mathematical reason to do so.

 

[Schwarzschild90]

But you determine the first column of u, while the professor said that only the first row is of interest.

 

[Ray Vickson]

But you determine the first column of u, while the professor said that only the first row is of interest.

It does not matter in this case because the first row of Inv(T) equals the first column.

Anyway, I much prefer to avoid matrix inverses altogether. What you have is an equation-solving problem, and using a matrix inverse is one of the worst ways to do it (although is often used nevertheless). If your 4x4 matrix T has first row [-2r,r,0,0] and last row [0,0,r,-2r], the equations you need to solve for the ruin probabilities $u_1,u_2,u_3,u_4$ are:
$$\begin{array}{rcl}
0 = r - 2r u_1 + r u_2 &\Rightarrow& u_1 = \frac{1}{2} + \frac{1}{2} u_2 \\
0 = r u_1 - 2r u_2 + u_3 &\Rightarrow& u_2 = \frac{1}{2} u_1 + \frac{1}{2} u_3 \\
0 = r u_2 -2r u_3 + r u_4 &\Rightarrow&u_3 = \frac{1}{2} u_2 + \frac{1}{2} u_4 \\
0 = r u_3 - 2r u_4 & \Rightarrow& u_4 = \frac{1}{2} u_3
\end{array}
$$
That's it: just solve those equations. You will get $(u_1,u_2,u_3,u_4) = (4/5, \, 3/5, \, 2/5, \, 1/5)$ for any $r > 0$.

 

[haruspex]

I set tau=1 for simplicity, as I thought it simplified the expression, but I also see there's a rigorous mathematical reason to do so.

I'd go a bit further than that. Tau simply should not appear in that equation. There must be a flaw in the algebra lesding to it.

 

[Schwarzschild90]

It does not matter in this case because the first row of Inv(T) equals the first column.

Anyway, I much prefer to avoid matrix inverses altogether. What you have is an equation-solving problem, and using a matrix inverse is one of the worst ways to do it (although is often used nevertheless). If your 4x4 matrix T has first row [-2r,r,0,0] and last row [0,0,r,-2r], the equations you need to solve for the ruin probabilities $u_1,u_2,u_3,u_4$ are:
$$\begin{array}{rcl}
0 = r - 2r u_1 + r u_2 &\Rightarrow& u_1 = \frac{1}{2} + \frac{1}{2} u_2 \\
0 = r u_1 - 2r u_2 + u_3 &\Rightarrow& u_2 = \frac{1}{2} u_1 + \frac{1}{2} u_3 \\
0 = r u_2 -2r u_3 + r u_4 &\Rightarrow&u_3 = \frac{1}{2} u_2 + \frac{1}{2} u_4 \\
0 = r u_3 - 2r u_4 & \Rightarrow& u_4 = \frac{1}{2} u_3
\end{array}
$$
That's it: just solve those equations. You will get $(u_1,u_2,u_3,u_4) = (4/5, \, 3/5, \, 2/5, \, 1/5)$ for any $r > 0$.

But does r > 0 not imply that tau is likewise greater?

Does it hold for a 100 x 100 matrix as well?

A plot of the ultimate probabilities show a linear relationship between matrix elements and ultimate probabilities.

I'd go a bit further than that. Tau simply should not appear in that equation. There must be a flaw in the algebra lesding to it.

If only one is the correct value to pick for tau, then it should not appear in the equation. We're better off absorbing the variable into the expression.

 

[haruspex]

If only one is the correct value to pick for tau, then it should not appear in the equation. We're better off absorbing the variable into the expression.

I feel it is more than that - it is a dimensionality issue. If tau represents a rate it should have a dimension, like time^-1, which would give the expression in the equation for probability a dimension. But without seeing the derivation I cannot be sure.

 

[Schwarzschild90]

I feel it is more than that - it is a dimensionality issue. If tau represents a rate it should have a dimension, like time^-1, which would give the expression in the equation for probability a dimension. But without seeing the derivation I cannot be sure.

I thought about that, but decided to take a leap of faith and take tau = 1.

With tau = 1, then a 100 x 100 matrix presents me with 99,01% chance of ultimately ruining my opponent, as expected.

I present a plot of U(l) versus position l.

 

[haruspex]

I thought about that, but decided to take a leap of faith and take tau = 1.

I am not sure you are grasping my point.
Suppose I wanted an equation for the speed of a car and came up with (engine rpm)x(gear ratio)x(wheel radius)x(some constant)/(number of steering wheels). Setting the number of steering wheels to 1 may give the right answer, but that does not mean it is the right value to plug in. The number of steering wheels should not have featured in the equation in the first place.

 

[Schwarzschild90]

I am not sure you are grasping my point.
Suppose I wanted an equation for the speed of a car and came up with (engine rpm)x(gear ratio)x(wheel radius)x(some constant)/(number of steering wheels). Setting the number of steering wheels to 1 may give the right answer, but that does not mean it is the right value to plug in. The number of steering wheels should not have featured in the equation in the first place.

I see your point.

It does not matter in this case because the first row of Inv(T) equals the first column.

Anyway, I much prefer to avoid matrix inverses altogether. What you have is an equation-solving problem, and using a matrix inverse is one of the worst ways to do it (although is often used nevertheless). If your 4x4 matrix T has first row [-2r,r,0,0] and last row [0,0,r,-2r], the equations you need to solve for the ruin probabilities $u_1,u_2,u_3,u_4$ are:
$$\begin{array}{rcl}
0 = r - 2r u_1 + r u_2 &\Rightarrow& u_1 = \frac{1}{2} + \frac{1}{2} u_2 \\
0 = r u_1 - 2r u_2 + u_3 &\Rightarrow& u_2 = \frac{1}{2} u_1 + \frac{1}{2} u_3 \\
0 = r u_2 -2r u_3 + r u_4 &\Rightarrow&u_3 = \frac{1}{2} u_2 + \frac{1}{2} u_4 \\
0 = r u_3 - 2r u_4 & \Rightarrow& u_4 = \frac{1}{2} u_3
\end{array}
$$
That's it: just solve those equations. You will get $(u_1,u_2,u_3,u_4) = (4/5, \, 3/5, \, 2/5, \, 1/5)$ for any $r > 0$.

For a 4 x 4 matrix, I would expect a 4/5% probability of winning if I have 4 coins and my opponent has one?

 

[Schwarzschild90]

We have that O(j) for k = 1.. M-1 is a column matrix, but does this imply that O(j) is a row vector with matrix elements (k,j)=(1,1), (1,2), (1,3), (1,4)?