# coin toss

27 views

### Fakename

Sep 4, 2005, 3:27:41â€¯PM9/4/05
to

If you toss 100 coins, what's the probability of getting 5 (either heads or
tails in a row)? 6 in a row?
How do you figure it out?

--
submissions: post to k12.ed.math or e-mail to k12...@k12groups.org
private e-mail to the k12.ed.math moderator: kem-mo...@k12groups.org
newsgroup website: http://www.thinkspot.net/k12math/
newsgroup charter: http://www.thinkspot.net/k12math/charter.html

### Fakename

Sep 4, 2005, 3:52:56â€¯PM9/4/05
to

ooops ...make that "toss one coin 100 times"

"Fakename" <fake...@comcast.net> wrote in message
news:tqidnZbTpZN...@giganews.com...

### Dave Chamberlain

Sep 5, 2005, 2:30:19â€¯AM9/5/05
to

Fakename <fake...@comcast.net> wrote:

: If you toss 100 coins, what's the probability of getting 5 (either heads or

: tails in a row)? 6 in a row?
: How do you figure it out?

If I'm following the question correctly.

Each toss has an equal chance 50/50 (1:2 or 1/2) of being heads or tails.
If the first toss is heads, the odds of the second toss still has
a 50/50 chance of being heads.
Tosses 1 and 2:
H H
H T
T H
T T
There are four combinations (2 choices raised to 2 tosses), with
2 of them yielding all Heads or Tails. So your chances are
2 out of the 4 combinations will be the same. 2/4 = 1/2 = 50%

If you toss the coin a third time:
H H H
H H T
H T H
H T T
T H H
T H T
T T H
T T T
You wind up with 8 combinations, 2 raised to the 3rd power, with
2 of those 8 being all the same.

So if you were to toss it 5 times you would have 32 combinations,
2^5 (64 combinations if you wanted 6 in a row). With 2 of them
being all the same.
With 5 coins: 2:32 = 1:16 = 6.25%
With 6 coins: 2:64 = 1:32 = 3.125%

--

-davec
-----------------------------------------------------------------

### Fakename

Sep 5, 2005, 1:34:00â€¯PM9/5/05
to

"Dave Chamberlain" <da...@osmium.mv.net> wrote in message
news:dfgcri\$2fls\$1...@pyrite.mv.net...

No, what I mean is ...if you tossed the coin exactly 100 times, what is the
probability that you will get at least one run of five in a row (either

### Jim Spriggs

Sep 5, 2005, 5:56:01â€¯PM9/5/05
to

Fakename wrote:

> No, what I mean is ...if you tossed the coin exactly 100 times, what is the
> probability that you will get at least one run of five in a row (either

Does a run of ten heads count as two runs of five (and hence to be
counted) or as a run of more than five (and hence not to be counted)?

--
I don't know who you are Sir, or where you come from,
but you've done me a power of good.

### Kevin Karplus

Sep 5, 2005, 5:56:02â€¯PM9/5/05
to

On 2005-09-04, Fakename <fake...@comcast.net> wrote:
> If you toss 100 coins, what's the probability of getting 5 (either heads or
> tails in a row)? 6 in a row?
> How do you figure it out?

I believe the answer you are looking for can be found on
http://mathworld.wolfram.com/Run.html
which I found by googling
probability runs

------------------------------------------------------------
Kevin Karplus kar...@soe.ucsc.edu http://www.soe.ucsc.edu/~karplus
Professor of Biomolecular Engineering, University of California, Santa Cruz
(Senior member, IEEE) (Board of Directors, ISCB)
life member (LAB, Adventure Cycling, American Youth Hostels)
Effective Cycling Instructor #218-ck (lapsed)
Affiliations for identification only.

### Duane Bozarth

Sep 5, 2005, 9:15:12â€¯PM9/5/05
to

Jim Spriggs wrote:
>
> Fakename wrote:
>
> > No, what I mean is ...if you tossed the coin exactly 100 times, what is the
> > probability that you will get at least one run of five in a row (either
>
> Does a run of ten heads count as two runs of five (and hence to be
> counted) or as a run of more than five (and hence not to be counted)?

If we're asking, does a run of six count as zero, one or two runs of
five? :)

### Fakename

Sep 5, 2005, 9:15:13â€¯PM9/5/05
to

"Kevin Karplus" <kar...@cheep.cse.ucsc.edu> wrote in message
news:slrndhpf9o....@cheep.cse.ucsc.edu...

### Fakename

Sep 5, 2005, 9:15:15â€¯PM9/5/05
to

a run of ten would count as two runs of five.
a run of six would count as one run of five... and so on.

"Jim Spriggs" <jim.s...@ANTISPAMbtinternet.com.invalid> wrote in message
news:431C8696...@ANTISPAMbtinternet.com.invalid...

### Robert Morewood

Sep 6, 2005, 12:54:58â€¯PM9/6/05
to

: If you toss 100 coins, what's the probability of getting 5,
: either heads or tails, in a row? 6 in a row?

: How do you figure it out?

Are you asked for "at least" five in a row, or "exactly" five in a row?

I derived a recursive formula which answers the question for "at least"
K in a row the same from a sample of N coins. A small program
(on computer or calculator) quickly gives an approximate answer.
For "exactly" five in a row, something similar might work, but
I'll leave that to someone else. In the following I will explain
the thought process which led to my formula.

Try the calculation with less than 100 coins.

Less than five coins is too simple?
The odds of five in a row with fewer than five coins is ZERO!

Try FIVE coins instead of 100:
- As Dave Chamberlain already noted (by starting small: two coins, then
three coins, etc), the odds of the FIRST five being the same is 1/16.
[The first coin can be either head or tail. The next four must be
the same as the first with probability of 1/2 each: (1/2)^4 = 1/16.]
In fact, Dave found a formula (which I will use much later) for odds
of the first "k" coins the same: 2/2^k.

To go from small to large, induction is often helpful.
Can you use what you already know and just add on the extra bit?

For SIX coins:
- The odds of five in a row among the first five is known (1/16).
- Look at having five in a row, but NOT in the first five.
It must be the last five the same, with the first different.
The odds of that are 1/32.
[The first coin can be either heads or tails. The next five must
all be different from the first with probability 1/2 each.]
These two possibilities are "mutually exclusive".
If the last five are the same with the first coin different,
then there cannot be five the same among the first five.
So we can just add the probabilities: 1/16+1/32=3/32.

Similarily for SEVEN coins:
- The odds of five in a row among the first six is known (3/32).
- Look at having five in a row, but NOT in the first six.
Again, it must be the last five the same with the preceeding coin
(that is the second coin) different. Odds of that are still 1/32.
Total 3/32+1/32=4/32.

Also for EIGHT coins we get 5/32 and for NINE coins we get 6/32.

But for TEN coins there is a problem.
- If the last five coins are the same, with the preceeding coin
different, we could still have the first five coins the same!
The two cases are no longer mutually exclusive.
However, the first five coins are "independant" of the last
five coins and we already know the odds that they do NOT have
five in a row the same (1-1/16). The odds that the last five
coins are the same and different from the preceeding (fifth)
coin is still 1/32.
- So the odds that the last five are the same (different from
the preceeding coin) AND that there are NOT already five in
a row amongst the first five is: 1/32*(1-1/16).
(The odds of having both of two independant events is just
the product of their individual odds.)

So the total odds of finding five in a row among ten coins is:
The odds of five in a row among the first nine PLUS
the odds of the last five the same (different from the preceeding coin)
AND NOT have five the same before the last five (in the first five).
= 6/32 + 1/32*(1-1/16) = 111/512

This last idea can be continued.
The total odds of finding five in a row among ELEVEN coins is:
The odds of five in a row among the first TEN coins PLUS
the odds of the last five the same (different from the preceeding coin)
AND NOT have five the same before the last five (in the first SIX)
= 111/512 + 1/32*(1-3/32) = 251/1024

In general:
The total odds of finding five in a row among N coins is:
The odds of five in a row among the first (N-1) coins PLUS
the odds of the last five the same (different from the preceeding coin)
AND NOT having five the same in the first (N-5).

If we write F_5(N) = the odds of having 5 in a row among N coins.
The above is a recusive formula:
F_5(N) = F_5(N-1) + (1/32)*[1-F_5(N-5)] for N>5.
For N=5, we have F_5(5)=1/16 and for N<5 we have F_5(N)=0 of course.

More generally if F_k(N) = the odds of having k in a row among N coins:

/ 0 N<k
F_k(N) = { 2/2^k N=k
\ F_k(N-1) + [1-F_k(N-k)]/2^k N>k

I don't want to think about finding a closed-form for this,
but it is easily evaluated with a simple program. In REXX:

/* Find the odds of at least Number in a row the same
out of a Total number of coins tossed. */

Say "Enter the number in a row the same:"
Pull Number
Say "Enter the total number of coins tossed:"
Pull Total

/* Trivial odds - fewer coins tossed than wanted in a row. */
Do Count=0 to Number-1
Odds.Count=0
end

/* Dave's formula for tossing a number of coins all the same. */
Odds.Number=2/(2**Number) /* Double * is exponentiation in REXX */

/* Now use the recursive formula */
Do Count=Number+1 to Total
PreviousCount=Count-1
EarlyCount=Count-Number
Odds.Count=Odds.PreviousCount+(1/32)*(1-Odds.EarlyCount)
end

Say "The odds are: " Odds.Total*100"%"

I'll leave it to the readers to translate into your favorite language.
The above produced:

Enter the number in a row the same:
5
Enter the total number of coins tossed:
100
The odds are: 97.1689674%

There are techniques for turning such recursive formulas into
closed form formulas, but I'll go no further for now.

Instead, here is a simplier challenge:

Can you find the expected number (the average number) of sequences
of exactly five coins in a row the same (heads or tails) from a
sequence of 100 random coin tosses?

This is essentially the last question from last year's Hypatia
contest and I think the solution leads (with considerable work)
to a solution for the problem of finding the odds of having at
least one sequence of exactly five in a row the same.

|)|\/| || Crofton House School
|\| |ore...@olc.ubc.ca || Beautiful British Columbia
Mathematics & Computer Science || (Canada)

### Dave Chamberlain

Sep 6, 2005, 8:00:43â€¯PM9/6/05
to

Fakename <fake...@comcast.net> wrote:

: "Dave Chamberlain" <da...@osmium.mv.net> wrote in message
: news:dfgcri\$2fls\$1...@pyrite.mv.net...
: >
: > With 5 coins: 2:32 = 1:16 = 6.25%

: > With 6 coins: 2:64 = 1:32 = 3.125%
: >
: >

: No, what I mean is ...if you tossed the coin exactly 100 times, what is the
: probability that you will get at least one run of five in a row (either

Well without having the time to fully think it through, my answer
would be that where percentage means "of 100", I would say that if
you through a coin 100 times you would find it coming up 5 of the
same (in a row) 6 1/4 times (6.25%)

### Duane Bozarth

Sep 7, 2005, 11:58:28â€¯PM9/7/05
to

Fakename wrote:
>
> a run of ten would count as two runs of five.
> a run of six would count as one run of five... and so on.
...

I was thinking of it as there are 95 "runs of five" tosses. Toss 1-5,
2-6, 3-7, ..., 94-98, 95-99, 96-100. Each of those is independent until
the last condition that a run of six is to be counted as only one run

### BlankMondragon

Sep 7, 2005, 11:58:29â€¯PM9/7/05
to

Fakename wrote:
: If you toss 100 coins, what's the probability of getting 5,
: either heads or tails, in a row? 6 in a row?

: How do you figure it out?

You can make a simulation.

Create a list of 100 tosses:

[1 1 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1
0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 1 1 1]

group them:

[[1 1] [0 0] [1] [0 0] [1] [0] [1 1 1 1] [0] [1 1] [0 0 0] [1 1 1 1 1 1
1] [0] [1 1 1] [0] [1] [0] [1 1] [0 0] [1] [0] [1] [0] [1 1 1] [0 0 0 0
0] [1 1 1] [0 0 0 0 0] [1 1] [0 0 0] [1 1] [0] [1] [0] [1] [0 0] [1 1
1] [0 0] [1 1] [0 0] [1 1] [0 0] [1] [0] [1] [0] [1 1] [0 0] [1 1 1 1
1] [0] [1 1 1]]

count the members of each group:

[2 2 1 2 1 1 4 1 2 3 7 1 3 1 1 1 2 2 1 1 1 1 3 5 3 5 2 3 2 1 1 1 1 2 3
2 2 2 2 2 1 1 1 1 2 2 5 1 3]

find the maximum of those:

7

is that number greater than or equal to 5 (if 5 is what you want)

1

(1 means true, 0 means false)

Create a list of many such experiments (here I show 100 if them):

[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]

find the average

0.99

If you try with 1000 experiments instead of just a 100 you'll get
values like:

show simul 5
0.975

show simul 6
0.84

show simul 7
0.548

show simul 8
0.3

show simul 9
0.15

show simul 10
0.081

Daniel

### Robert Morewood

Sep 8, 2005, 12:23:59â€¯PM9/8/05
to

BlankMondragon (blankmo...@gmail.com) wrote about FakeName's query:
: : If you toss 100 coins, what's the probability of getting 5,

: : either heads or tails, in a row? 6 in a row?
: : How do you figure it out?
:
: You can make a simulation.
:
< intermediate results snipped >
:
: show simul 5

: 0.975
:
: show simul 6
: 0.84

Hi BlankMondragon,

Would you care to share some of your code? Did you do that in LISP?

_
|)|\/|ore...@olc.ubc.ca || Fermat is dead! ||
|\| |Beautiful BC (Canada) || Long Live Wiles!! ||

### BlankMondragon

Sep 9, 2005, 1:38:10â€¯AM9/9/05
to

On 8 Sep 2005 at 6:36, Robert Morewood wrote:

> BlankMondragon (blankmo...@gmail.com) wrote about FakeName's query:
> : : If you toss 100 coins, what's the probability of getting 5,
> : : either heads or tails, in a row? 6 in a row?
> : : How do you figure it out?
> :
> : You can make a simulation.
> :
> < intermediate results snipped >
> :
> : show simul 5
> : 0.975
> :
> : show simul 6
> : 0.84
>

> Would you care to share some of your code? Did you do that in LISP?

It's Logo. MSWLogo with LogoFE (Logo Functional Extensions).
LogoFE is in Spanish.

make "many.throws impon "random clona: 100 2

show :many.throws

[1 1 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1
0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 1 1 1]

show disgrega duplica :many.throws
[[1 1] [0 0] [1] [0 0] [1] [0] [1 1 1 1] [0] [1 1] [0 0 0] [1 1 1 1 1 1

1] [0] [1 1 1] [0] [1] [0] [1 1] [0 0] [1] [0] [1] [0] [1 1 1] [0 0 0 0
0] [1 1 1] [0 0 0 0 0] [1 1] [0 0 0] [1 1] [0] [1] [0] [1] [0 0] [1 1
1] [0 0] [1 1] [0 0] [1 1] [0 0] [1] [0] [1] [0] [1 1] [0 0] [1 1 1 1

1] [0] [1 1 1]]

show impon "count disgrega duplica :many.throws

[2 2 1 2 1 1 4 1 2 3 7 1 3 1 1 1 2 2 1 1 1 1 3 5 3 5 2 3 2 1 1 1 1 2 3
2 2 2 2 2 1 1 1 1 2 2 5 1 3]

show max impon "count disgrega duplica :many.throws
7

show esmenor: 4 max impon "count disgrega duplica :many.throws
1

make "many.experiments impon [esmenor: 4 max impon "count disgrega
duplica impon "random] clona: 100 clona: 100 2

show :many.experiments

[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]

show media :many.experiments
0.99

funciona "simul [concreta [media impon [esmenor: dec \$X max impon
"count disgrega duplica impon "random] clona: 1000 clona: 100 2]]

show simul 5
0.975

show simul 6
0.84

show simul 7
0.548

show simul 8
0.3

show simul 9
0.15

show simul 10
0.081

### Dave Chamberlain

Sep 9, 2005, 11:11:12â€¯AM9/9/05
to

BlankMondragon <blankmo...@gmail.com> wrote:

: show disgrega duplica :many.throws

: [[1 1] [0 0] [1] [0 0] [1] [0] [1 1 1 1] [0] [1 1] [0 0 0] [1 1 1 1 1 1
: 1] [0] [1 1 1] [0] [1] [0] [1 1] [0 0] [1] [0] [1] [0] [1 1 1] [0 0 0 0
: 0] [1 1 1] [0 0 0 0 0] [1 1] [0 0 0] [1 1] [0] [1] [0] [1] [0 0] [1 1
: 1] [0 0] [1 1] [0 0] [1 1] [0 0] [1] [0] [1] [0] [1 1] [0 0] [1 1 1 1
: 1] [0] [1 1 1]]

Using the combinations formula (2 ^ 5 = 32) and saying that you're looking
for 2 of the combinations (all heads or all tails/all 0's all 1's)
you want 2 out of 32 or 2/32 = 1/16 = .0625 or 6.25%.

In looking at what you have above, you found 5 ones in a row 4 times
(you found 7 in a row, which has 3 groups of 5 in a row) and 5 zeroes
2 times, for a total of 6.

Got to love it when math works :-)

: show simul 5
: 0.975

: show simul 6
: 0.84

: show simul 7
: 0.548

: show simul 8
: 0.3

: show simul 9
: 0.15

: show simul 10
: 0.081

--

-davec
-----------------------------------------------------------------

### Duane Bozarth

Sep 9, 2005, 2:50:19â€¯PM9/9/05
to

Dave Chamberlain wrote:
>
> BlankMondragon <blankmo...@gmail.com> wrote:
>
> : show disgrega duplica :many.throws
> : [[1 1] [0 0] [1] [0 0] [1] [0] [1 1 1 1] [0] [1 1] [0 0 0] [1 1 1 1 1 1
> : 1] [0] [1 1 1] [0] [1] [0] [1 1] [0 0] [1] [0] [1] [0] [1 1 1] [0 0 0 0
> : 0] [1 1 1] [0 0 0 0 0] [1 1] [0 0 0] [1 1] [0] [1] [0] [1] [0 0] [1 1
> : 1] [0 0] [1 1] [0 0] [1 1] [0 0] [1] [0] [1] [0] [1 1] [0 0] [1 1 1 1
> : 1] [0] [1 1 1]]
>
> Using the combinations formula (2 ^ 5 = 32) and saying that you're looking
> for 2 of the combinations (all heads or all tails/all 0's all 1's)
> you want 2 out of 32 or 2/32 = 1/16 = .0625 or 6.25%.
>
> In looking at what you have above, you found 5 ones in a row 4 times
> (you found 7 in a row, which has 3 groups of 5 in a row) and 5 zeroes
> 2 times, for a total of 6.
>
> Got to love it when math works :-)
...

But OP wanted a run of 6 to be only one "event" when I asked what
comprised a "run of five"...

### BlankMondragon

Sep 13, 2005, 6:13:22â€¯PM9/13/05
to

> But OP wanted a run of 6 to be only one "event" when I asked what
> comprised a "run of five"...

In the simulation I showed a run of 6 as only one event.

Notice that this:

[1 1 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1
0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 1 1 1]

was a event because it had a run of 7 heads (ones). 7 was the maximum
number of elements in a run in this particular experiment.

7 was greater than or equal to 5. So this event was represented as a 1
in the following list. Only one of the 100 experiments didn't have a
run of 5 or more.

show :many.experiments
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]

Maybe a clearer way to show the process would be to create a list
composed of the
maximum number of elements in a run of each experiment:

[... 5 7 13 6 4 8 8 7 8 5 6 7 7 8 13 7 5 11 6 6 5 9 9 6 7 7 7 ...]

and then to mark all of the ones that are greater than or equal to 5:

[... 5 7 13 6 4 8 8 7 8 5 6 7 7 8 13 7 5 11 6 6 5 9 9 6 7 7 7 ...]
[... 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...]

Daniel

### Duane Bozarth

Sep 13, 2005, 7:49:29â€¯PM9/13/05
to

BlankMondragon wrote:
>
> > But OP wanted a run of 6 to be only one "event" when I asked what
> > comprised a "run of five"...
>
> In the simulation I showed a run of 6 as only one event.
>

Yes, I was commenting back to Dave Chamberlain who noted a run of 7 as
"3 runs of 5" when doing his calculations of P(5 H|T) independently that
that didn't follow the rules as outlined by OP.

I had noted a similar approach some time much earlier in looking at the
100 tosses as a series of 96 independent sets of 5 but when OP responded
that a run of N >= 5 is to be counted as on run, that eliminates that
simplification.

### Dave Chamberlain

Sep 14, 2005, 1:41:35â€¯AM9/14/05
to

Duane Bozarth <dpbo...@swko.dot.net> wrote:

: BlankMondragon wrote:
: >
: > > But OP wanted a run of 6 to be only one "event" when I asked what
: > > comprised a "run of five"...
: >
: > In the simulation I showed a run of 6 as only one event.
: >

: Yes, I was commenting back to Dave Chamberlain who noted a run of 7 as
: "3 runs of 5" when doing his calculations of P(5 H|T) independently that
: that didn't follow the rules as outlined by OP.

: I had noted a similar approach some time much earlier in looking at the
: 100 tosses as a series of 96 independent sets of 5 but when OP responded
: that a run of N >= 5 is to be counted as on run, that eliminates that
: simplification.

I thought I had replied to this but I don't see my reply.

You're right, the OP (in a later followup I believe) did say that a
run of 6 wouldn't count as two runs of 5, which is fine. I like to
see if the math works for it though. So consider this:

A run of 5 that must be EXACTLY 5 is really a run of 6 with the last one
being opposite. Meaning:
H H H H H T or
T T T T T H

Thus a run of 6 has 64 combinations, 2 of which are acceptable (shown just above).
2 out of 64 (2/64) is 1 out of 32, so roughly 3%. In the sample run there
were 2 runs of exactly 5 tails and 1 run of exactly 5 heads. So the math
does work, 3 out of the 100 tosses resulted in a run of exactly 5.

--

-davec
-----------------------------------------------------------------