{"id":3555,"date":"2011-10-08T15:47:20","date_gmt":"2011-10-08T14:47:20","guid":{"rendered":"http:\/\/www.walkingrandomly.com\/?p=3555"},"modified":"2016-04-04T19:18:51","modified_gmt":"2016-04-04T18:18:51","slug":"probability-of-overlapping-sub-sequences","status":"publish","type":"post","link":"https:\/\/walkingrandomly.com\/?p=3555","title":{"rendered":"Probability of overlapping sub-sequences?"},"content":{"rendered":"<p>Consider a periodic sequence, seq<sub>p<\/sub>, with period p<\/p>\n<p>seq<sub>p<\/sub> = <em>a<\/em><sub>1<\/sub>, <em>a<\/em><sub>2<\/sub>, &#8230;, <em>a<\/em><sub><em>p<\/em><\/sub>,\u00a0\u00a0<em>a<\/em><sub>1<\/sub>, <em>a<\/em><sub>2<\/sub>, &#8230;, <em>a<\/em><sub><em>p<\/em><\/sub>,\u00a0\u00a0<em>a<\/em><sub>1<\/sub>, <em>a<\/em><sub>2<\/sub>, &#8230;, <em>a<\/em><sub><em>p<\/em><\/sub>, &#8230;<\/p>\n<p>Two sub-sequences, each of length N where 2&lt; N&lt; p, are produced by choosing two random start points in seq<sub>p<\/sub> and using the next N-1 numbers. What is the probability that these two sub-sequences will overlap?<\/p>\n<p>If you take M&gt;2 such length N sub-sequences then what is the probability that <strong>any<\/strong> two will overlap?<\/p>\n<p>For a more concrete example, assume that p = 2^19937 &#8211; 1 (yes, a very big number) and consider 10,000 sub-sequences each of length 10^9.<\/p>\n<p>Disclaimer: I don&#8217;t have the solution to this and haven&#8217;t yet tried to find it<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Consider a periodic sequence, seqp, with period p seqp = a1, a2, &#8230;, ap,\u00a0\u00a0a1, a2, &#8230;, ap,\u00a0\u00a0a1, a2, &#8230;, ap, &#8230; Two sub-sequences, each of length N where 2&lt; N&lt; p, are produced by choosing two random start points in seqp and using the next N-1 numbers. What is the probability that these two sub-sequences [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[6,54,21],"tags":[],"class_list":["post-3555","post","type-post","status-publish","format-standard","hentry","category-general-math","category-probability","category-problem-of-the-week"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3swhs-Vl","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts\/3555","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3555"}],"version-history":[{"count":1,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts\/3555\/revisions"}],"predecessor-version":[{"id":3897,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts\/3555\/revisions\/3897"}],"wp:attachment":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3555"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3555"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3555"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}