Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-09T01:32:28.604Z Has data issue: false hasContentIssue false
  • English
  • Français

The first repetition of a pattern in a symmetric Bernoulli sequence

Published online by Cambridge University Press:  14 July 2016

Ehud D. Karnin
Ehud D. Karnin*
Affiliation:
Stanford University
*
∗ Postal address: Information Systems Laboratory, Department of Electrical Engineering, Stanford University, Stanford, CA 94305, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

In a symmetric sequence of Bernoulli trials we define each successive l outcomes as a pattern, and look at the first time that any pattern repeats. Asymptotic expressions, as l →∞, of the distribution and the expectation of this waiting time are derived.

Keywords

REPEATED PATTERNSBIRTHDAY PROBLEM
Type
Short Communications
Information
Journal of Applied Probability , Volume 20 , Issue 2 , June 1983 , pp. 413 - 418
Copyright
Copyright © Applied Probability Trust 1983 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This work was supported by the Joint Services Electronics Program under contract no. DAAG29-81-0057 and by the National Science Foundation under contract no. ECS79–16161.

References

[1] Feller, W. (1968) An Introduction to Probability Theory and its Applications, Vol. 1, 3rd edn. Wiley, New York.Google Scholar
[2] Hellman, M. E. (1982) On DES based synchronous encryption. Computer Mag. Submitted.Google Scholar
[3] National Bureau Of Standards (1980) DES modes of operation. FIPS PUB 81, 2 December 1980.Google Scholar
[4] Sevastyanov, B. A. (1972) Poisson limit law for a scheme of sums of dependent random variables. Theory Prob. Appl. 17, 695–699.Google Scholar
[5] Zubkov, A. M. and Mikhailov, V. G. (1974) Limit distribution of random variables associated with long duplications in a sequence of independent trials. Theory Prob. Appl. 19, 172–179.Google Scholar