Let $\left\{B_n\right\}_{n=0}^{\infty}$ be an i.i.d. process, such that, for every $n\in\mathbb{N}\cup{0}$:
$$\mathbb{P}[B_n=-1]=p \\ \mathbb{P}[B_n=+1]=q$$
Such that $p+q=1$. Let $\left\{X_n\right\}_{n=0}^\infty\subset\mathbb{S}$ be a markov chain, where $\mathbb{S}=\left\{i\right\}_{i=0}^K=\left\{0,1,...,K\right\}$ for some $K\in\mathbb{N}$, such that:
$$X_n=X_{n-1}+B_{n}\qquad0<X_{n-1}<K \\ X_n=X_{n-1}\qquad\qquad \ \ X_{n-1}\in\left\{0,K\right\}$$
I drew the diagram of the process in order to see things more clearly:
Define the probabilty $\rho_{ij}$ for every $i,j\in\mathbb{S}\setminus\left\{0,K\right\}$ such that:
$$\rho_{ij}\triangleq\mathbb{P}[\exists n>0 : X_n=j \mid X_0=i]$$
(In other words, $\rho_{ij}$ is the probability that the chain would somewhen visit the state {$j$}, given that the initial state is {$i$}. It is clear that if the initial state is $X_0=0$, then it is certain that the chain would visit the state {$0$} again, but never any other state. In other words, $\rho_{0k}=\delta[k]$ where $\delta$ is the delta of kronecker.)
It is given that $p=q=1/2$. Find $\rho_{ij}$ for every $i,j\in\mathbb{S}\setminus\left\{0,K\right\}$.
I feel like I've tried everything. It seems that doing this straightforward is impossible, since the total number of paths that must be considered is too large. I understand that the expression would be different for the three cases $i=j,i>j$ and $i<j$. Finding $\rho_{ii}$ shouldn't be a problem if I knew $\rho_{ij}$ for $i>j$ and $i<j$, since:
$$\rho_{ii}=p\rho_{i-1,i}+q\rho_{i+1,i}=[\rho_{i-1,i}+\rho_{i+1,i}]/2$$
And obviously $i>i-1$ & $i<i+1$.
Thank you very much!
A suggestion: Merge states $1$ and $2$, and also $K-1$ and $K$. Find the transition matrix $P_{(K-2)\times (K-2)}$ for the new $(K-2)$-state Markov chain, which the elements of $P^n$ gives you the transition probabilities for states $3$ to $K-2$. A conditional probability would yield the desired result for the inner states of the two merged states.