Context Question
Let $K_n$ be the complete graph on $n > 1$ vertices, undirected. Suppose the vertices are enumerated $v_1,\dots,v_n$, and you start at $v_1$. We have a random walk of $k$ steps in $K_n$ as follows: at stage $j$, move from $v$ to any distinct vertex adjacent to $v$ (which for $K_n$ is any vertex $\{v_1,\dots,v_n\} – \{v\}$ of course), with equal probability of choosing any of the other $n-1$ vertices. What is the probability that on our last move we arrive back at $v_1$? Naively, we might say that, since all vertices are pairwise adjacent, the answer is $P = \frac{1}{n-1}$ for $ k > 1$. But what if we end up on vertex $v_1$ at stage $k -1$? We would be forced to end on a vertex other than $v_1$. Moreover, cleary $P = 0$ for $k = 1$.
Puzzle
You are on a strange archipelago consisting of $n$ small islands linked by identical, unstable bridges. There is exactly one bridge between any two such islands, but these bridges are so unstable that they collapse upon being crossed (think of deleting an edge in $K_n$ after it's traversed). Moreover, the islands are far enough apart to where they can't be seen from one another, so you choose any of the remaining bridges to cross with equal probability. If your adventure consists of $k$ stages, each stage [trying to] cross a bridge, what is the probability that you end up at your starting point (in terms of $n$ and $k$)?
Remarks and Thoughts:
We know that $K_n$ has $\frac{1}{2}n(n-1)$ edges, so we may as well bound $k$ by this number for our puzzle. Moreover, we may become "trapped" prematurely (ending on an island and collapsing it's last bridge in the process) before actually taking $k$ steps. So we'll interpret $k$ steps as "always taking a step when possible, up to $k$ times". Another thing to note is that again $P = 0$ when $k = 1$, so we'll assume $k > 1$. When trying to think of a solution to this problem, my first thoughts are to consider simple cases. For $n = 3$, we have the triangle $K_3$, for which we will always return to the start after $k > 1$ steps. This is not true for $K_4$. Moreover, for $n \geq 4$, we see that $P = 0$ for $k \leq 2$. Any insight or partial answers are appreciated! I will update the question with any progress I make.
Best Answer
I'll do the first question . . .
For positive integers $n,k$ with $n > 1$, let $f(n,k)$ be the probability that a $k$-step random walk on $K_n$ ends at the starting vertex.
Then we have the recursion $$ f(n,k) = \begin{cases} \;0&\text{if}\;\,k=1\\[4pt] {\Large{\frac{1-f(n,k-1)}{n-1}}}&\text{if}\;\,k>1\\ \end{cases} $$ Explanation:
For $k > 1$, to be at the starting vertex after $k$ steps, one needs be at a vertex other than the starting vertex after $k-1$ steps, probability $1-f(n,k-1)$, followed by a move to the starting vertex, probability ${\large{\frac{1}{n-1}}}$.
Examining the data for small values of $n,k$ a pattern becomes evident, suggesting the closed form $$ f(n,k) = \frac {1-\left(-{\Large{\frac{1}{n-1}}}\right)^{\large{k-1}}} {n} $$ which can then be proved by a straightforward induction on $k$.