# Questions tagged [bit-strings]

Use this tag for questions related to array data structures that compactly store bits.

27 questions
2answers
191 views

### Why are bitstrings without 00 of length n equals $Fib_{n+2}$?

EDIT: $B_{n}$ denotes the number of bitstrings of length n without 00. So I've been studying Discrete Math, and I came across the proof that $B_{n} = f_{n+2}$. What I do not understand about this is, ...
2answers
236 views

### Bitstring Mathematical Induction Proof

I have to use induction to prove that for any finite bitstring $s$, if $s$ ends in a $1$, then $01$ occurs at most one more time than $10$. Induct on the length of $s$. I really can't solve this ...
1answer
50 views

### Is there a name for the set of “unique” combinations of the powerset of $2^n$ modulo permutation?

I was studying an algorithm on $k$-combinations of $n$-bit strings and realised that, my brute-force approach would spend lots of time on "structurally equivalent" bitstring combinations, that could ...
1answer
49 views

### Bit swapping probability question

Let $x = x(1), \dots , x(n)$ be a bit string containing exactly $m$ occurrences of 1. Consider the following operation on $x$: we choose a random pair of indices $(i,j),$ and we swap $x(i)$ and $x(j)$ ...
1answer
138 views

### Question about equivalence relation/bitstring

Actually i have no idea about this question.i know the definition of equivalence relations 1-) reflective 2-) symmetric 3-) transitive but not more :(
1answer
21 views

### Is there a prefix-free language that can encode any other prefix-free language with at most a constant overheard?

Let $U$ and $P$ be prefix-free languages with alphabet $\{0,1\}$. We say that $U$ can encode $P$ with at most a constant overhead if there exists an injective function $c:P \to U$ and a constant $a$ ...
1answer
49 views

### Probability that a bit sequence does not appear in a sequence

Find the probability that a bit sequence $X$ of length $2k$ does not appear in a randomly generated bit sequence of length $n\geq 2k$. If for the general case it is hard, let's solve it for the ...
1answer
45 views

### Show that for any n ≥ 1, there is an error-detecting set of strings of length n, using the digits 0, 1, and 2, that has 3n−1 strings?

Can anyone please show me a proof by induction for this? A set of error-detecting strings is a set of strings that differ by more than one character. For example: for {0,1,2} for n = 2: {00,11,22} ...
0answers
99 views

### Generating combinations using a butterfly network

I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming ...
0answers
23 views

### Is reversing a string an example of a one to one function?

The word "apple" reversed yields "elppa". No other input can produce the same output. And in such a scenario can palindromes also be included in the list of permissible strings. Was wondering about ...
0answers
38 views

### Maximizing the number of occurrences of a fixed subsequence

Fix two positive integers $N$ and $M$ and assume $n:=\frac{N}{M}\in\mathbb{N}$. Consider a fixed binary sequence $Y=Y_1,\ldots,Y_M\in\{0,1\}^M$. The goal is to find an optimizing length-$N$ ($N\geq M$)...
0answers
117 views

### Multiplying strings as polynomials

Interdisciplinary Question: How to approach the question and arrive at the solution?
0answers
69 views

### How long message can I send?

I know the $n$-bit message ($M$). I have to send it to the receiver bit by bit. For each bit I can also send one bit of comment ($C$). Before receiver gets the bit, he have to guess it($G$). After ...
0answers
49 views

### reference request - Practice problems for probability theory.

I need some good probability theory practice problems on the following topics - Binary strings ( Bit strings ) generating random permutations using bit strings Coin toss problems where each toss is ...
0answers
62 views

### entropy of binary strings showing a beta-distribution hamming distance

Let's define a binary string random variable of length $n$, i.e., $X\in \left\{0,1\right\}^n$. Let us define $D$ as the random variable obtained as the Hamming distance between two samples of $X$ $x_1$...
0answers
53 views

### What is the graph of my chances to mine a bitcoin?

Consider the next hashing definishion of $f(x)$ $$f(1) = 100$$ $$f(x) = \operatorname{SHA-256}(f(x-1))$$ Where $x$ is a positive integer and SHA-256 is the hash algorithm. You can think of SHA-256 ...
0answers
46 views

### Probability that two bit sequences match more than 60%

Assume that there is a random bit sequence generator that each time returns a bit sequence of length 100. Each bit of the sequence can be a 1 or 0 with equal probability. Question: What is the ...
0answers
45 views

### Number of bin. strings with Hamming weight r, which do not contain k consecutive zeros for large string length

I am interested in the number of binary strings of length $m$ and Hamming weight $r$, which do not contain $k$ consecutive zeros. A nice derivation of that number is in Number of binary and constant-...
0answers
105 views

### Characteristic Vector Question

I have been asked the following questions on a tutorial worksheet and am not sure how to answer. "There is a natural relationship between sets and bit strings which is called the characteristic ...
0answers
16 views

### Binary Rotation in Hilbert Curve?

Currently, I am following this guide to try and code up a function for the Hilbert Curve, however, I am stuck on the rotation step. I am a computer science student with not much a mathematical ...
0answers
59 views

### Preserving the bitwise dot product distributive property

We can define the bitwise dot product as the dot product between the vectors of the binary bit representations of two numbers. E.g. $$5\cdot 7 = (1,0,1)\cdot(1,1,1) = 2$$ But curiously, this dot ...
0answers
25 views

### Total number of bit-strings that start with 3 ones and end with 2 ones

I have a problem where I need to find the total number of bit-strings with the length of 30 that start with 3 ones and end with 2 ones. The total number of 1s in the string is 17 and the total number ...
0answers
320 views

### Number of binary strings of length n where specific substrings occur more than m times in total

Problem Given integers $n,m,k,v$ count the number of possible bit strings $s$ of length $n$ such that at least $m$ of the contiguous substrings of $s$ of length $k$ have value greater than $v$ when ...
0answers
29 views

### Asymptotic Behaviour of a formula

I have the following hideous equation $$\frac{1}{n} \log_q (q^lx)$$ with \begin{equation} x=\sum_{i=0}^{\lfloor \frac{n}{l} \rfloor -1} \left( \sum_{j=0}^{\lfloor \frac{n-(i+1)l}{l} \rfloor} (1-q)^j ...
0answers
116 views

### Propositional logic as sets of bit-vectors

Consider that formulas in propositional logical can be represented as sets of bit-vectors. For example, a formula $\neg b$ (all bit-vectors of the type $?0?$) with three atomic propositions $a,b$ and \$...
0answers
41 views

### Deduce patterns of divisibility in bit strings

This is partially a computer science question, but belongs here as well. The question has to do with the bit representation of integers. For simplicity, assume only non-negative integers. Can we find ...
0answers
618 views

### Given binary string of length n with k bit sets, how many permutations have x consecutive ones and no y consecutive ones where y > x

Not sure if this is possible to calculate in an easy way but given binary string of length n with k bit sets, how many permutations have x consecutive ones and no y consecutive ones where y > x An ...