{"entities":{"Q1108734":{"pageid":1119483,"ns":120,"title":"Item:Q1108734","lastrevid":66730617,"modified":"2026-04-12T12:29:28Z","type":"item","id":"Q1108734","labels":{"en":{"language":"en","value":"Approximating functions by their Poisson transform"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068148"}},"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":"Q1108734$8B6E5525-E4DA-4047-8170-49B772F18867","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"41a31ac90400b68613a1c48beb88d62d00aa7854","datavalue":{"value":{"text":"Approximating functions by their Poisson transform","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108734$46F1DA19-D43D-4817-8D0F-4AF7B0E95B10","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d6a5da9f4b6921804cf4ae2ec3d62467794312e","datavalue":{"value":"0654.65012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108734$96AB630B-0DFB-456B-9EDB-0CE7DE2C846A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1b96d40e8fa0c37c0e9aefadf1580d241ae0951c","datavalue":{"value":"10.1016/0020-0190(86)90111-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108734$5236D9D2-7F44-4402-8629-E8B76B3E8CC8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"698fecf7533e32e129fade113f8a29627f1228f8","datavalue":{"value":{"entity-type":"item","numeric-id":818122,"id":"Q818122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108734$CAF4C102-7C48-43AA-B16A-8389038F90E3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108734$714AE965-2A32-494A-96E4-D754DF4A3459","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1108734$DB7366B4-DB7E-4F67-BB96-6D500A08CDFB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ad1dba4f2e23223eec32bccca3d72bd36b44735a","datavalue":{"value":"When analyzing the performance of hashing algorithms, it is usually assumed that the hash function distributes the n keys randomly over the m table positions. In this exact filling model, all the m n possible arrangements are equally likely. In some cases, the analysis under this model becomes too difficult, and a Poisson filling model is used instead. Under this model, the number of keys falling in a given table slot is assumed to follow a Poisson distribution with parameter \\(\\alpha\\), independently of the number of keys falling elsewhere. The total number of keys, then, follows a Poisson distribution with parameter \\(m\\alpha\\).    The results obtained under the Poisson model are usually interpreted as an approximation of those one would obtain working under the exact model, with \\(n=m\\alpha\\). \\textit{G. H. Gonnet} and \\textit{J. I. Munro} [J. Algorithms 5, 451-470 (1984; Zbl 0606.68058)] showed that the relationship between these two models is a deeper one: a Poisson result can be interpreted as a transform of the exact one, and this transform can be inverted to recover the exact result. They also point out that the intuitive notion of using a Poisson result to approximate the corresponding exact result can be formalized, by means of an asymptotic expansion.    In this article, we provide a stronger version of their approximation theorem, together with a detailed proof. In particular, we find an explicit form for all the terms of the asymptotic expansion. We also prove that they satisfy a recurrence relation, which may be more useful for the actual computation of these terms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108734$1E0FC094-0C74-49D6-80E8-98889969563F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2afc8b14470e661c10725547661d94fa1583b792","datavalue":{"value":"65D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108734$DBF86533-3502-49D0-BDBF-03FFFDF08045","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"75cb3ed6fa5df310b65911778291e2a33e57f8db","datavalue":{"value":"4068148","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108734$0EA85DB3-673E-4007-A95E-9A8F51CE86E5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108734$C3806E2E-2E3A-4C93-9B07-522B11C063EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f6d650ff256815774c9639b6e18ede2e051449b","datavalue":{"value":"Poisson transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108734$2DE8AE95-6B72-4DAD-9BD1-B2FE35352273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"069b05783fde65f08779aaf0b59fde6582f99137","datavalue":{"value":"hashing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108734$95FECB6A-D110-4B81-B50F-E3BB843A4490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d7434c94d8497c4023b4d57fe7f52d8534410ed","datavalue":{"value":"exact filling model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108734$9209B2C8-FC0C-4D4B-BD4F-AD08CC47D2E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab9c2e806d047afb020eaf56d09a1d6315732f0a","datavalue":{"value":"Poisson filling model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108734$10E5920E-0C78-4AFF-8C01-16DE0A9B0C75","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":"Q1108734$F1989B35-54D7-4CA1-8C93-3491E48B0B10","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b086dea06b3b6a3d1dc86ad832a68351677410a0","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90111-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108734$20AAEF0A-00A7-41E6-B529-2FDB16677C30","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"376d058539a8b869bd48ab2724b7b81860af7b62","datavalue":{"value":"W2005879515","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108734$3B190938-459A-47B4-8D63-17AF64627228","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5abb06dcb698da6e8a6e190be6ec3ca3bf0c44b7","datavalue":{"value":{"entity-type":"item","numeric-id":1129001,"id":"Q1129001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b5b3cb63117b87d5e1a7fdca042e0b14b530d87","datavalue":{"value":{"amount":"+0.7987391948699951","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":"Q1108734$7A1F2A37-FF8E-43FA-A835-388368A9D27A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"320a7ac67dfb1e44291775502a29528d70a86ace","datavalue":{"value":{"entity-type":"item","numeric-id":3122915,"id":"Q3122915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c028ce02932d2d26ca2feae30ad5c7e7610861da","datavalue":{"value":{"amount":"+0.7814756035804749","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":"Q1108734$08A20888-EE5B-49EE-B918-65481CCA7995","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff3fe76c10697137184a29fc9c59330bcf44681e","datavalue":{"value":{"entity-type":"item","numeric-id":5485328,"id":"Q5485328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9e5e5e75601c54d86fed4e30bc10e66d0d6afd6","datavalue":{"value":{"amount":"+0.7684674263000488","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":"Q1108734$3F66215C-7D3E-4B69-8E9D-E553D7FED884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a767bd7cd728fea2bc3293b487aca9aabad71cf1","datavalue":{"value":{"entity-type":"item","numeric-id":2920841,"id":"Q2920841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b333448dd0553bad0381f2a69a6023075345d9a4","datavalue":{"value":{"amount":"+0.7421903610229492","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":"Q1108734$E61231A6-0252-48BB-866C-A159D7C6B381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c13cc11f097855d11996e13a619c98dab52e0930","datavalue":{"value":{"entity-type":"item","numeric-id":4894602,"id":"Q4894602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1074eaaa150c118b67d012d774726e236b59fc5","datavalue":{"value":{"amount":"+0.7388637065887451","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":"Q1108734$8A676AF9-05F7-4385-A478-BDFC433B5378","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximating functions by their Poisson transform","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximating_functions_by_their_Poisson_transform"}}}}}