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

[Psyche]

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.

[Psyche]

guys i was so secretly confident that you'd have this solved for me by now

[Psyche]

ok ok ok here is some help

i asked this on stackexchange once and got these answers:
http://math.stackexchange.com/questions ... th-n-given

my problem is that i can't understand them!
or at least even though i think i understand them when i try to apply this example to some test problems things don't work out

either solve the problem your own way or help me understand this/these solutions and ill be your bubble box bitch forever

[KuroiXHF]

I feel like you want us to do your homework for you.

[Psyche]

i am beyond homework rn msr kuroixhf

[Kublai Khan]

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

Hit the bubble box with a sledgehammer until it's destroyed. Then you can reliably predict that the expected frequency of each color is nil no matter what transition matrix or sequence length is inputted.

[Psyche]

ur destroying my faith in humanity right now kublai khan do you know that
it's not the bubble box you're sledging it is my soul

[Kublai Khan]

I'm okay with that

[DeathRowKitty]

Diagonalize the transpose of the matrix.

[Cheery Dog]

x

[Psyche]

Diagonalize the transpose of the matrix.

haha and then what ;)

[DeathRowKitty]

Find a vector for the distribution of the nth color and hope you can find a nice way to sum it over n. If that doesn't work and you don't need an exact result, sum the small terms manually and approximate the larger terms using the steady-state solution. It should converge pretty quickly, I think.

If you can't diagonalize, try Psyche normal form instead.

[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.

[DeathRowKitty]

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.

Yeah, this is the point of diagonalizing it.

(I mentioned transpose because I have an irrational dislike of row vectors)

[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?

[Kappy]

After a lot of thought, I have solved this problem.

Spoiler: Answer

Stop counting bubbles and get a life.

[Psyche]

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

im generating/ordering stimuli for an experiment on statistical learning

[Psyche]

i know what markov chains are i was just trying to dumb the problem down a little

[Psyche]

not sure i understand all the lingo but having 3+ different explanations should be enough for me to connect the dots

[mole]

The steady states are the eigenvectors of the transition matrix.

[Claus]

write a 10 line python code to simulate the bubble machine. Run 100 simulations, calculate the confidence interval for the frequencies.