Expected number of users reaching a particular state

102 Views Asked by At

I have a problem to solve where N users chooses value with uniform distribution between 3 and 7 initially. Then every second, every user decrements its value (like if 7 is chosen 7, then it becomes 6, if 3, then it becomes 2).

I want to calculate expected number of users reaching state when they have the value of 1.

I have solved for getting probability $P_1$ to be in state with value of 1 using Markov chain, but how can I know the number of users every second that reach the value of 1 ? After getting to the value of 1 each user again chooses a number between 3 and 7 randomly and process continues.

1

There are 1 best solutions below

3
On BEST ANSWER

It is not at all clear from your following statement:

I want to calculate expected number of users reaching state when they have the value of 1.

exactly what it is that you want to calculate. Given the scenario you have described, however, the state of every user can be represented by a $7$-state Markov chain with transition matrix $$ P=\pmatrix{0&0&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}\\ 1&0&0&0&0&0&0\\ 0&1&0&0&0&0&0\\ 0&0&1&0&0&0&0\\ 0&0&0&1&0&0&0\\ 0&0&0&0&1&0&0\\ 0&0&0&0&0&1&0}\ . $$ and initial distribution $$ \pi_1=\pmatrix{0&0&\frac{1}{5} &\frac{1}{5} &\frac{1}{5} &\frac{1}{5} &\frac{1}{5}}\ . $$ The distribution $\ \pi_t\ $ of a user's state at time $\ t\ $ is given by $$ \pi_t=\pi_1P^{t-1}\ . $$ If there are $\ N\ $ users at the start, then the expected number $\ e_{tj}\ $ of users in state $\ j\ $ at time $\ t\ $ is given by $$ e_{tj}=N\pi_{tj}\ . $$ If you want an explicit formula for $\ \pi_{t1}\ $, you can get it in terms of the eigenvalues of $\ P\ $, which are the roots of its characteristic equation: $$ x^7-\frac{1}{5}\left(x^4+x^3+x^2+x+1\right)=0\ . $$ The stationary distribution of the chain is $$ \pi_\infty=\pmatrix{\frac{1}{5} &\frac{1}{5} &\frac{1}{5} &\frac{4}{25} &\frac{3}{25} &\frac{2}{25} &\frac{1}{25}}\ , $$ so for sufficiently large $\ t\ $, the expected number of users in sate $\ 1\ $ will be $$ N\pi_{t1}\approx \frac{N}{5}\ . $$