# Tagged Questions

59 views

### Gambler's ruin and coin toss

Edit 3. Fixed question to be more clear and include current solution Problem Two players player 1 and player 2 plays a game of fair coin flipping. Player 1 starts with $A$ coins and Player 2 with ...
97 views

### Meaning of 'expected value' in the following problem

Ok, I have found an interesting probabilites problem on TopCoder. I have truncated the statement: "What is the expected number of dice throws needed to attain a value of at least n (candies, in this ...
29 views

### Is it possible that a randomized recursion has a nonzero probability of either converging or diverging?

I have very little "hands-on" experience with probability, but here is my context: I was looking at the random Fibonacci sequence: $$f_0=f_1=1, f_n=f_{n-1}+Xf_{n-2}$$ where $X$ is chosen randomly ...
47 views

### recurrent events-Probability of even number of successes

Let E be the event of an even number of successes. $u_n$:Probability of E occurring at the nth trial not necessarily for the first time $f_n$:Probability of E occurring at the nth trial for the first ...
51 views

### Expected Time for n Independent Prisoners to Escape

Suppose there are $n$ prisoners, and each day every prisoner independently has a probability $p$ of escaping. What is the expected length of time before all prisoners have escaped? Someone asked ...
63 views

### forming difference equation

there is a square with $60$ equal blocks. If a mosquito(bug)is set to fly starting at block $1$, it is equally likely to fly to other blocks. what is the probability after $n$ flies, the mosquito is ...
26 views

### Changing recurrence to matrix

$$F(x) = aF(x-k+1) + bF(x-k+2) + cF(x-k+4) + dF(x-k+7)$$ where $F(x) = 1$ if $x<k$. $a,b,c,d,k$ are known (and positive) and $x$ is chosen. Can anyone show how to set this up in matrix form ...
113 views

### Closed form solution to a recurrence relation (from a probability problem)

Is there a closed form solution to the following recurrence relation? $$P(i,j) = \frac{i^{5}}{5i(5i-1)(5i-2)(5i-3)(5i-4)}\sum\limits_{k=0}^{j-5}(1-P(i-1,k))$$ where $P(i,j)=0$ for $j<5$. The ...
65 views

### Outcome probabilities for set number of dice rolls with conditional extra rolls

If we are allowed $n$ rolls of a dice, where each roll of 1 gives us an extra roll, what is the probability of rolling m 1s in the sequence of available rolls, and likewise what is the probability of ...
496 views

### Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
315 views

### Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
143 views

### Mathematical formula to find adjacent items in a grid

I have a 3x3 grid of dots. Selecting any one of the 9 dots, I need to find out which of the remaining dots are adjacent to the first dot. So, if for example we chose the first dot in the first row ...
159 views

### Solving a recurrence for a probability?

I came across the following recurrence relation when exploring properties of a certain type of randomized perfect binary tree: $$T(0) = \frac{1}{2}$$ $$T(k + 1) = 1 - T(k)^2$$ (Specifically, ...
134 views

### probability of sum of a given set of whole numbers being greater than a certain number

There are total of n balls in k boxes. Box one contains n1 balls, box 2 contains n2 balls and so on. The probability of picking balls from boxes is p1,p2,...,pk. We can pick either all the balls in a ...
242 views

### Probability of rolling $n$ successes on an open-ended/exploding dice roll

I'm trying to compute the probability of achieving a certain number of successes when rolling a die pool for both open-ended/exploding and closed tests. Success is defined as a roll above a certain ...
138 views

### How to solve recurrence in two variables

How can you solve this simple looking recurrence relation in two variables? $f(a,b) = 1 + \frac{a f(a+1,b+1) + (x-a)f(a+1,b)}{x}$ The function $f$ is defined for non-negative integer values $a$ and ...
83 views

### Guidelines for Obtaining Recursive Equations?

I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills ...
548 views

### Probability of tossing a biased coin without having k heads consecutively in a row

I got asked by a friend this question; I have a coin, the probability of receiving a head by tossing is $p$ and tail $1-p$. I have to toss it $n$ times without getting $k$ heads in a row. What is the ...
177 views

### To obtain the closed-form expression of CDF and PDF from the recurrence relation

Now I have a question, in which I need to find the probability mass function and the cumulative distribution function. But now I only have the recurrence relation. Here is the details: Assume ...
451 views

### recurrence relation arising from Magic the Gathering scenario [duplicate]

Possible Duplicate: Probability of a random binary string containing a long run of 1s? EDIT: Cocopuffs below has partially answered the question, but the critical base case $L=2$ to his ...
235 views

### Finding Probability Generating function for $P\left\{ X > n+1\right\}$

I am trying to find probability generating function for $P\left\{ X > n+1\right\}$. Let X be a random variable assuming the values $0, 1, 2, ...$. The notation both for the distribution of $X$ ...
119 views

### recurrence solution to gambler's ruin

From DeGroot 2.4.2, let $a_i$ be the conditional probability that the gambler wins all $k$ given gambler is at $i$. $a_i = pa_{i+1} + (1 - p)a_{i-1}$ It's not clear from the text what steps are ...
136 views

### A difference equation related to RW on Hypercube

I am trying to solve the following recurrent relation $$T(n)=\frac{n}{m}T(n-1)+\frac{m-n}{m}T(n+1)+1, \,\, \text{subject to } T(m)=0$$ Where $0\leq n\leq m$ and $m$ is a fixed integer. I have ...
402 views

### Asymptotics for the expected length of the longest streak of heads.

As Introduction to Algorithms (CLRS) describes, the problem is Suppose you flip a fair coin $n$ times. What is the longest streak of consecutive heads that you expect to see? The book claims ...
903 views

### Probability of a random binary string containing a long run of 1s?

For some fixed $n$, let $p_n$ be the probability that a random infinite binary string contains a run of consecutive $1$s, containing $n$ more $1$s than the total number appearing before the run. For ...
167 views

### Asymptotic behaviour of a two-dimensional recurrence relation

This problem comes out of a research in models of firm growth. The model is simple: A firm has two parameters which are its size (number of employees) and job vacancies. A firm of size $n$ will ...
511 views

### Solving a simple recurrence relation

I have the following recurrence relation: $a_0=1$ $a_{n}=pa_{n+1}+qa_{n-1}$ Where $p+q=1$. This relation arises in analyzing a "gambler's ruin" situation. It is claimed that the general solution ...
233 views

### Moments on number of occurrences of substring

Let $S$ be a string of length $n$. Each character of $S$ has probability $p$ of being 'A' and probability $1-p=q$ of being 'B'. $R$ is the number of occurrences of the substring 'AB' in $S$. I'd like ...
414 views

### Solving randomized recurrence relation

I'm looking at the random sequence $x_n$ with $x_0=x_1=1$ and $$x_{n+1}=2x_n\pm x_{n-1}$$ where we choose the $\pm$ sign independently with equal probability. Now ...