1
vote
1answer
21 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 ...
3
votes
2answers
43 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 ...
2
votes
1answer
48 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 ...
1
vote
1answer
60 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 ...
0
votes
1answer
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 ...
2
votes
1answer
112 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 ...
1
vote
1answer
64 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 ...
9
votes
2answers
420 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 ...
1
vote
1answer
284 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 ...
0
votes
2answers
135 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 ...
5
votes
2answers
154 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, ...
0
votes
1answer
131 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 ...
2
votes
1answer
215 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 ...
1
vote
1answer
137 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 ...
1
vote
2answers
81 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 ...
2
votes
0answers
526 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 ...
1
vote
0answers
170 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 ...
19
votes
4answers
446 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 ...
2
votes
1answer
228 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$ ...
2
votes
3answers
116 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 ...
3
votes
1answer
135 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 ...
3
votes
0answers
386 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 ...
19
votes
2answers
883 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 ...
4
votes
0answers
165 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 ...
6
votes
1answer
496 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 ...
1
vote
1answer
230 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 ...
10
votes
3answers
411 views

Solving randomized recurrence relation

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