A robot randomly walks backward and forward, with probability $p$ and $1-p$ respectively. Let $S_i$ denote the direction he walks on the $i$-th step. Are $S_1$ and $S_2$ independent? What assumptions are you making? Are they conditionally independent?
I tried to approach this problem by using a simple tree diagram: knowing what direction the robot moved in the first step does not give us any new information about the where the robot might move in the second step; this means that they are independent, right? It seems to me that there's more going on here.
$S_1$ and $S_2$ are indeed independent. The probability of moving backward on $S_1$ is exactly $p$. The probability of moving backward on $S_2$ is also $p$. $p$ is a constant. $S_1$ and $S_2$ depend only on the constant $p$. They are independent.
$S_1$ and $S_2$ depending on the same constant $p$ does not make $S_1$ and $S_2$ conditionally independent. $S_1$ and $S_2$ would only be conditionally independent if they dependended on the same randomly-determined number. $S_1$ and $S_2$ are not conditionally independent because $p$ is not a randomly-determined variable. $p$ a known constant. If $p$ were randomly determined by the robot when you turn the robot on then $S_1$ and $S_2$ would be conditionally independent. This is not the case.
I don't understand your question "What assumptions are you making?" The independence of $S_1$ and $S_2$ isn't an assumption. It's the definition of a random walk. A random walk is defined as a situation where every step is independent of every other step.
There isn't anything else going on here. $S_1$ and $S_2$ are as independent of each other as two identical coins. They have the same probability of moving backward (or flipping heads), but that does not make them dependent.