{"entities":{"Q818669":{"pageid":820517,"ns":120,"title":"Item:Q818669","lastrevid":64570977,"modified":"2026-04-11T20:47:18Z","type":"item","id":"Q818669","labels":{"en":{"language":"en","value":"Average case analysis of Gosper's algorithm for a class of urn model inputs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5013752"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q818669$168542F3-07D3-4293-9E85-BD2B4E4B9AEA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8dd832a2bbc57bc3f42cabcff694ac99bb4ea75a","datavalue":{"value":{"text":"Average case analysis of Gosper's algorithm for a class of urn model inputs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q818669$9C8A8FDD-311A-4BB8-9059-915BABEF8B2A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"93b1848902d68241c57457992ab500b8b0bfb613","datavalue":{"value":"1092.33019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q818669$86AA9D54-8D6B-4CA4-BF50-BA99D2F13124","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c5832f8876614de1887b6fff71a1066143db327e","datavalue":{"value":{"entity-type":"item","numeric-id":786129,"id":"Q786129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q818669$BAE8F7E0-6F89-498D-B2B7-94539E9F22EF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q818669$61393169-D840-4B0A-9904-C64E280D4564","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"772948f2487b02c578217863cb0a65a1011ee253","datavalue":{"value":{"time":"+2006-03-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q818669$B780ACF0-7B87-40B7-9993-C12C8AB0382A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d7f1cdccd904d216922b0e30b2b919c9642682f3","datavalue":{"value":"http://hdl.handle.net/2027.42/41350","type":"string"},"datatype":"url"},"type":"statement","id":"Q818669$B5E4FF19-7020-4C45-AAD7-E4FB337F85C9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"574e59646afa7bf408b427be10225b097ef9c014","datavalue":{"value":"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\u00fcrgen 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})\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q818669$4B377F23-D201-49D4-B16E-3C6078FCB4DE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"42de9321ec9bffe9bd1dcf8c8689a504914f3754","datavalue":{"value":"33F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q818669$3F1E5A6D-E697-4828-B61F-2F9F32EE992B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q818669$D9D0EA26-72D1-4C30-ABFB-034C032BB34B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"322dd4d0598d573dc53c41c14bf73d75c6ed1486","datavalue":{"value":"5013752","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q818669$93100C9B-9B10-4FF8-BA47-65AA99DC1DF1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a2adb78a7e9d0ee11c60a036ba2de46bd0d1a1e","datavalue":{"value":"Gosper's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q818669$956247F7-F147-4FA4-96DA-5AE28C82FFB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b18cc0ac017dfb6f9afae2037f2fd9465f70379b","datavalue":{"value":"hypergeometric terms","type":"string"},"datatype":"string"},"type":"statement","id":"Q818669$C686279C-FF76-4F45-B0B7-98FF7BC7BDE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4780b02cfc7bc35a586062e3271a9f52fa94f067","datavalue":{"value":"complexity analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q818669$EB2139C8-A19A-4A48-9DDF-97D7ABBC14CF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c76cd4b8599ad1bdedd7f6dabdc2469da181f44d","datavalue":{"value":{"entity-type":"item","numeric-id":214104,"id":"Q214104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q818669$49D7AAF9-FE40-4645-92B3-FA954AF6BC1B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q818669$1A154503-A7DA-42EE-9570-BB981EA5E501","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f9223adb1148b6bb77dfb35b7a893bae9bc1626b","datavalue":{"value":"W2033829327","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q818669$40E41671-D083-4DBA-9027-53DCCC15CF3C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f2f0caaa642dab260bfc60f5a39653d7085ea83b","datavalue":{"value":"10.1007/S00453-005-1173-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q818669$D8F84BA1-BED7-4F52-A11F-10A195BF989C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69ba8e57a61ce7ef69952244e232bed645a1bf79","datavalue":{"value":{"entity-type":"item","numeric-id":4651811,"id":"Q4651811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed3eb32d6a854c5bd4ea81a5cc88a5ad39502f55","datavalue":{"value":{"amount":"+0.7798581719398499","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q818669$C1059E43-BF8F-4469-9E7A-9E9E82EB2E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08291d7e6ae5916de0c1989e41839cd2ae5a80ed","datavalue":{"value":{"entity-type":"item","numeric-id":1174718,"id":"Q1174718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"044a33d453df23b6faa7fee9eb92af3ada33829c","datavalue":{"value":{"amount":"+0.7569331526756287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q818669$DF94532A-36C2-4F4B-95CD-79C4DBD32245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36e5bbf3243f2ffaa4431e540162f08f8b657b6c","datavalue":{"value":{"entity-type":"item","numeric-id":1379160,"id":"Q1379160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"044a33d453df23b6faa7fee9eb92af3ada33829c","datavalue":{"value":{"amount":"+0.7569331526756287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q818669$5282E5D8-F9D9-42EA-8093-33D43D7A8F9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60cf872760353686642f7d73250b50989e8bd566","datavalue":{"value":{"entity-type":"item","numeric-id":1314432,"id":"Q1314432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a01a36e8646ff94b61f3d490d032182b9cfd169c","datavalue":{"value":{"amount":"+0.742094099521637","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q818669$C5D7F2B5-F01D-4F5A-8658-DBC5274ECD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9182a6925519ac618c6a3e3422093f1e12a2d0f8","datavalue":{"value":{"entity-type":"item","numeric-id":5204317,"id":"Q5204317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c3252a2b8a326418977a98acb717617f223d640","datavalue":{"value":{"amount":"+0.7309010028839111","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q818669$609CDC05-0554-4F2F-9508-CF35689ABF5E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Average case analysis of Gosper's algorithm for a class of urn model inputs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Average_case_analysis_of_Gosper%27s_algorithm_for_a_class_of_urn_model_inputs"}}}}}