Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Probability of some sequence in a list of numbers

  1. Aug 10, 2017 #1
    Hello,
    would like to derive a length of list of random numbers in which I may find some special sequence of few numbers with some probability.

    For clearness I give an example: I have two generator of (pseudo) random numbers with same range of numbers, let's say (1-k). First generator give a random sequence of n numbers from range (1-k) and numbers may repiet. The second do the same but sequence of m numbers and m>n. What has to be m and n if I would like to find n in m (anywhere) with probability p?
     
  2. jcsd
  3. Aug 10, 2017 #2
    Ok my opinion is:
    in long sequence "m" is ##m-n+1## of "n" sequences. A number of combinations of small sequence "n" is ##k^n##. So probability than is ##p=\frac{m-n+1}{k^n}##
    Is it right?
     
  4. Aug 10, 2017 #3

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    You need to explain more. For instance, you should say if you are talking about integers in some range or about real numbers. And what type of "special sequence" are you talking about? -- exact values, increasing numbers, etc. etc.
     
  5. Aug 10, 2017 #4
    Sorry, I'm talking about integers. And both sequences are random sequences of numbers from range (1-k). The word special was wrong.
     
  6. Aug 10, 2017 #5

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Sorry, I see that that was probably clear in your original post. I misread it.
     
  7. Aug 10, 2017 #6
    Nevermind, and what do you mean about my formula from post #2?
     
  8. Aug 10, 2017 #7

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    I don't know the answer. And I'm still not completely clear on the question. Are you starting with a given sequence that needs to be matched or are you asking about any repeats of a certain length? Either way, I am not sure that I can answer your questions. I'll have to leave that to people who are better at it.
     
  9. Aug 10, 2017 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    It is complicated.

    Let's start with an easier question: For a given sequence of n integers from 1 to k, what is the probability that this sequence appears in a sequence of m random integers from 1 to k?
    It turns out that this probability depends on the sequence. As a simple example, consider k=1, m=3 and compare the sequences "11" and "12". For the string of length 3, there are 8 options (111, 112, 121, 122, 211, 212, 221, 222), three of them contain "11" but four of them contain "12". That does not mean "11" would be less likely to appear, but it appears twice in the same string (in 111) while "12" does not.

    For a given sequence, you can calculate the probability that it appears with a Markov chain. There is no nice general formula, and you have to do this for every type of pattern a sequence of n integers can form.
    If n=1 or k is large, the approximation of m-n+1 independent sequences of length n will give a reasonable approximation in most cases, and the cases where it fails are long repetitions, they are unlikely for large k anyway (especially for large n).
     
  10. Aug 11, 2017 #9
    What is behind:
    Roulette and very well known myth about winning due a betting on one color and doubling of a bet. Probably you know it. You bet still one color (black/red) and when you lose you double your bet untill you win.
    So question is what is probability of sequence of let's say 6-10 same color in line?
    May I use my formula for that?
     
  11. Aug 11, 2017 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Neglecting 0 we have the case k=2, where your formula shows large deviations.
     
  12. Aug 14, 2017 #11
    Ok, so there doesn't exist some easy formula how to describe such situation?
     
  13. Aug 14, 2017 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Not that I am aware of, but calculating it with Markov chains is fast. You can probably find some approximation for most cases, where only some special cases (like long series of the same color) lead to some deviations, but these special cases are rare.
     
  14. Aug 15, 2017 at 7:30 AM #13
    Ok, thank you. And do you know about good article or some text about Markov chains?
     
  15. Aug 15, 2017 at 10:02 AM #14

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The Wikipedia article should give a good introduction, and there are various textbooks with more details.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Probability of some sequence in a list of numbers
  1. Number sequence (Replies: 5)

  2. Number Sequences (Replies: 10)

  3. Number Sequence (Replies: 1)

Loading...