solve this math problem and ill be ur bubble box bitch 4ever

[Rob14]

i dont think u can tbh

A MAGIC BUBBLE BOX is releasing multicolored bubbles into the world at a breakneck pace
it can send out red bubbles, orange bubbles, blue bubbles - all the colors, really

best of all, people can control which and in what pattern colored bubbles are released from the box by giving it three simple instructions:
1. an ordered list of colors to be released
2. a total number of bubbles to be released until the box stops
3. a transition matrix that dictates for each color the probability distribution of colors that will follow it!

here's an example of a transition matrix for a two-color bubble box output:
R B
R .6 .4
B .5 .5

With these instructions, R will follow occurrences of R 60% of the time. 40% of the time, though, B will happen instead!
If the last bubble released was B, though, there's a 50% chance that R will be released next and a 50% chance that B will be released next!

If the transition matrix were
R B
R .5 .5
B .5 .5
Then every color would be equiprobable at any given moment. You can expect a sequence of bubbles of any length to be, on average, about 50% R and 50% B.

But a matrix like the first one I showed you might be a bit more complicated to understand. Furthermore, some matrices might involve many more than just two colors. In fact, most magic bubble box bros work with 8 colors at a time!

Offer me

a reliable strategy for calculating the expected frequency of each color given a transition matrix and sequence length

and i will be your bubble box bitch forever.

Not enough information. What color starts and/or what is the probabilities for the first color?

[Rob14]

Rather than your example, I'm using the following example/terminology, because it's closer to what economics stuff I know that relates to this problem.

Consider a situation where the economy can be in multiple states. There could be any (finite) number of possible states. One example would be {-2% growth, 0% growth, 1% growth, 5% growth}, but it could be any number of states and the states could represent anything.

Case A) Finite problem. You're given a starting state, sequence length, and transition matrix. Call the starting state

j

, the sequence length

n

, and the transition matrix

A

. Note that

A

is of dimension

n

x

n

.

Construct a 1x

n

vector that has the value of 1 in the

j

-th place and 0 in all other places. This is called the state vector, and it represents the state that your economy starts in. If our starting state was 0% growth, our state vector would be (0, 1, 0, 0). Call this state vector

J

.

If we wanted to get the probabilities of growth in next period, we would multiply

J

*

A

. You'll need to write this out to understand it, but multiplying those matrices gets us a 1x

n

vector of the form {

Pj

1,

Pj

2, ... ,

Pjn

} where

Pji

is the probability of state

i

occurring if state

j

occurred last period.

Similarly, we can get the probabilities of any given state appearing in period

k

given

only the initial state, j

. Do this by multiplying

J

*

A

^

k

. You need to calculate that for

k

= 1, ...,

n

to find the probabilities of each state in each period. From there, you can get the expected frequency (number of times a given state appears over the course of the sequence length) by adding up all the probabilities for each state.

i.e. If there's a 50% chance of A in period 1 and an 80% chance of A in period 2 (given only state j, not what happens in period 1), then you expect to see A in 1.3 periods on average if you ran the system infinite times.

[Rob14]

Typing up the infinite case now, since that's more interesting.

[Rob14]

Case B) Infinite problem. You're given only the transition matrix and asked to find the probabilities of each state that the economy/system will converge to.

In this problem, expected frequency has no meaning, since it's infinite. Instead, the meaningful outcome is a "steady state", meaning a set of probabilities a system will converge to given infinite periods. There's two ways to find this.

You could plug in any starting state and compute

J

*

A

^

k

as

k

goes to infinity. This will give you a very good approximation of the steady state.

Alternatively, you could solve for the set of probabilities that would be unaffected by the transition matrix. If you're in the steady state, that means that applying the transition matrix changes nothing. If this weren't the case, then the system wouldn't be converging to that set of probabilities. So you're looking for a set of probabilities

P

such that:

P

*

A

=

P

You can see how this is "steady"; applying the transition matrix to it an infinite number of times would still result in the same set of probabilities.

Then find

P

. You'll need to multiply out

P

*

A

using

P

={p1, p2, ... , pn} and then solve a system of equations to find p1, ... , pn.

[Rob14]

Also, if you're looking for more materials on this subject, you should be searching for Markov chains.

[Rob14]

What class/subject is this for, by the way?