Results 1 to 4 of 4

Thread: Find string probabilities

  1. #1
    Member
    Join Date
    Sep 2018
    Location
    Moscow
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Find string probabilities

    - I have two symbols, one is "long" 1 bit and one is "long" 2 bits. That is X and YY
    - The first has probability 2/3 and the second 1/3
    - I have a string of these symbols, for example "X YY X X YY YY X X..."

    My question: Given a length L, how do I find how many different strings exist of such length? In other words how many different strings I can build such the the length of all its symbols is exactly L

    Thanks for the help.

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,775
    Thanks
    276
    Thanked 1,206 Times in 671 Posts
    Seems to be this:
    Table[(Fibonacci[L] + LucasL[L])/2, {L, 1, 100}]
    or this:
    Table[Total[ Function[x, Binomial[x[[1]] + x[[2]], x[[1]]] ] /@ FrobeniusSolve[{1, 2}, L]], {L, 1, 100}]
    (Fibonacci[L-1]+Fibonacci[L]+Fibonacci[L+1])/2
    ((1+Sqrt[5])^L*(1+Sqrt[5]+((Sqrt[5]-3)/2)^L*(Sqrt[5]-1)))/Sqrt[5]/2^(L+1)


    Example: L=4
    Code:
    1) ----
    2) ##--
    3) -##-
    4) --##
    5) ####

  3. Thanks:

    encode (15th September 2018)

  4. #3
    Member
    Join Date
    Sep 2018
    Location
    Moscow
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    How did you arrive to Table[(Fibonacci[L] + LucasL[L])/2, {L, 1, 100}] ???

  5. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,775
    Thanks
    276
    Thanked 1,206 Times in 671 Posts
    I only made the "FrobeniusSolve" line, by looking up relevant functions in mathematica help.
    Btw, it can be easily modified to compute string probabilities.
    Once I had actual values, there's FindSequenceFunction.

    Normally its done by building a recurrent function, converting it to generating function, etc.
    But I'm too rusty at this stuff.
    There's a good book btw - https://en.wikipedia.org/wiki/Concrete_Mathematics

Similar Threads

  1. Why SSE in PAQ8 works on un-stretched probabilities?
    By Piotr Tarsa in forum Data Compression
    Replies: 2
    Last Post: 21st April 2018, 01:31
  2. Replies: 5
    Last Post: 20th January 2018, 01:39
  3. Semilocal string comparison (3 lectures [in russian])
    By lz77 in forum Data Compression
    Replies: 0
    Last Post: 29th November 2016, 11:21
  4. Replies: 1
    Last Post: 17th February 2014, 22:05
  5. Directory hash as one string
    By FatBit in forum The Off-Topic Lounge
    Replies: 6
    Last Post: 16th January 2012, 23:29

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •