We are attempting to find the average number of steps in a certain mathematical game. Let us define a function which represents the average number of steps to completion. We will have this function be called T, for time, and have T(x) be the expected number of remaining steps at the position x. A review of the formal rules of the game and the definition of this function:
n \in \mathbb{N} \\[4pt] \operatorname f : \mathbb R, \mathbb Q \to \mathbb Q \\[8pt] \operatorname f {(p, x)} = \begin{cases} p > x : x-\frac1{2n} \\[4pt] p < x : x+\frac1{2n} \\[4pt] p = x : x \end{cases} \\[48pt] \operatorname T: \mathbb Q \to \mathbb N \\[4pt] \operatorname T(0) = \operatorname T(1) = 0 \\[12pt] \operatorname T(x) = x\operatorname T\left(x-\frac1{2n}\right)\ + \ (1-x)\operatorname T\left(x+\frac1{2n}\right)\ +\ 1We can rephrase this equation to express T(x+1/2n) – T(x) in terms of T(x) – T(x-1/2n), a much more use-full equation. Consider a T(-1/2n). This extends the space of T beyond that which actually represents f–allowing us to find T(1/2n). T(-1/2n) = -1, so T(0) – T(-1/2n) = 1. Using the equation below: T(1/2n) – T(0) is 2n/(2n-1) + 1/(2n-1) = (2n+1)/(2n-1). This may then be extended further: T(1/n) – T(1/2n) is (2n(2n-1) + 2(2n-0) + 2) / (2n-2)(2n-1). Can we go for a formula in pi and sigma notation: yes. What about a polynomial formula, or at least something less hard to calculate? NO.
\operatorname T(x)-\operatorname T\left(x-\frac1{2n}\right)\ =\ \frac1{1-x} \ +\ \frac x{1-x}\left(\operatorname T\left(x+\frac1{2n}\right) – \operatorname T(x)\right)\\[24pt] \operatorname T(x) – \operatorname T\left(x-\frac1{2n}\right)\ =\ \left((2nx)!+\sum_{k=0}^{2nx}{(2nx)!(2n-k)\over k!}\right)\div \left(\prod_{l=1}^{2nx}2n-l\right)And finally, we can summate T(k/2n) – T((k-1)/2n) for all k from 1 to n. The answer is, therefore, the following huge formula!
\Large {\Huge\sum_{k=1}^n}\left((2nk)!+\sum_{l=0}^{2nk}{(2nk)!(2n-l)\over l!}\right) \div\left(\prod_{m=1}^{2nk}2n-m\right)