Consider binary strings with n digits (for example, if n=4, some of the possible strings are 0011,1010,1101, etc.) Let Zn be the number of binary strings of length n that do not contain the substring 000 Find a recurrence relation for Zn You are not required to find a closed form for this recurrence.

Question
Bivariate numerical data
asked 2021-03-07
Consider binary strings with n digits (for example, if n=4, some of the possible strings are 0011,1010,1101, etc.)
Let Zn be the number of binary strings of length n that do not contain the substring 000
Find a recurrence relation for Zn
You are not required to find a closed form for this recurrence.

Answers (1)

2021-03-08
Consider such a sequence of n digits.
If the first digit is 1, then we must not have a substring 000 in the remaning part of this sequence. Thus, we have Zn-1 such sequences.
If the first digit is 0, then we look at the second digit. If the second digit is 1, then this sequence starts with 01, meaning that we must not have a substring 000 in the remaning n—2 digits. Therefore, there are Zn-2 such sequences.
If the second digit is 0, then this sequence starts with 00. This means that the third digit must be 1 (otherwise, we would have 000 in this sequence). Therefore, this sequence starts with 001, meaning that we must not have 00 asa substring in the remaining n —3 digits. Thus, there are Zn-3 such sequences.
This covers all cases. Therefore, the recurrence relation is Zn=Zn-1+Zn-2+Zn-3
0

Relevant Questions

asked 2021-02-23
1. A researcher is interested in finding a 98% confidence interval for the mean number of times per day that college students text. The study included 144 students who averaged 44.7 texts per day. The standard deviation was 16.5 texts. a. To compute the confidence interval use a ? z t distribution. b. With 98% confidence the population mean number of texts per day is between and texts. c. If many groups of 144 randomly selected members are studied, then a different confidence interval would be produced from each group. About percent of these confidence intervals will contain the true population number of texts per day and about percent will not contain the true population mean number of texts per day. 2. You want to obtain a sample to estimate how much parents spend on their kids birthday parties. Based on previous study, you believe the population standard deviation is approximately \(\displaystyle\sigma={40.4}\) dollars. You would like to be 90% confident that your estimate is within 1.5 dollar(s) of average spending on the birthday parties. How many parents do you have to sample? n = 3. You want to obtain a sample to estimate a population mean. Based on previous evidence, you believe the population standard deviation is approximately \(\displaystyle\sigma={57.5}\). You would like to be 95% confident that your estimate is within 0.1 of the true population mean. How large of a sample size is required?
asked 2021-01-10
In 1985, neither Florida nor Georgia had laws banning open alcohol containers in vehicle passenger compartments. By 1990, Florida had passed such a law, but Georgia had not.
(i) Suppose you can collect random samples of the driving-age population in both states, for 1985 and 1990. Let arrest be a binary variable equal to unity if a person was arrested for drunk driving during the year. Without controlling for any other factors, write down a linear probability model that allows you to test whether the open container law reduced the probability of being arrested for drunk driving. Which coefficient in your model measures the effect of the law?
(ii) Why might you want to control for other factors in the model? What might some of these factors be?
(iii) Now, suppose that you can only collect data for 1985 and 1990 at the county level for the two states. The dependent variable would be the fraction of licensed drivers arrested for drunk driving during the year. How does this data structure differ from the individual-level data described in part (i)? What econometric method would you use?
asked 2020-11-20
Response rates to Web surveys are typically low, partially due to users starting but not finishing the survey. The factors that influence response rates were investigated in Survey Methodology (Dec. 2013). In a designed study, Web users were directed to participate in one of several surveys with different formats. For example, one format utilized a welcome screen witb a white background, and another format utilized a welcome screen with a red background. The "break-off rates," i.e., the proportion of sampled users who break off the survey before completing all questions, for the two formats are provided in the table. \(\displaystyle{b}{e}{g}\in{\left\lbrace{m}{a}{t}{r}{i}{x}\right\rbrace}\ \text{ }\ &\text{White Welcome Screen}&\text{Red Welcome Screen}\ \text{Number of Web users}&{190}&{183}\ \text{Number who break off survey}&{49}&{37}\ \text{Break-off rate}&{0.258}&{0.202}\ {e}{n}{d}{\left\lbrace{m}{a}{t}{r}{i}{x}\right\rbrace}\) a) Verify the values of the break-off rates shown in the table. b) The researchers theorize that the true break-off rate for Web users of the red welcome screen will be lower than the corresponding break-off Tate for users of the white welcome screen. Give the null and alternative hypotbesis for testing this theory. c) Conduct the test, part b, at \(\displaystyle\alpha={0.10}.\) What do you conclude?
asked 2021-02-25
Give a full and correct answer Why is it important that a sample be random and representative when conducting hypothesis testing? Representative Sample vs. Random Sample: An Overview Economists and researchers seek to reduce sampling bias to near negligible levels when employing statistical analysis. Three basic characteristics in a sample reduce the chances of sampling bias and allow economists to make more confident inferences about a general population from the results obtained from the sample analysis or study: * Such samples must be representative of the chosen population studied. * They must be randomly chosen, meaning that each member of the larger population has an equal chance of being chosen. * They must be large enough so as not to skew the results. The optimal size of the sample group depends on the precise degree of confidence required for making an inference. Representative sampling and random sampling are two techniques used to help ensure data is free of bias. These sampling techniques are not mutually exclusive and, in fact, they are often used in tandem to reduce the degree of sampling error in an analysis and allow for greater confidence in making statistical inferences from the sample in regard to the larger group. Representative Sample A representative sample is a group or set chosen from a larger statistical population or group of factors or instances that adequately replicates the larger group according to whatever characteristic or quality is under study. A representative sample parallels key variables and characteristics of the large society under examination. Some examples include sex, age, education level, socioeconomic status (SES), or marital status. A larger sample size reduced sampling error and increases the likelihood that the sample accurately reflects the target population. Random Sample A random sample is a group or set chosen from a larger population or group of factors of instances in a random manner that allows for each member of the larger group to have an equal chance of being chosen. A random sample is meant to be an unbiased representation of the larger population. It is considered a fair way to select a sample from a larger population since every member of the population has an equal chance of getting selected. Special Considerations: People collecting samples need to ensure that bias is minimized. Representative sampling is one of the key methods of achieving this because such samples replicate as closely as possible elements of the larger population under study. This alone, however, is not enough to make the sampling bias negligible. Combining the random sampling technique with the representative sampling method reduces bias further because no specific member of the representative population has a greater chance of selection into the sample than any other. Summarize this article in 250 words.
asked 2020-12-30
You are interested in finding a 95% confidence interval for the mean number of visits for physical therapy patients. The data below show the number of visits for 14 randomly selected physical therapy patients. Round answers to 3 decimal places where possible.
\(9 6 10 15 19 6 23 26 19 16 11 25 16 11\)
a. To compute the confidence interval use a t or z distribution.
b. With 95% confidence the population mean number of visits per physical therapy patient is between ___ and ___ visits.
c. If many groups of 14 randomly selected physical therapy patients are studied, then a different confidence interval would be produced from each group. About ___ percent of these confidence intervals will contain the true population mean number of visits per patient and about ___ percent will not contain the true population mean number of visits per patient.
asked 2020-10-23
The table below shows the number of people for three different race groups who were shot by police that were either armed or unarmed. These values are very close to the exact numbers. They have been changed slightly for each student to get a unique problem.
Suspect was Armed:
Black - 543
White - 1176
Hispanic - 378
Total - 2097
Suspect was unarmed:
Black - 60
White - 67
Hispanic - 38
Total - 165
Total:
Black - 603
White - 1243
Hispanic - 416
Total - 2262
Give your answer as a decimal to at least three decimal places.
a) What percent are Black?
b) What percent are Unarmed?
c) In order for two variables to be Independent of each other, the P \((A and B) = P(A) \cdot P(B) P(A and B) = P(A) \cdot P(B).\)
This just means that the percentage of times that both things happen equals the individual percentages multiplied together (Only if they are Independent of each other).
Therefore, if a person's race is independent of whether they were killed being unarmed then the percentage of black people that are killed while being unarmed should equal the percentage of blacks times the percentage of Unarmed. Let's check this. Multiply your answer to part a (percentage of blacks) by your answer to part b (percentage of unarmed).
Remember, the previous answer is only correct if the variables are Independent.
d) Now let's get the real percent that are Black and Unarmed by using the table?
If answer c is "significantly different" than answer d, then that means that there could be a different percentage of unarmed people being shot based on race. We will check this out later in the course.
Let's compare the percentage of unarmed shot for each race.
e) What percent are White and Unarmed?
f) What percent are Hispanic and Unarmed?
If you compare answers d, e and f it shows the highest percentage of unarmed people being shot is most likely white.
Why is that?
This is because there are more white people in the United States than any other race and therefore there are likely to be more white people in the table. Since there are more white people in the table, there most likely would be more white and unarmed people shot by police than any other race. This pulls the percentage of white and unarmed up. In addition, there most likely would be more white and armed shot by police. All the percentages for white people would be higher, because there are more white people. For example, the table contains very few Hispanic people, and the percentage of people in the table that were Hispanic and unarmed is the lowest percentage.
Think of it this way. If you went to a college that was 90% female and 10% male, then females would most likely have the highest percentage of A grades. They would also most likely have the highest percentage of B, C, D and F grades
The correct way to compare is "conditional probability". Conditional probability is getting the probability of something happening, given we are dealing with just the people in a particular group.
g) What percent of blacks shot and killed by police were unarmed?
h) What percent of whites shot and killed by police were unarmed?
i) What percent of Hispanics shot and killed by police were unarmed?
You can see by the answers to part g and h, that the percentage of blacks that were unarmed and killed by police is approximately twice that of whites that were unarmed and killed by police.
j) Why do you believe this is happening?
Do a search on the internet for reasons why blacks are more likely to be killed by police. Read a few articles on the topic. Write your response using the articles as references. Give the websites used in your response. Your answer should be several sentences long with at least one website listed. This part of this problem will be graded after the due date.
asked 2020-12-25
Case: Dr. Jung’s Diamonds Selection
With Christmas coming, Dr. Jung became interested in buying diamonds for his wife. After perusing the Web, he learned about the “4Cs” of diamonds: cut, color, clarity, and carat. He knew his wife wanted round-cut earrings mounted in white gold settings, so he immediately narrowed his focus to evaluating color, clarity, and carat for that style earring.
After a bit of searching, Dr. Jung located a number of earring sets that he would consider purchasing. But he knew the pricing of diamonds varied considerably. To assist in his decision making, Dr. Jung decided to use regression analysis to develop a model to predict the retail price of different sets of round-cut earrings based on their color, clarity, and carat scores. He assembled the data in the file Diamonds.xls for this purpose. Use this data to answer the following questions for Dr. Jung.
1) Prepare scatter plots showing the relationship between the earring prices (Y) and each of the potential independent variables. What sort of relationship does each plot suggest?
2) Let X1, X2, and X3 represent diamond color, clarity, and carats, respectively. If Dr. Jung wanted to build a linear regression model to estimate earring prices using these variables, which variables would you recommend that he use? Why?
3) Suppose Dr. Jung decides to use clarity (X2) and carats (X3) as independent variables in a regression model to predict earring prices. What is the estimated regression equation? What is the value of the R2 and adjusted-R2 statistics?
4) Use the regression equation identified in the previous question to create estimated prices for each of the earring sets in Dr. Jung’s sample. Which sets of earrings appear to be overpriced and which appear to be bargains? Based on this analysis, which set of earrings would you suggest that Dr. Jung purchase?
5) Dr. Jung now remembers that it sometimes helps to perform a square root transformation on the dependent variable in a regression problem. Modify your spreadsheet to include a new dependent variable that is the square root on the earring prices (use Excel’s SQRT( ) function). If Dr. Jung wanted to build a linear regression model to estimate the square root of earring prices using the same independent variables as before, which variables would you recommend that he use? Why?
1
6) Suppose Dr. Jung decides to use clarity (X2) and carats (X3) as independent variables in a regression model to predict the square root of the earring prices. What is the estimated regression equation? What is the value of the R2 and adjusted-R2 statistics?
7) Use the regression equation identified in the previous question to create estimated prices for each of the earring sets in Dr. Jung’s sample. (Remember, your model estimates the square root of the earring prices. So you must actually square the model’s estimates to convert them to price estimates.) Which sets of earring appears to be overpriced and which appear to be bargains? Based on this analysis, which set of earrings would you suggest that Dr. Jung purchase?
8) Dr. Jung now also remembers that it sometimes helps to include interaction terms in a regression model—where you create a new independent variable as the product of two of the original variables. Modify your spreadsheet to include three new independent variables, X4, X5, and X6, representing interaction terms where: X4 = X1 × X2, X5 = X1 × X3, and X6 = X2 × X3. There are now six potential independent variables. If Dr. Jung wanted to build a linear regression model to estimate the square root of earring prices using the same independent variables as before, which variables would you recommend that he use? Why?
9) Suppose Dr. Jung decides to use color (X1), carats (X3) and the interaction terms X4 (color * clarity) and X5 (color * carats) as independent variables in a regression model to predict the square root of the earring prices. What is the estimated regression equation? What is the value of the R2 and adjusted-R2 statistics?
10) Use the regression equation identified in the previous question to create estimated prices for each of the earring sets in Dr. Jung’s sample. (Remember, your model estimates the square root of the earring prices. So you must square the model’s estimates to convert them to actual price estimates.) Which sets of earrings appear to be overpriced and which appear to be bargains? Based on this analysis, which set of earrings would you suggest that Dr. Jung purchase?
asked 2021-01-31
(a) Find a closed-form solution for this recurrence relation: an=2⋅an−1−n+1 with a1=2a
(b) Prove that your closed-form solution is correct.
asked 2021-01-19
Suppose the alphabet consists of just {a,b,c,d,e}. Consider strings of letters that show repetitions. How many 4-letter strings are there that do not contain “aa"?
asked 2020-12-27
Consider the next 1000 98% Cis for mu that a statistical consultant will obtain for various clients. Suppose the data sets on which the intervals are based are selected independently of one another. How many of these 1000 intervals do you expect to capture the corresponding value of \(\mu?\)
What isthe probability that between 970 and 990 of these intervals conta the corresponding value of ? (Hint: Let
Round your answer to four decimal places.)
‘the number among the 1000 intervals that contain What king of random variable s 2) (Use the normal approximation to the binomial distribution
...