At the time $n=0$ we place $N$ balls in $k$ urns and change this in each step as follows: We choose one of the balls evenly distributed at random (meaning: each ball is chosen with a probability of $\frac{1}{N}$) and place it in an urn that is also randomly selected (meaning: every urn is chosen with probability $\frac{1}{k}$). Let $(X_n)_{n\in\mathbb{N}_0}$ be the stochastic process that describes the number of balls in the first urn after $n$ steps and $(\mathcal{F}_n)_{n\in\mathbb{N}_0}$ the natural Filtration of the stochastic process (meaning: $\mathcal{F}_n=\sigma(X_1,\ldots,X_n)$ for all $n\in\mathbb{N}$).
- Try to express $E[X_n|\mathcal{F}_n]$ using $X_n$.
- Set $Z_n:=a_nX_n+b_n$. Find $(a_n)_{n\in\mathbb{N}_0}$ and $(b_n)_{n\in\mathbb{N}_0}$ such that $(Z_n)_{n\in\mathbb{N}_0}$ defines a Martingale.
It is mentioned as explicit example for this question I solved here. So it makes sense that $E[X_n|\mathcal{F}_n]$ will be of the form $E[X_n|\mathcal{F}_n]=u_nY_n+v_n$ for some real-valued sequences $(u_n)_{n\in\mathbb{N}}$ and $(v_n)_{n\in\mathbb{N}}$. With that solution in mind Part 2 is quite simple, I just need to find $u_n$ and $v_n$ and the solution follows directly. So let us get to the point of finding $u_n$ and $v_n$:
Surely $P(X_0=m)=(\frac{1}{k})^m\cdot(1-\frac{1}{k})^{N-m}$ for $m\in\{0,1,\ldots,n\}$. Now the probability of taking out a ball ...
- ... of the first urn and putting it back into the first urn is $\frac{X_n}{N}\cdot\frac{1}{k}$.
- ... of the first urn and putting it into one of the other urns is $\frac{X_n}{N}\cdot(1-\frac{1}{k})$.
- ... not form the first urn and putting it in the first urn is $(1-\frac{X_n}{N})\cdot\frac{1}{k}$.
- ... not form the first urn and putting it not in the first urn is $(1-\frac{X_n}{N})\cdot(1-\frac{X_n}{N})$.
This brings us to the conclusion that:
$$\begin{cases} & P(X_{n+1}=X_n)=(\frac{X_n}{N}\cdot\frac{1}{k})+(1-\frac{X_n}{N})\cdot(1-\frac{X_n}{N})\\ & P(X_{n+1}=X_n-1)=\frac{X_n}{N}\cdot(1-\frac{1}{k})\\ & P(X_{n+1}=X_n+1)=(1-\frac{X_n}{N})\cdot\frac{1}{k} \end{cases}$$
Now I am struggling to define $P(X_n=m)$ in general (do i even need it?). Somehow I think that I am on a wrong track.
Any assistance or thoughts how to properly approach this problem would be much appreciated.
Edit: After correcting my mistakes i get the desired form I mentioned at the beginning:
$$\begin{align}E[X_{n+1}|\mathcal{F}_n]&=(X_{n}+1)P(X_{n+1}=X_n+1)+X_{n}P(X_{n+1}=X_n)\\&\hspace{5em}+(X_{n}-1)P(X_{n+1}=X_n-1)\\&=X_n\underbrace{[P(X_{n+1}=X_n+1) + P(X_{n+1}=X_n) + P(X_{n+1}=X_n-1)]}_{\substack{=1}} \\&\hspace{5em}+ P(X_{n+1}=X_n+1) - P(X_{n+1}=X_n-1) \\&= X_n + P(X_{n+1}=X_n+1) - P(X_{n+1}=X_n-1)\\&=\underbrace{\frac{1}{Nk}(Nk+k-2)}_{\substack{=:u_n}}\cdot X_n+\underbrace{\frac{1}{k}}_{\substack{=:v_n}}\end{align}$$
... which means that Part 2 follows with the statement here.
You don't need $P(X_n = m)$ here because we are just looking for $\mathbb{E}[X_{n+1}|\mathcal F_n]$. I think you made a slight mistake in some of those probabilities, though. Since we are selecting the ball to move uniformly across all of the balls instead of all of the urns, the probability a ball from the first urn is selected is actually $\frac{X_n}{N}$ so $\mathbb{P}(X_{n+1}=X_n +1 | \mathcal F_n) = \left(1-\frac{X_n}{N}\right) \cdot \frac 1k $ and $\mathbb{P}(X_{n+1}=X_n - 1 | \mathcal F_n) = \frac{X_n}{N} \cdot \left(1-\frac 1k\right)$