Average case analysis of Gosper's algorithm for a class of urn model inputs (Q818669)

Given a sequence \(t_k\), Gosper's algorithm finds a hypergeometric term antidifference \(z_k\), satisfying therefore \(z_{k+1}-z_k=t_k\), if it exists. The sequence \(z_k\) is called a hypergeometric term if \(z_{k+1}/z_k\) is a rational function. It turns out that if \(z_k\) is a hypergeometric term, then so is the input \(t_k\), and \(z_k=y_k\,t_k\) for a rational function \(y_k\). Hence Gosper's algorithm boils down to compute the rational function \(y_k\). In his dissertation \textit{Jürgen Gerhard} [Modular Algorithms in Symbolic Summation and Symbolic Integration, LNCS 3218] presented a worst case analysis for a modular version of Gosper's algorithm. In the present paper an average case analysis for the first part of Gosper's algorithm, namely the computation of the so-called Gosper form (however not the Gosper-Petkovsek form) of the rational function \(t_{k+1}/t_k=f_k/g_k=a_k/b_k\cdot c_{k+1}/c_k, f_k,g_k,a_k,b_k,c_k\) polynomials, is presented. Insofar, the current work complements Gerhard's work. In the paper it is assumed that \(\deg(f_k)=\deg(g_k)=n\) and that \(f_k\) and \(g_k\) have only rational zeros. Several urn models are considered, model \textbf{T} assuming that the input \(t_k\) is rational, and model \textbf{R} assuming that the input is given by \(f_k\) and \(g_k\) with randomly chosen linear factors. One of the main results, Theorem 12, concerns model \textbf{R} under the additional assumption that the linear factors of \(f_k\) and \(g_k\) are chosen uniformly as multisets: Let \(N=\max\{j\in{\mathbb N}_{\geq 0}|\gcd(f_k,g_{k+j})\neq 1\}\) denote the dispersion of \(f_k\) and \(g_k\), given here in terms of the random input factors, then asymptotically for \(n,N\rightarrow\infty\) one has for the expected value \[ E(\deg c_k) \sim {2\over 3\sqrt{\pi n}}(n+N)^{3/2}\sqrt N\;. \] Note that for \(n=N\) this yields \(O(N^{3/2})\).